Алгоритм внешнего поиска
Если у меня очень большой отсортированный список хранится во внешнем хранилище. Предполагая, что этот список не может быть перенесен во внутреннюю память, какой будет хороший алгоритм поиска, который ищет ключ в этом списке в псевдокоде? какова будет сложность времени? и какие основные факторы следует учитывать при разработке этого алгоритма?
1 ответ
Предполагая, что ваше внешнее хранилище представляет собой простой массив записей постоянного размера, хранящихся в файле, и ваш язык программирования позволяет отображать файл в памяти, вы можете использовать обычный алгоритм двоичного поиска.
Скажем, в C++ вы
- mmap файл принимает void* указатели на начало и конец файла mmap,
- приведите указатели к вашему типу записи
- и затем ищите запись, используя std:: lower_bound (), которая является одной из стандартных реализаций бинарного поиска.
Обратите внимание, что отображение файла в памяти не означает загрузку всего файла во внутреннюю память, вместо этого система автоматически загрузит необходимые страницы из файла в кэш загруженных страниц с разумной политикой сохранения размера кэшированных страниц в пределах доступных границ памяти.
Это стандартная практика поиска в отсортированных файлах, и нет причин для ее повторного проектирования (насколько мне известно). Сложность алгоритма бинарного поиска во внешней памяти зависит от модели внешнего хранилища, стратегии буферизации / подкачки и т. Д., Но для вашего жесткого диска вы все еще можете предположить, что он находится в обычном O(log N). Я бы порекомендовал вам поискать учебники и библиотеки по неосновным алгоритмам и структурам данных.