🎊 STL 的set容器查找效率惊人

今天测试词典对中文句子分词

采用vector容器和stl的find算法，分词速度为：15026字/秒

采用set容器的分词速度为：20214600字/秒

后者是前者的1000多倍，下面的例子，用vector耗时10秒左右，用set瞬间即可完成。平衡二叉树的威力确实厉害 .据说set容器的底层是自平衡二叉树的一种（红黑树）。

set唯一的缺点就是不能根据find（）函数返回的迭代器修改里面的数据。

//用C++测试词典分词的速度

#include

#include

#include

#include

#include

#include

#include

using namespace std;

int main()

{

ifstream dict_file("mini_dict.txt");

vector dict;

//set segs;

vector segs;

if (dict_file.good())

{

string word;

while (dict_file.peek() != EOF)

{

dict_file >> word;

//dict.insert(word);

dict.push_back(word);

}

}

string text = "中文编码是一个复杂而繁琐的问题，尤其是在使用C++的时候，不像python这种直接就可以迭代出单个中文字符，C++中是以字节为单位的，那么我们要读取一个中文字符就要读取三次字节流，读取英文字符就只需要读取一次，是不是超级麻烦。那么C++怎么样在中英文混合的字符串中分离中英文或者计算字符串长度（不是字节数）呢，那就需要彻底搞清楚编码是个怎么回事";

clock_t start = clock();

string seg;

for (int i = 0; i < text.size();)

{

string longest_word = text.substr(i, 3);

for (int j = i + 3; j < text.size() + 1; j += 3)

{

seg = text.substr(i, j - i);

//if (dict.find(seg) != dict.end())

if (find(dict.begin(), dict.end(), seg) != dict.end())

{

if (seg.size() > longest_word.size())

{

longest_word = seg;

}

}

}

i = i + longest_word.size();

segs.push_back(longest_word);

}

clock_t end = clock();

cout << "分词完成\n";

double consumeTime = (double)(end - start) / CLOCKS_PER_SEC;

cout << "分词速度:" << text.size() / 3 * 1000.0 / consumeTime << "字/秒" << endl;

for (auto p = segs.begin(); p != segs.end(); p++)

cout << *p << endl;

}