Какой самый быстрый способ найти строки в текстовых файлах? Случайный сценарий: поиск определенного пути в текстовом файле с 50000 файловыми путями (каждый путь имеет собственную строку).Самый быстрый способ найти подстроки в текстовых файлах
Файл такого размера должен легко вписываться в память, и вы можете сделать его в std :: set (или даже лучше hashset, если у вас есть библиотека этого под рукой) с путями в качестве элементов. Проверка того, будет ли точный путь, будет очень быстрым.
Если вам нужно искать подпункты, то сортируемый std :: vector (если вы ищете только префиксы) может быть единственным полезным подходом - или если вы ищете полностью общие подстроки путей, то вам все равно нужно будет сканировать весь вектор, но если вы не будете делать это за миллион раз, это будет не так уж плохо.
Это поле для регулярных выражений; вы должны смотреть в grep и awk.
Вам нужно найти одну строку один раз в файле, одну и ту же строку в нескольких файлах, несколько строк в одном файле?
В зависимости от сценария у вас есть несколько возможных ответов.
построение stucture данных (например, набор, предложенный Alex) является полезным, если у вас есть, чтобы найти несколько строк в одном файле
используя алгоритм, как Boyer-Moore является эффективным, если вы должны искать одна строка
с использованием механизма регулярных выражений, вероятно, будет предпочтительнее, если вам придется искать несколько строк.
Я не уверен, насколько вы хотели бы использовать поиск, но FSM - хорошие варианты использования.
Вот дискуссия: Short example of regular expression converted to a state machine?
Я сомневаюсь, что это самый быстрый способ - его самый простой. Если поиск по определенному пути будет самым быстрым способом, нужно прочитать каждую строку, сравнить его с найденным путем и прервать, как только найдет совпадение. Все остальное накладное. Кроме того, std :: hash_set обычно намного быстрее, чем std :: set. –
Да, я рекомендовал хэш-набор, если у вас есть библиотека с этим - помните, что это НЕ в стандарте C++ (пока), несмотря на стандартно-нарушающий префикс 'std:', используемый некоторыми библиотеками. Чтение нескольких 100 КБ в один глоток является эмпирически более быстрым (по крайней мере, в многозадачных системах с хорошими FS, дисковыми кэшами, readahead и т. Д.), Чем смешивание операций ввода-вывода и процессора, как вы предлагаете - сегодня стоимость дискового ввода-вывода гораздо больше, чем в линейных чтениях (100 КБ <1 мсек), и смешение может позволить переключателям контекста, вызывая поиск (поскольку другие процессы будут искать в другом месте на диске). –
Я потратил время и написал образец теста. Вы ошибаетесь: чтение 5-мегабайтного файла с 80000 строк занимает около 0,60 с на хорошей машине, включая strcmp для каждой строки. Если я опускаю strcmp и вместо этого создаю std :: set, время выполнения увеличивается до 0.75s. –