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

Question

Как видно из названия, у меня есть файл, содержащий словари (каждая по одной строке), отсортированные по А-Я, и я хотел бы получить все словари с помощью данный префикс. Проблема состоит в том, что файл содержит более одного сортированного пробега A-Z, каждый из которых представляет собой другой язык. Невозможно выполнить предварительную обработку файла данных, и поскольку вы не можете определить длину сортированного прогона, я не могу думать о лучшем способе, чем просто перемещаться по всему файлу и сравнивать на пробеге, который принимает O (n). Можно ли достичь O (logN) с помощью этого странно отсортированного файла?

Answer 1

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

Однако, если начальное смещение каждого прогона известно, то полное сканирование файла необходимо выполнить только один раз, и двоичный поиск может быть использован в каждом разделе - для ~ O(k lg (n/k)) после построения индекса. Стартовые смещения тривиально доступны на время работы программы и могут быть сохранены в файле кеша по мере необходимости.

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

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

Answer 2

Вы можете объединить списки k в 1 отсортированный список (k way merge), который является задачей o (n * lg (k)). После этого вы сможете выполнить команду o (log n).