如何优化C++中双文本文件单词匹配的O(n²)算法？

当然有更高效的解决办法！你现在用的嵌套循环在十万+百万级的数据量下，O(n²)的时间复杂度肯定会慢到离谱——15分钟没完成完全在意料之中。下面给你两种实用的优化思路，能把时间复杂度降到线性或线性对数级别，处理速度会提升几个数量级：

方法一：哈希集合（推荐，实现简单且速度快） #

核心逻辑是先把规模更小的那个单词集合放进哈希集合（C++里的unordered_set），因为哈希集合的查找操作平均时间是O(1)。之后遍历规模更大的集合，逐个检查单词是否在哈希集合里，存在就执行doSomething()。

这种方法的时间复杂度是O(n + m)（n是小集合的大小，m是大集合的大小），空间复杂度是O(n)——十万级的字符串占用的内存完全在现代程序的承受范围内。

代码示例：

#include <unordered_set>
#include <vector>
#include <string>

void processWords(const std::vector<std::string>& firstTextFile, const std::vector<std::string>& secondTextFile) {
    // 优先把小集合放进哈希表，节省内存和构建时间
    const auto& smallerVec = firstTextFile.size() < secondTextFile.size() ? firstTextFile : secondTextFile;
    const auto& largerVec = firstTextFile.size() >= secondTextFile.size() ? firstTextFile : secondTextFile;

    std::unordered_set<std::string> wordSet(smallerVec.begin(), smallerVec.end());

    for (const std::string& word : largerVec) {
        if (wordSet.contains(word)) { // C++20及以上可用contains，旧版本用find != end
            doSomething();
        }
    }
}

注：如果你的编译器不支持C++20，把wordSet.contains(word)换成wordSet.find(word) != wordSet.end()即可。

方法二：排序 + 双指针（无额外内存开销） #

如果担心哈希集合的内存占用，可以先对两个向量排序，再用双指针遍历找交集。这种方法的时间复杂度是O(n logn + m logm)（主要是排序的时间），空间复杂度是O(1)（如果允许原地排序原始向量的话，否则需要复制一份向量的内存）。

代码示例：

#include <vector>
#include <string>
#include <algorithm>

void processWords(const std::vector<std::string>& firstTextFile, const std::vector<std::string>& secondTextFile) {
    // 复制原向量避免修改原始数据，若允许修改原数据可直接排序
    std::vector<std::string> sortedFirst = firstTextFile;
    std::vector<std::string> sortedSecond = secondTextFile;

    std::sort(sortedFirst.begin(), sortedFirst.end());
    std::sort(sortedSecond.begin(), sortedSecond.end());

    size_t i = 0, j = 0;
    while (i < sortedFirst.size() && j < sortedSecond.size()) {
        if (sortedFirst[i] == sortedSecond[j]) {
            doSomething();
            // 跳过重复单词，避免重复执行doSomething()（如果不需要重复执行的话）
            const std::string current = sortedFirst[i];
            while (i < sortedFirst.size() && sortedFirst[i] == current) ++i;
            while (j < sortedSecond.size() && sortedSecond[j] == current) ++j;
        } else if (sortedFirst[i] < sortedSecond[j]) {
            ++i;
        } else {
            ++j;
        }
    }
}

额外优化提示 #

• 如果doSomething()本身是耗时操作，可以考虑多线程并行处理：把大集合分成多个子块，每个子块单独检查哈希集合，同时执行操作，能进一步压缩处理时间。
• 处理重复单词：如果两个文件里有重复的同一单词（比如第一个文件"apple"出现5次，第二个出现3次），要明确需求是每次匹配都执行doSomething()，还是只执行一次。哈希集合方法默认会去重（每个单词只存一次），如果需要处理重复匹配，可以用unordered_map统计每个单词的出现次数，再根据次数执行对应次数的操作。

内容的提问来源于stack exchange，提问作者AshTJ94