Самый быстрый метод для запуска двоичного поиска файла в C?

Question

Например, допустим, я хочу найти определенное слово или число в файле. Содержимое в отсортированном порядке (очевидно). Поскольку я хочу запустить бинарный поиск по файлу, кажется, что это настоящая трата времени, чтобы скопировать весь файл в массив и затем запустить бинарный поиск ... Я фактически сделал это алгоритмом с линейным временем, потому что мне придется потратить O (n) время, чтобы скопировать чертов файл, прежде чем я смогу начать поиск.

Есть ли более быстрый способ сделать это? Может быть, есть что-то вроде lseek, которое работает со строками вместо байтов?

Если нет, то мне лучше вместо этого просто выполнить линейный поиск (при условии, что я запускаю поиск один раз для всей продолжительности моей программы)?

Answer 1

Вы не можете искать по линии. Это довольно очевидно, если подумать.

Но вы можете выполнить своего рода двоичный поиск по текстовому файлу.

Что вы делаете:

• Стат файл, чтобы получить длину или искать до конца и получить позицию.
• Карта памяти файла.
  (Думаю, это лучше, но вы можете использовать lseek и читать, если нужно.)
• Поиск в середине файла, минус средняя длина строки. Просто угадай.
• Сканирование вперед для новой строки, если вы не в позиции 0.
• Прочитайте свою строку и сравните.
• Повторите для 1/4 или 3/4, 1/8, 1/16 и т. Д.

Answer 2

Бинарный поиск на диске должен быть, по крайней мере на начальном этапе, « block-based », т. Е. Учитывать тот факт, что если вы читаете один байт целой группы, то ввод / вывод Стоимость одинакова. Другой считает, что нужно знать о относительной более высокой стоимости операции поиска по сравнению с последовательной операцией чтения .

Несколько способов использования этой информации о характеристиках дискового ввода-вывода:

• В конце поиска предпочтение отдается линейному поиску (сканированию), а не поиску.
• В начале проверяйте как первый, так и последний элемент в блоке, это может помочь экстраполировать лучшую догадку для следующего разбиения
• Кэширование дерева (или даже короткого плоского списка) некоторых элементов, найденных в различных местах файла (немного похоже на промежуточные узлы в формальной структуре btree)
• Объявите и используйте соответствующий размер буфера

Answer 3

Если файл небольшой, например, несколько сотен килобайт, почти наверняка быстрее (или практически карта памяти) прочитать весь файл в память. Это связано с тем, что затраты на выполнение нескольких операций ввода-вывода для поиска и передачи намного хуже, чем простое чтение всего файла, что и делают большинство программ, и большинство операционных систем считают, что это сделано.

Если все строки не имеют одинаковую длину или очень предсказуемую длину, простого способа поиска строки #n нет. Но чтобы выполнить бинарный поиск, я бы работал со смещением байтов в бинарном поиске и читал, скажем, 100 байт (если длина всех слов меньше 100 символов) до и после смещения - всего 200 байт. Затем найдите строку до и после середины, чтобы извлечь слово.

Answer 4

Не было бы функции "lseek", потому что файловые команды не имеют понятия "строки". Это понятие существует на другом уровне абстракции, чем необработанные файловые команды.

От того, будет ли он быстрее или нет, ответ будет зависеть от ряда факторов, включая размер файла, скорость дисковода и объем доступной оперативной памяти. Если это не большой файл, я думаю, что будет быстрее загрузить весь файл в память.

Если это большой файл, я бы использовал алгоритм двоичного поиска, чтобы сузить его до меньшего диапазона (скажем, пару мегабайт), а затем загрузил бы весь этот блок.

Answer 5

Да, вы можете искать, но было бы полезно, если бы фиксировался размер каждого слова / числа в строке, если это не так, что более вероятно, тогда вам придется искать по размеру файла и искать ближайшее слово, начинающее все еще достигать типичной сложности O (log n) времени двоичных поисков.

Answer 6

Как упоминалось выше, поскольку файл является текстовым файлом, прогнозирование байта, с которого начинается данная строка в файле, не может быть надежно выполнено. Идея бинарного поиска ersatz довольно хороша. Но это действительно не сэкономит вам тонну, если файл не будет огромным, учитывая, насколько быстрым является последовательный ввод-вывод в настоящее время и насколько медленным является случайный ввод-вывод.

Как вы упомянули, если вы собираетесь читать это, вы можете также линейно искать его по ходу дела. Так что сделайте так, используйте модифицированный поиск Бойера-Мура, когда будете его читать, и у вас все получится.

Answer 7

Здесь так много компромиссов в производительности, что невозможно понять, что имеет смысл, пока у вас не будет измерений на типовых данных.

Если вы собираетесь сохранить этот код, он должен быть простым. Если поиск выполняется редко или файл небольшой, используйте линейный поиск. Если стоимость действительно имеет значение, вам придется провести несколько экспериментов.

Второе, что я бы попробовал после линейного поиска, - это mmap файл и просмотр его на наличие новых строк. Это занимает линейное время, но strchr может быть очень быстрым. Это помогает, если вы можете гарантировать, что файл заканчивается новой строкой. Как только вы разметите линии, вы можете сохранить небольшое количество сравнений, выполнив бинарный поиск.

Другой вариант, который вы должны рассмотреть, - поиск строки Бойера-Мура. Это сублинейный поиск по времени, и в зависимости от размера шаблона поиска он может быть быстрее, чем логарифмический двоичный поиск. Бойер-Мур особенно хорош с длинными поисковыми строками.

Наконец, если вы определите, что бинарный поиск действительно хорош, но определение строк является узким местом производительности, вы можете предварительно вычислить начальное местоположение каждой строки и сохранить эти предварительно вычисленные местоположения в двоичном формате во вспомогательном файле.

Я чувствую себя комфортно, делая только одно предсказание: почти наверняка стоит избегать чтения по одной строке за раз с чем-то вроде readline() или fgets(), потому что эта стратегия неизменно включает в себя вызов malloc() для хранения содержимого линия. Стоимость звонка malloc() на каждую линию, вероятно, будет завышать любые затраты на поиск или сравнение.