pro.algorithms
Есть два гигантских файла, то есть на терабайты. Как найти в
них общие строки за минимальное время?
5 ответов
можно суффиксным массивом
Тут нужно понять, какой размер строки, и сколько уникальных строк ожидается? Если строки длинные и редко повторяются, то хэшами индексировать. Нужно понимать, что хэшей тоже могут быть терабайты, зависит от размера хэша и размера строки среднего. Если строки короткие, и вариантов мало, то просто построить хэшсет по одному файлу, потом пройти по второму и искать в хэшсете строки.
Я люблю котиков
Автор вопроса
Тут нужно понять, какой размер строки, и сколько у...
А если и короткие, и при этом редко повторяются? Думал в такой ситуации сортировать один файл и искать в нём строки из другого бинарным поиском. Есть ли способы эффективнее?
А если и короткие, и при этом редко повторяются? Д...
Думаю, что лучше sorted merge сделать, это эффективнее, если файлы на диске.
А если и короткие, и при этом редко повторяются? Д...
Бинарный поиск может быть неэффективен для данных, которые лежат на диске. Обычно используют деревья с большим числом ключей на узле, чтобы меньше прыжков по диску делать. BTREE.
Похожие вопросы
Обсуждают сегодня