C ++ Search Performance - PullRequest
Новая
       10

C ++ Search Performance

1 голос
/ 21 мая 2011

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

В любом случае, то, что я имею до сих пор, это: 

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;
 }

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

Ответы [ 3 ]

4 голосов
/ 21 мая 2011

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

1 голос
/ 21 мая 2011

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

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

0 голосов
/ 01 декабря 2011

Несмотря на то, что карта любого вида является самым простым решением, Скотт Майерс дает хороший пример для сортировки vector и binary_search из алгоритма (в Effective 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) Элементы вектора находятся в смежном диапазоне (поэтому перед заполнением вектора следует использовать резерв, вставки выполняются быстрее), поэтому поиск по элементам вектора редко пересекает границы страницы (немного быстрее).

4) Это круто.

...