优化经常使用的anagram函数

Question

我写了一个函数来确定两个单词是否是字谜.单词A是单词B的字谜,如果你可以通过重新排列字母来构建单词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

地图创建和您std::map::find在迭代中的调用非常昂贵.

在这种情况下,您可以使用std::string在许多方面表现得像a 的事实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))排序两个字符串的喧嚣.

Answer 2

你有26个字符,制作一个大小为26的数组,然后遍历两个单词,当你用字包围字符时,为第一个字中的字符增加一个相应的数组元素,并减少第二个字中字符的相应数组元素字.如果单词是字谜,那么所有数组元素最后都是0.复杂性只是O(N),其中N是单词的长度.

Answer 3

以下是一系列执行anagram分析的函数:

#include <iostream>
#include <iomanip>
#include <map>
#include <cctype>
#include <string>
#include <algorithm>

using namespace std;

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

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


bool is_anagram1(const std::string & s1, const std::string & s2)
{
    auto check = [](const std::string& x)
    {
        std::map<char, unsigned> counter;
        for(auto c : x)
        {
        ++counter[c];
        }
        return counter;
    };

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


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


bool is_anagram3(std::string s1, std::string s2)
{
    if (s1.length() != s2.length()) return false;
    std::sort(s1.begin(), s1.end());
    std::sort(s2.begin(), s2.end());
    return s1 == s2;
}

bool is_anagram4(const std::string &s1, const std::string &s2)
{
    int arr[256] = {};
    if (s1.length() != s2.length()) return false;
    for(std::string::size_type i = 0; i < s1.length(); i++)
    {
    arr[(unsigned)s1[i]]++;
    arr[(unsigned)s2[i]]--;
    }
    for(auto i : arr)
    {
    if (i) return false;
    } 
    return true;
}

bool is_anagram5(const std::string &s1, const std::string &s2)
{
    int arr[26] = {};
    if (s1.length() != s2.length()) return false;

    for(std::string::size_type i = 0; i < s1.length(); i++)
    {
    arr[(unsigned)tolower(s1[i])-'a']++;
    arr[(unsigned)tolower(s2[i])-'a']--;
    }
    for(auto i : arr)
    {
    if (i) return false;
    } 
    return true;
}


static __inline__ unsigned long long rdtsc(void)
{
    unsigned hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}


template<typename T>
void bm(const char *name, T func, 
    const std::string &s1, const std::string &s2)
{
    unsigned long long time = rdtsc();
    bool res = func(s1, s2);
    time = rdtsc()-time;
    cout << "Function" << left << setw(15) << name 
     << " time: " << right << setw(8) << time 
     << " Res: " << res << endl;
}


#define BM(x) bm(#x, x, s1, s2)

int main()
{
    const std::string short1 = "lead";
    const std::string short2 = "deal";
    const std::string long1 = "leaddealleaddealleaddealleaddealleaddealleaddealleaddealleaddealleaddealleaddeal";
    const std::string long2 = "dealleaddealleaddealleaddealleaddealleaddealleaddealleaddealleaddealleaddeallead";

    cout << "Testing with short strings:" << endl;
    std::string s1 = short1;
    std::string s2 = short2;

    BM(is_anagram);
    BM(is_anagram1);
    BM(is_anagram2);
    BM(is_anagram3);
    BM(is_anagram4);
    BM(is_anagram5);

    cout << "Testing with long strings:" << endl;
    s1 = long1;
    s2 = long2;

    BM(is_anagram);
    BM(is_anagram1);
    BM(is_anagram2);
    BM(is_anagram3);
    BM(is_anagram4);
    BM(is_anagram5);

    cout << "Testing with inequal short string:" << endl;
    s1 = short1;
    s2 = short2;
    s1[s1.length()-1]++;

    BM(is_anagram);
    BM(is_anagram1);
    BM(is_anagram2);
    BM(is_anagram3);
    BM(is_anagram4);
    BM(is_anagram5);

    cout << "Testing with inequal long string:" << endl;
    s1 = long1;
    s2 = long2;
    s1[s1.length()-1]++;

    BM(is_anagram);
    BM(is_anagram1);
    BM(is_anagram2);
    BM(is_anagram3);
    BM(is_anagram4);
    BM(is_anagram5);
}

结果如下:

Testing with short strings:
Functionis_anagram      time:    72938 Res: 1
Functionis_anagram1     time:    15694 Res: 1
Functionis_anagram2     time:    49780 Res: 1
Functionis_anagram3     time:    10424 Res: 1
Functionis_anagram4     time:     4272 Res: 1
Functionis_anagram5     time:    18653 Res: 1
Testing with long strings:
Functionis_anagram      time:    46067 Res: 1
Functionis_anagram1     time:    33597 Res: 1
Functionis_anagram2     time:    52721 Res: 1
Functionis_anagram3     time:    41570 Res: 1
Functionis_anagram4     time:     9027 Res: 1
Functionis_anagram5     time:    15062 Res: 1
Testing with inequal short string:
Functionis_anagram      time:    11096 Res: 0
Functionis_anagram1     time:    10115 Res: 0
Functionis_anagram2     time:    13022 Res: 0
Functionis_anagram3     time:     8066 Res: 0
Functionis_anagram4     time:     2963 Res: 0
Functionis_anagram5     time:     1916 Res: 0
Testing with inequal long string:
Functionis_anagram      time:    44246 Res: 0
Functionis_anagram1     time:    33961 Res: 0
Functionis_anagram2     time:    45004 Res: 0
Functionis_anagram3     time:    38896 Res: 0
Functionis_anagram4     time:     6455 Res: 0
Functionis_anagram5     time:    14603 Res: 0

很明显,根据每个角色的出现,使用数组向上/向下计数的直接检查是胜利者.我拿了原始代码并删除了find,只是使用了一个事实,map::operator[]如果没有条目,a 将创建一个零值is_anagram1,这也表明了一些不错的改进.

结果来自我的机器,这些可能会或可能不会反映其他机器上的结果,但我怀疑"胜利者与失败者"将会有显着差异.

编辑:

想到"查找"操作,并决定以不同的方式使用它:

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

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

与原始功能相比有一点改进,但​​不足以与提供最佳结果的阵列解决方案竞争.

Answer 4

除了所有其他建议之外,如果你试图在集合中找到成对的字谜,你将重复调用is_anagram相同的参数(尽管不是相同的参数对).

大多数解决方案包括两个步骤:

1. 将字符串参数映射到其他对象(已排序的字符串,长度为26的数组,与您自己的解决方案中的映射)
2. 将这些对象相互比较

如果你有一组N字符串,并且想要找到彼此字符串的所有对,那么你将调用is_anagram O(N^2)时间.

您可以先为每个N字符串计算上面的步骤1 ,然后比较结果,从而节省很多.