Быстрый поиск в 1 млрд строк
Есть несколько текстовых файлов. Размером от 50 Мб до 5 Гб. Общей сложностью примерно 700-1000 млн строк. Все текстовые файлы лежат в одной папке, их имена известны заранее.
Пример файла:
c4ca4238a0b9233d5fcc509a6f75849b.z001 6b3u3v65vu26u3bv6u
3d5f728d9d4c2f636f067f89cc14862c.z001 4cv5b7nm86ompmp9n6
ecc3d5fe4b5ce2fe28308fd9f2a7baf3.z001 1p864nv6rwye653565
a87ff679a2f3e71d9181a67b73d5f22c.z001 vb4484nb4646v46bvu
e4da3b7f3d5f2345d7772b0674a318d5.z001 vb75in86o486onb7i3
1679091c5a880faf6fb5e6087eb1b2dc.z001 v66v4664u64uvu6464
8f14e45fceea167a5a36dedd4bea2543.z001 4g6v6464buv64ubv64
c9f0f895fb98ab9159f51fd0297e236d.z001 54vb567n7u35gf6b6h
45c48cce2e2d7fbdea1afc51c7c6ad26.z001 g64u34u73h5635g636
Необходимо найти все строки, которые содержат ключевые символы и выгрузить эти строки в отдельный файл. Список ключевых символов находится в отдельном файле keys.txt. Выгружать нужно не всю строку, только с 1 символа до первого знака табуляции или пробела.
Пример файла keys.txt:
3d5f
0000
сссс
Необходимо найти все строки, которые содержат ключевые символы и выгрузить эти строки в отдельный файл. Список ключевых символов находится в отдельном файле keys.txt. Их количество может достигать 100 шт. Выгружать нужно не всю строку, только с 1 символа до первого знака табуляции или пробела.
Т.е. для моего примера правильный выходной файл должен иметь вот такой вид:
c4ca4238a0b9233d5fcc509a6f75849b.z001
3d5f728d9d4c2f636f067f89cc14862c.z001
ecc3d5fe4b5ce2fe28308fd9f2a7baf3.z001
a87ff679a2f3e71d9181a67b73d5f22c.z001
e4da3b7f3d5f2345d7772b0674a318d5.z001
Необходимо обрабатывать подобные файлы как можно быстрее. Желательно, чтобы работало и в Windows и в *nix системах.
Какой алгоритм следует использовать? Может кто-нибудь помочь написать пример?
Ответы (2 шт):
Насколько я понимаю, поиск должен выполняться по каждым запросам однократно, так что:
Очевидно, что ничего быстрее чем прочитать файлы один раз и выполнить одновременно поиск, ничего быть не может. Впрочем, можно поиграться с memory mapped files - теоретически это может повысить скорость чтения.
Внутри каждой строки надо осуществлять поиск. Можно пытаться строить деревья поиска, если обычный поиск недостаточно эффективен, но я по вопросу этого не увидел. Если искомых строк не очень много, они не очень длинные и не сформированы специально, чтобы завалить обычный алгоритм поиска, его должно хватить.
Можно разделить программу на 2 (при необходимости и более) потоков: один считывает данные, другие их (при необходимости параллельно) обрабатывают. Если все данные на одном физическом диске, то считывать в несколько потоков смысла нет, потому что наоборот диск будет работать медленнее. Если на разных, то можно параллелить по физическим дискам.
В общем-то это всё, дальше надо реализовывать и пробовать на конкретных данных.
Имеет ли смысл распараллеливать чтение если файл находится на SSD?
Тоже нет. Главное не косячить с размером блока при чтении (например, использовать блоки по 1048576 байт) и SSD выдаст свою максимальную скорость на 1 поток считывания (замеры есть в комментариях).
Программирование - наука экспериментальная... Так что ставим эксперимент... - см. исходники тут.
Первая программа создала за 3 с половиной минуты 10-гиговый файл со случайными строками и файл ключей, причем каждая пятая строка в файле данных обязательно содержала тот или иной ключ.
Вторая программа читает эти 10 гиг и заносит в отдельный файл первые части строк, в которых найдены ключи. Читает построчно, проверяет тупо, испытывая все 100 ключей, пока не найдет или пока ключи не закончатся (это для тех, кто через 40 строк кода продраться не может...).
По мне - достаточно жесткое испытание. Машина у меня далеко не премиум класса :), но менее чем за 11 минут собрала гиговый файл с найденными строками.
Считаю это "ужас-ужас-ужас!" надуманным, как таковой особой проблемы просто нет...
По заявкам зрителей :)
Если искомых строк нет вообще - обработка чуть больше 2 минут.
Если все строки - искомые, то примерно 10 минут. Вероятно, потому что теперь не требуется в 90% случаев прогонять весь поиск, по всем 100 ключам.
Применение алгоритма Ахо-Корасик сократило время работы первоначального эксперимента (там, где было 11 минут) вдвое.
Испытывать по 10 раз и считать среднее - у меня терпения не хватило :)