Алгоритм внешнего поиска

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

1 ответ

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

Скажем, в C++ вы

  1. mmap файл принимает void* указатели на начало и конец файла mmap,
  2. приведите указатели к вашему типу записи
  3. и затем ищите запись, используя std:: lower_bound (), которая является одной из стандартных реализаций бинарного поиска.

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

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

Другие вопросы по тегам