C++实现双文本set_intersection运算极慢 479k词规模优化求助
核心性能问题定位
你现在的程序跑不动,根本不是排序、输出打印的问题,是代码的循环作用域嵌套完全错误,导致操作次数膨胀到了天文数字,具体拆解如下:
为什么现在跑几天都跑不完
- 首先算清楚你的代码实际执行的循环量级:
- 你把存储正序单词的长字符串
words1,和拆出来的分词器tokenizer1,全放在了「逐行读取file2」的内层循环块里。这意味着:每读file2的一行内容,你就会重新创建一个分词器,把整个正序单词表从头拆一遍、从头遍历一遍。 - 如果两个词典的所有单词都是用逗号分隔存在同一行长文本里,那么光读file2的第一行内容,就会触发「遍历整个479k词的正序列表」+「遍历整个479k词的反向列表」的双层循环,总操作量是479k * 479k ≈ 2.3亿亿次,就算CPU每秒能跑10亿次操作,也要跑7年才能跑完——这就是你在游戏PC上跑一整天只出30个结果的根本原因。
- 你把存储正序单词的长字符串
- 你提到的加
cout << "token: " << *it << std::endl;导致程序长时间运行:这行打印确实会拖慢速度,但它只是放大器,不是核心矛盾。endl会强制刷新输出缓冲区,输出速度会比普通写字符慢10-100倍,但就算你把这行删掉,上面说的天文数字级别的循环量,照样要跑几年。 - 你注释掉sort之后10k词规模速度变快,本质上是你原来的sort逻辑本来就是多余的(因为你每次只给vector push一个元素,排序根本没效果),删掉了之后少了无意义的函数调用,自然快了一点,但根本没碰到核心性能问题。
代码里多余的离谱操作
除了循环嵌套的结构错误,你还有一堆完全没必要的操作在进一步拖慢速度:
- 每次处理一个分词,就新建一个只存1个元素的
words1Vec、words2Vec,再调用set_intersection去求交集——等于你为了判断两个单个字符串是否相等,要经历两次内存分配、一次算法调用、一次erase操作,纯纯的资源浪费。 - 把本来应该一次性加载到内存的全量单词数据,拆成了逐行、逐token的即时处理,完全没利用你提到的「两个文件本身已经排好序」的核心优势。
正确的优化思路(新手友好,改完就能秒跑)
完全不用改你的核心设计逻辑,只要把代码结构调整对,479k词的全量文件也能在1秒内跑完:
- 彻底抛弃嵌套读文件的逻辑:先一次性把两个文件里的所有单词全部读出来,分别存在两个独立的有序vector里,全程不要嵌套循环。
- 读
Dictionary.txt的时候,碰到逗号分隔的单词,直接push_back到存储正序单词的vector里,因为文件本身是排好序的,你连sort都不用调用。 - 同理读
Backwardsdictionary.txt的时候,把所有逗号分隔的反转词直接push_back到存储反向单词的vector里,同样不需要排序。
- 读
- 一次性求两个有序vector的交集:因为两个vector都是文件自带的有序结果,直接调用一次
std::set_intersection,就能算出所有匹配的双向拼写单词,总操作量只有两个文件的单词数之和(约100万次),比原来的逻辑快1亿倍以上。 - 删掉所有循环内层的多余操作:不要在循环里反复创建vector、反复新建分词器。读文件的时候就把所有分词操作一次性做完,把单词直接存到全局的vector里。
- 如果你还要留调试打印,把
endl换成'\n',避免每次打印都强制刷新缓冲区,等功能跑通后记得把调试打印全删掉,只保留最终匹配结果的输出。
极简版本的正确逻辑代码参考
#include <iostream> #include <string> #include <fstream> #include <vector> #include <algorithm> #include <boost/tokenizer.hpp> typedef boost::char_separator<char> separator_type; int main() { // 一次性存全量单词的有序vector,文件本身带排序,不需要额外sort std::vector<std::string> normal_words; std::vector<std::string> reversed_words; // 第一次读文件:把正序词典的所有单词全部加载完 std::fstream file1("Dictionary.txt"); if (!file1) { std::cout << "无法打开正序词典文件\n"; return 1; } std::string line; separator_type comma_sep(","); while (std::getline(file1, line)) { boost::tokenizer<separator_type> tok(line, comma_sep); for (auto& word : tok) { if (!word.empty()) { normal_words.push_back(word); } } } file1.close(); // 第二次读文件:把反向词典的所有单词全部加载完 std::fstream file2("Backwardsdictionary.txt"); if (!file2) { std::cout << "无法打开反向词典文件\n"; return 1; } while (std::getline(file2, line)) { boost::tokenizer<separator_type> tok(line, comma_sep); for (auto& word : tok) { if (!word.empty()) { reversed_words.push_back(word); } } } file2.close(); // 两个有序vector直接求交集,一次调用出所有结果 std::vector<std::string> matches; std::set_intersection( normal_words.begin(), normal_words.end(), reversed_words.begin(), reversed_words.end(), std::back_inserter(matches) ); // 输出所有匹配结果 for (auto& word : matches) { std::cout << word << '\n'; } return 0; }
改完之后你会发现,原来要跑几天的479k词规模任务,现在几毫秒就能跑完所有计算,剩下的时间基本都是花在读取本地文件上。
内容的提问来源于stack exchange,提问作者maria9876
相关产品推荐
相关产品推荐

