Блог

У меня есть два текстовых файла. Один содержит список примерно из 70 000 имен (~ 1,5 МБ). Другой содержит текст, который будет получен из разных источников. То есть содержимое этого файла будет меняться каждый раз при запуске программы (~ 0,5 МБ). По сути, я хочу иметь возможность вставить некоторый текст в текстовый файл и посмотреть, какие имена из моего списка найдены. Что-то вроде функции поиска (CTR F), но с 70 000 ключевыми словами.

В любом случае, то, что у меня есть на данный момент, это:

 int main()
{
     ifstream namesfile("names.txt");   //names list
     ifstream miscfile("misc.txt");     //misc text
     vector<string> vecnames;           //vector to hold names
     vector<string> vecmisc;            //vector to hold misc text
     size_t found;

     string s;
     string t;

     while (getline(namesfile,s))       
         veccomp.push_back(s);  

     while (getline(miscfile,t))        
         vectenk.push_back(t);

     //outer loop iterates through names list
     for (vector<string>::size_type i = 0; i != vecnames.size();   i) {
         //inner loop iterates through the lines of the mist text file
         for (vector<string>::size_type j = 0;j != vecmisc.size();   j) {
             found=vecmisc[j].find(vecnames[i]);
             if (found!=string::npos) {
                 cout << vecnames[i] << endl;
                 break;
             }
         }
     }

     cout << "SEARCH COMPLETE";

     //to keep console application from exiting
     getchar();

     return 0;
 }
  

Теперь это отлично работает в том, что касается извлечения нужных мне данных, однако это ужасно медленно и, очевидно, неэффективно, поскольку для каждого имени требуется, чтобы я потенциально снова выполнял поиск по всему файлу, что дает (75000 x # строк в текстовом файле misc) итерации. Если кто-нибудь может помочь, я был бы, безусловно, признателен. Некоторые примеры кода приветствуются. Кроме того, я использую Dev C , если это имеет какое-либо значение. Спасибо.

Используйте std::hash_set . Вставьте все ваши ключевые слова в набор, затем просмотрите большой документ и каждый раз, когда вы подходите к слову, проверяйте, содержит ли набор это слово.

Используя вектор, в лучшем случае время поиска, которое вы получите, составляет O (log N) сложности при использовании бинарного алгоритма поиска, и это будет работать только для отсортированного списка. Если учесть время, которое потребуется для выполнения отсортированных вставок в список, конечная амортизированная сложность для отсортированного линейного контейнера (массивов, списков), а также нелинейных контейнеров, таких как деревья двоичного поиска, равна O(N log N). По сути, это означает, что если вы добавите в список больше элементов, время, необходимое как для добавления этих элементов в список, так и для их последующего поиска, увеличится со скоростью, немного превышающей линейную скорость роста списка (т. Е., если вы удвоите размер списка, на сортировку списка уйдет чуть более чем вдвое больше времени, и тогда любой поиск по списку будет довольно быстрым … чтобы удвоить время поиска, список должен был бы увеличиться в квадрате от существующего количества элементов).

С другой стороны, хорошая реализация хэш-таблицы (такая как std::unordered_map ) наряду с хорошим хэш-алгоритмом, который позволяет избежать слишком большого количества коллизий, имеет амортизированную сложность O (1) … это означает, что в целом для любого заданного элемента требуется постоянное время поиска, независимо от того, сколько в нем элементов, что делает поиск очень быстрым. Основным недостатком линейного списка или дерева двоичного поиска для хэш-таблицы является фактический объем памяти хэш-таблицы. Хорошая хэш-таблица, чтобы избежать слишком большого количества коллизий, должна иметь размер, равный некоторому большому простому числу, которое, по крайней мере, больше 2 * N, где N — общее количество элементов, которые вы планируете хранить в массиве. Но «потраченное впустую пространство» — это компромисс для эффективного и чрезвычайно быстрого поиска.

В то время как карта любого вида является самым простым решением, Скотт Майерс приводит веские аргументы в пользу sorted vector и binary_search из algorithm (в эффективном STL).

При использовании отсортированного вектора ваш код будет выглядеть примерно так

 #include <algorithm>
  

…

 int vecsize = vecnames.size();
sort(vecnames.begin(), vecnames.begin()   vecsize );
for (vector<string>::size_type j = 0;j != vecmisc.size();   j)
{
  bool found= binary_search(vecnames.begin(), vecnames.begin() vecsize,vecmisc[j]);
  if (found) std::cout << vecmisc[j] << std::endl;
}
  

Преимущества использования отсортированного вектора и binary_search заключаются в

1) Нет дерева для обхода, двоичный поиск начинается с (end-start) / 2 и продолжает делиться на 2. Для поиска в диапазоне потребуется не более log (n).

2) Отсутствует пара ключ-значение. Вы получаете простоту вектора без накладных расходов на карту.

3) Элементы вектора находятся в непрерывном диапазоне (вот почему вы должны использовать reserve перед заполнением вектора, вставки выполняются быстрее), и поэтому поиск по элементам вектора редко пересекает границы страницы (немного быстрее).

4) Это круто.