c++ - 优化非常常用的字谜函数

Question

我写了一个函数来判断两个单词是否是字谜。单词如果您可以通过重新排列从 A 中构建单词 B，则 A 是单词 B 的字谜字母，例如:

lead is anagram of deal

这是我的功能:

bool is_anagram(std::string const & s1, std::string const & s2)
{
    auto check = [](std::string const & x)
    {
        std::map<char, unsigned> counter;
        for(auto const & c : x)
        {
            auto it = counter.find(c);
            if(it == counter.end())
                counter[c] = 1;
            else
                ++counter[c];
        }
        return counter;
    };

    return check(s1) == check(s2);
}

这很好用，但是随着单词数量的增加(并且使用了此功能在我的应用程序中数百万次)，它很快成为一个主要的我的应用程序的瓶颈。

有人知道如何加快这个功能吗？

Answer 1

map 创建和您调用std::map::find在迭代中，相当昂贵。

在这种情况下，您可以使用 std::string在许多方面表现得像一个 std::vector<char> ，这意味着您可以使用 std::sort 对其进行排序:

bool is_anagram(std::string s1, std::string s2)
{
    std::sort(s1.begin(), s1.end());
    std::sort(s2.begin(), s2.end());
    return s1 == s2;
}

我将复制字符串而不是您创建的两个 map (通过值而不是 const 引用传递它们)并对它们进行排序，所以

sort("lead") => "adel"
sort("deal") => "adel"

此更改应该已经大大加快了您的算法速度。多一个如果您倾向于比较任意的东西，可能会极大地影响性能话:

bool is_anagram(std::string s1, std::string s2)
{
    if(s1.length() != s2.length())
        return false;
    /* as above */
}

如果两个字符串的长度不同，显然不能是字谜。 std::string::length()是一个非常快速的操作(它需要存储无论如何都是字符串大小)，所以我们省去了 O(N*log(N)) 的麻烦。从对两个字符串进行排序。