29

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

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

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

4

7 回答 7

43

地图创建和您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))对两个字符串进行排序的麻烦。

于 2013-08-08T10:43:25.077 回答
36

你有 26 个字符，创建一个大小为 26 的数组，然后遍历两个单词，当你在单词中遇到字符时，为第一个单词中的字符递增相应的数组元素，并为第二个单词中的字符递减对应的数组元素单词。如果单词是字谜，则所有数组元素最终都将为 0。复杂度将只是 O(N)，其中 N 是单词的长度。

于 2013-08-08T10:53:43.553 回答
33

以下是一些执行字谜分析的函数：

#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);
}

与原始函数相比略有改进，但不足以与提供最佳结果的数组解决方案竞争。

于 2013-08-08T11:35:53.410 回答
7

除了所有其他建议之外，如果您试图在一组中找到成对的字谜，您将重复调用is_anagram相同的参数（尽管不是相同的参数对）。

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

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

如果您有一组N字符串，并且您想找到所有彼此是字谜的对，那么您将调用is_anagram O(N^2)时间。

N您可以通过首先为每个字符串计算上面的步骤 1，然后比较结果来节省很多。

于 2013-08-08T15:36:32.680 回答
4

我提出了一个解决方案，它只对两个字符串中的一个进行排序：

 bool is_anagram(std::string const & s1, std::string s2)
 {
     if (s1.length() != s2.length()) return false;
     for (int i=0; i<s1.length(); ++i)
     {
         size_t pos = s2.find(s1[i], i);
         if (pos == std::string::npos)
         {
             return false;
         }
         std::swap(s2[i], s2[pos]);
     }
     return true;
 }

这种解决方案在一个字符串中有一个字符而另一个字符串中没有的情况下可能是有利的 - 因为如果它在另一个字符串中找不到该字符，它可以缩短评估（与此处显示的所有其他解决方案，其中始终评估两个完整字符串）。特别是如果一侧的这个排他字符出现在一个长字符串的早期......

与排序解决方案相比，一个优势还在于需要存储空间——排序解决方案需要复制两个字符串，而在我的解决方案中只创建一个副本。对于较短的字符串长度（取决于用于计数的 int 类型，但至少最多 256 个字符），它还需要比“向上/向下计数”解决方案更少的内存。

另一方面，对于作为字谜的较长字符串，它开始落后于“向上/向下计数”解决方案。

分析

请参阅下面的代码和结果。可以很容易看出，我的解决方案 (is_anagram3) 对于短字谜非常快（仅被实际上功能不完全等效的 26 个字符向上/向下计数方法击败），并且对于长非字谜的情况也是最快的匹配字符；但对于作为字谜的较长字符串或仅因字符数不同的长非字谜，往往比向上/向下计数方法慢。

概括

最后，对于理想的解决方案是什么，它真的取决于预期的输入数据：

  • 对于单个调用，“向上/向下计数”解决方案通常会在许多情况下提供最佳性能。
  • 根据情况（例如，如上所述，字符串包含不同字符的可能性有多大），我的解决方案可能会更快
  • 尚未测试，但似乎可以肯定：对于要执行许多字谜检查的情况，并且当您为已排序的字符串实现缓存时，排序和比较解决方案将成为最快的。

代码：

#include <string>
#include <map>
#include <algorithm>

#include <sys/time.h>
#include <iostream>
#include <iomanip>

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);
}

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 const & s1, std::string s2)
{
    if (s1.length() != s2.length()) return false;

    for (int i=0; i<s1.length(); ++i)
    {
        size_t pos = s2.find(s1[i], i);
        if (pos == std::string::npos)
        {
            return false;
        }
        std::swap(s2[i], s2[pos]);
    }
    return true;
}

bool is_anagram4(std::string const & s1, std::string const & s2)
{
    if (s1.length() != s2.length()) return false;

    int count[26] = {0};
    for (int i=0; i<s1.length(); ++i)
    {
        count[s1[i]-'a']++;
        count[s2[i]-'a']--;
    }
    for (int i=0; i<26; ++i)
    {
        if (count[i] != 0) return false;
    }
    return true;
}

bool is_anagram5(std::string const & s1, std::string const & s2)
{
    if (s1.length() != s2.length()) return false;

    int count[256] = {0};
    for (int i=0; i<s1.length(); ++i)
    {
        count[s1[i]]++;
        count[s2[i]]--;
    }
    for (int i=0; i<256; ++i)
    {
        if (count[i] != 0) return false;
    }
    return true;
}

template<typename T>
bool test(const char* name, T func)
{
    if (!func("deal", "lead") || !func("lead", "deal") || !func("dealbreaker", "breakdealer") ||
        !func("dealbreakerdealbreakerdealbreakerdealbreaker", "breakdealerbreakdealerbreakdealerbreakdealer") ||
        func("dealbreakerdealbreakerdealbreakerdealbreakera", "breakdealerbreakdealerbreakdealerbreakdealerb") ||
        func("dealxbreakerdealbreakerdealbreakerdealbreaker", "breakdealerbreakdealerbreakdealerbreakdealerb") ||
        func("abcdefg", "tuvwxyz") ||
        func("lot", "bloat") || func("lead", "deala") ||
        func("lot", "bloat") || func("deala", "lead") ||
        func("abc", "abcd"))
    {
        std::cout << name << ": impl doesn't work" << std::endl;
        return false;
    }
    return true;
}

template<typename T>
void measure(const char* name, T func,
    std::string const & s1, std::string const & s2)
{
    timeval start,end;
    unsigned long secDiff;
    long usecDiff;

    gettimeofday(&start, 0);
    for (int i=0; i<100000; ++i)
    {
        func(s1, s2);
    }
    gettimeofday(&end, 0);
    secDiff = end.tv_sec - start.tv_sec;
    usecDiff = end.tv_usec - start.tv_usec;
    if (usecDiff < 0)
    {
        secDiff--;
        usecDiff += 1000000;
    }
 std::cout << name << ": " << secDiff << "."<< std::setw(3) << std::setfill('0') << (usecDiff/1000) << " s" << std::endl;
}

template <typename T>
void run(const char * funcName, T func)
{
    std::cout << funcName << std::endl;
    if (!test(funcName, func)) {
        return;
    }
    measure("short", func, "dealbreaker", "breakdealer");
    measure("short no anagram", func, "abcdefg", "tuvwxyz");
    measure("long", func, "dealbreakerdealbreakerdealbreakerdealbreaker", "breakdealerbreakdealerbreakdealerbreakdealer");
    measure("long no anagram", func, "dealbreakerdealbreakerdealbreakerdealbreakera", "breakdealerbreakdealerbreakdealerbreakdealerb");
    measure("long no anagram nonmatching char", func, "dealxbreakerdealbreakerdealbreakerdealbreaker", "breakdealerbreakdealerbreakdealerbreakdealerb");
}

int main(int argv, char**argc)
{
    run("is_anagram", is_anagram);
    run("is_anagram2", is_anagram2);
    run("is_anagram3", is_anagram3);
    run("is_anagram4", is_anagram4);
    run("is_anagram5", is_anagram5);
}

输出

在我的慢速 Atom 机器上测量，不同系统上的结果可能会有所不同，但总体上应该可以很好地描述相对性能：

is_anagram
short: 2.960 s
short no anagram: 2.154 s
long: 8.063 s
long no anagram: 8.092 s
long no anagram nonmatching char: 8.267 s
is_anagram2
short: 0.685 s
short no anagram: 0.333 s
long: 3.332 s
long no anagram: 3.557 s
long no anagram nonmatching char: 3.740 s
is_anagram3
short: 0.280 s
short no anagram: 0.022 s
long: 0.984 s
long no anagram: 0.994 s
long no anagram nonmatching char: 0.140 s
is_anagram4
short: 0.123 s
short no anagram: 0.071 s
long: 0.399 s
long no anagram: 0.389 s
long no anagram nonmatching char: 0.390 s
is_anagram5
short: 0.283 s
short no anagram: 0.145 s
long: 0.551 s
long no anagram: 0.454 s
long no anagram nonmatching char: 0.455 s
于 2013-08-08T11:41:24.590 回答
4

假设大多数词对不是字谜，那么您最需要优化的情况就是失败情况。

显然，如果长度不同，则字符串不能是字谜，并且长度是在创建字符串时计算一次的属性，因此作为快速比较进行比较是一件非常有效的事情。

如果您更改字符串类以包含更多这些属性，则可以提高快速输出案例的准确性。而不是以以下方式开始测试功能：

if (s1.length() != s2.length()) return false;

你可以使用：

if (s1.hash != s2.hash) return false;

并且当您创建字符串时（或在修改它之后），您将计算一个值，该值对于hash具有该组字母的所有字符串以任意顺序是唯一的（或几乎是唯一的）。

您仅在字符串更改时才计算此哈希；并非针对您所做的每一次比较。

计算哈希的一种非常简单的方法是：

long sum = 0;
for (int i = 0; i < s.length(); i++)
    sum += s[i];
s.hash = sum;

这可以快速计算，但容易发生冲突。

更高级的方法：

static const unsigned int primetable[256] = { 1, 3, 5, 7, /* ... */ };

unsigned long prod = 1;
for (int i = 0; i < s.length(); i++)
    prod *= primetable[s[i]];
s.hash = prod;

请注意，素数列表中省略了两个。这确保prod始终与 的可能范围互质unsigned long。这在面对数值溢出时最大化了结果的分布。

如果该表被安排在频繁的字母位置放置小素数，则可以最大限度地减少发生溢出（可能导致哈希冲突）的情况。如果没有溢出，那么您就有了一个完美的哈希值（出于这些目的），并且您可以true通过false比较hash.

因此，像这样计算散列效果要好得多：

static const unsigned int primetable[256] = {
    1, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619,
    821, 823, 827, 829, 839, 853, 857, 107, 859, 863, 877, 881, 883, 109, 887, 907, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 911, 919, 929, 937, 941, 947,
    601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
    359, 11, 61, 31, 37, 3, 71, 43, 59, 7, 101, 79, 29, 53, 13, 23, 47, 103, 17, 5, 19, 41, 73, 83, 89, 67, 97, 367, 373, 379, 383, 389,
    1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427,
    953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171,
    397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
    173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353
};

unsigned long prod = 1;
boolean overflow = false;
for (int i = 0; i < s.length(); i++)
{
    overflow |= (prod > ULONG_MAX / primetable[s[i]]);
    prod *= primetable[s[i]];
}
if (overflow)
    prod ^= 1;
s.hash = prod;

快速输出：

if (s1.hash != s2.hash) return false;
if ((s1.hash & 1) != 0) return true;
if (s1.length() != s2.length()) return false;

仅当字符编码不是多字节时，才可以安全使用中间行。如果您使用的是多字节编码方案，那么哈希仍然会消除大多数非字谜，但它会产生很多误报，因为某些字节顺序不能被忽略。

破解Mats Petersson 的测试代码以从字典中读取，并在真实的英语字典输入上尝试这个和其他算法，我们看到比下一个最佳算法大约提高了 4 倍（它是 10 倍，但我调整了其他代码):

Functionis_anagram      time:    218.9s hits: 93
Functionis_anagram1     time:      200s hits: 93
Functionis_anagram2     time:       40s hits: 93
Functionis_anagram3     time:     7.74s hits: 93
Functionis_anagram4     time:     2.65s hits: 93
Functionis_anagram5     time:      2.3s hits: 166
Functionis_anagram6     time:     0.56s hits: 166  <- This method

（命中数不同，因为最后两种算法都不区分大小写，而且我的字典可能包含与自然词冲突的首字母缩略词）

更新：虽然这不是被问到的，但我没有指出这一点是我的疏忽。我不知道我是否没有发现它，或者我只是厌倦了打字，或者我不想对调用代码做出假设......

对所有单词进行散列处理后，最小化测试次数的一种简单方法是按该散列对列表进行排序。然后，您可以轻松地将比较限制为可能匹配的列表部分（根据哈希）。这也可以使分支预测更有效。

我只是尝试更改我最初测试的 N^2 迭代（我确信这是故意低效的）以迭代排序列表中的邻居。该sort()调用支配了时间，但比最快的 N^2 测试快 200 倍，并且比较算法的选择不再对性能产生任何有意义的差异。

或者，您可以在收到单词时通过哈希对单词进行分类。

于 2013-08-09T10:45:24.630 回答
0

这个解决方案怎么样？如果您不介意，它在 C# 中。

public bool isAnagram(string first, string second) {
    if(first == null || second == null)
        return false;
    if(first.Length != second.Length)
        return false;
    string characters = "abcd...zABCD...Z";
    int firstResult = 0;
    int secondResult = 0;
    foreach(char x in second) {
        if(first.IndexOf(x) == -1)
            return false;
        if(char == " ")
            secondResult += 0;
        else
            secondResult += characters.IndexOf(x);
    }
    foreach(char x in first) {
        if(char == " ")
            firstResult += 0;
        else
            firstResult += characters.IndexOf(x);
    }
    return firstResult == secondResult;

}

于 2014-07-17T14:13:21.493 回答