优化非常常用的字谜功能

一尘不染

优化非常常用的字谜功能

algorithm

我写了一个函数，确定两个单词是否是字谜。如果您可以通过重新排列字母来从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);
}

这很好用，但是随着单词数量的增加（此功能在我的应用程序中使用了数百万次），很快就成为我应用程序的主要瓶颈。

有谁知道如何加快此功能？

阅读 201

2020-07-28

共1个答案

一尘不染

映射的创建以及您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;
}

而不是您要创建的两个映射，我正在获取字符串的副本（通过值而不是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))对两个字符串进行排序的麻烦。

2020-07-28