производительность — эффективный способ поиска строки в файле в C ++ для очень больших входных данных

У меня есть основной файл, который имеет миллионы строк. Затем, читая каждую строку из файла, мне нужно найти строку в другом файле, в котором гораздо меньше строк (всего несколько тысяч), чтобы принять какое-то решение. В настоящее время я использую вектор для чтения второго файла в начале, а затем для каждой строки в основном файле я перебираю вектор, чтобы найти строку. Проблема в том, что время работы довольно долго. Есть ли эффективный способ выполнить задачу и ограничить время работы каким-то разумным значением.

1

Решение

Вы должны прочитать второй файл в std::map<std::string,int>, Ключ карты — это строка, а значение — количество раз, когда строка встречалась во втором файле.

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

1

Другие решения

Вы можете попробовать заменить второй (меньший) вектор на std :: set.

0

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

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

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

0
По вопросам рекламы [email protected]