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

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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

Answer 7

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

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

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

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

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

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