C++搜索性能

Question

我有两个文本文件。其中包含大约 70,000 个姓名的列表 (~1.5MB)。另一个包含将从各种来源获得的文本。也就是说，每次执行程序时，该文件的内容都会发生变化（~0.5MB）。本质上，我希望能够将一些文本粘贴到文本文件中，并查看在我的列表中找到了哪些名称。有点像查找功能 (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杂项文本文件中的行数）迭代。如果有人可以提供帮助，我一定会很感激。一些示例代码是最受欢迎的。此外，如果这有什么区别的话，我正在使用 Dev C++。谢谢。

Answer 1

使用 std::hash_set。将所有关键字插入集合中，然后遍历大型文档，每次遇到一个单词时，测试集合中是否包含该单词。

Answer 2

使用向量，使用二分搜索算法获得的最佳情况搜索时间是 O(log N) 复杂度，并且这只适用于排序列表。如果将排序插入到列表中所需的时间包括在内，则排序线性容器（数组、列表）以及非线性容器（例如二叉搜索树）的最终摊余复杂度为 O(N log N ）。因此，这基本上意味着，如果向列表添加更多元素，则将这些元素添加到列表以及稍后查找它们所需的时间将以比线性增长率稍快的速度增加。列表（即，如果将列表的大小加倍，则对列表进行排序将花费两倍多的时间，然后列表上的任何搜索都会非常快......为了使搜索时间加倍，该列表必须按现有元素数量的平方增长）。

另一方面，良好的哈希表实现（例如 std::unordered_map）以及避免过多冲突的良好哈希算法的摊余复杂度为 O(1) ..这意味着总的来说，无论有多少元素，任何给定元素都有一个恒定的查找时间，这使得搜索速度非常快。哈希表相对于线性列表或二叉搜索树的主要缺点是哈希表的实际内存占用量。为了避免太多冲突，一个好的哈希表的大小需要等于某个至少大于 2*N 的大质数，其中 N 是您计划存储在哈希表中的元素总数。大批。但“浪费的空间”是高效且极快的查找的代价。

Answer 3

虽然任何类型的映射都是最简单的解决方案，但 Scott Myers 为排序向量和来自算法的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）没有要遍历的树，binary_search从（end-start）/2开始，并不断除以2搜索范围最多需要log(n)。

2）没有键、值对。您可以获得矢量的简单性，而无需地图的开销。

3）向量的元素位于连续范围内（这就是为什么在填充向量之前应该使用保留，插入速度更快），因此向量元素的搜索很少跨越页面边界（稍微快一些）。

4）这很酷。