Подтвердить что ты не робот

Оптимизация очень часто используемой функции анаграммы

Я написал функцию, которая определяет, являются ли два слова анаграммами. слово A - это анаграмма слова B, если вы можете построить слово B из A, просто переставив буквы, например:

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

Это отлично работает, но по мере увеличения количества слов (и эта функция используется несколько миллионов раз в моей заявке), он очень скоро стал основным узкое место моего приложения.

Есть ли у кого-нибудь представление о том, как ускорить эту функцию?

4b9b3361

ОТВЕТЫ

Ответ 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)) от сортировка двух строк.

Ответ 2

У вас есть 26 символов, создайте массив один размером 26, затем выполните итерацию по обоим словам и по мере того, как вы добавляете символы в словах, добавьте соответствующий элемент массива для символов в первом слове и декремент соответствующего элемента массива для символов во втором слове. Если слова являются анаграммами, все элементы массива будут 0 в конце. Сложность будет равна O (N), где N - длина слов.

Ответ 3

Здесь набор функций, которые выполняют анализ анаграмм:

#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[] создаст нулевое значение, если там нет записи в is_anagram1, что также показывает некоторое достойное улучшение.

Результаты из MY-машины, они могут отражать или не отражать результаты на других машинах, но я сомневаюсь, что "победитель против проигравшего" будет существенно отличаться.

Edit:

Мысль о операции "найти" и решила использовать ее по-разному:

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

Дает небольшое улучшение по сравнению с исходной функцией, но не лучше, чтобы конкурировать с решением массива, которое дает лучший результат.

Ответ 4

В дополнение ко всем другим предложениям, если вы пытаетесь найти пары анаграмм в наборе, вы будете вызывать is_anagram по тем же аргументам (хотя не те же самые пары аргументов ) несколько раз.

Большинство решений состоят из двух шагов:

  • сопоставить строковые аргументы с каким-либо другим объектом (отсортированная строка, массив длиной 26, карта как в вашем собственном решении)
  • сравнить эти объекты друг с другом.

Если у вас есть набор строк N, и вы хотите найти все пары, которые являются анаграммами друг друга, вы будете называть is_anagram O(N^2) раз.

Вы можете сэкономить много, сначала вычислив шаг 1 выше для каждой строки N, а затем сравнив результаты.

Ответ 5

Я предлагаю решение, которое сортирует только одну из двух строк:

 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 символов), он также требует меньше памяти, чем решение "count up/down".

Для более длинных строк, которые являются анаграммами, с другой стороны, он начинает отставать от решения "count up/down".

Анализ

См. код и результаты ниже. Как легко видеть, мое решение (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

Ответ 6

Предполагая, что большинство пар слов не являются анаграммами, наиболее вероятный случай, который вам нужно оптимизировать, - это случай сбоя.

Очевидно, что если длины различны, то строки не могут быть анаграммами, а длина - это свойство, которое вычисляется один раз при создании строки, что делает ее очень эффективной для сравнения в качестве быстрого выхода.

Если вы измените свой класс строк, чтобы включить в него больше этих свойств, вы можете повысить точность результата. Вместо запуска тестовой функции:

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;

Средняя строка используется только в том случае, если кодировка символов не является многобайтовой. Если вы работаете с многобайтовой схемой кодирования, хэш все равно устранит большинство неанаграмм, но у него будет много ложных срабатываний, поскольку некоторые байтовые порядки не могут быть проигнорированы.

Взлом Тест-код матов Petersson для чтения из словаря, и, пробовав этот и другие алгоритмы на реальном английском словаре, мы видим примерно фактор четырех улучшений по сравнению с следующим лучшим алгоритмом (это было десять раз, но я изменил другой код):

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

(количество обращений отличается от того, что последние два алгоритма нечувствительны к регистру, и мой словарь, вероятно, включал акронимы, сталкивающиеся с естественными словами)

update. Хотя это не то, что было задано, мне было небрежно не указывать на это. Я не знаю, не заметил ли я это, или мне просто надоело печатать, или если я не хочу делать предположения о вызывающем коде...

Как только вы все хешировали, тривиальный способ свести к минимуму количество тестов - сортировать список по этому хэшу. Затем вы можете тривиально ограничить сравнение с частями списка, которые, вероятно, совпадают (в соответствии с хэшем). Это также может сделать предсказание ветвей более эффективным.

Я только что попробовал сменить Итерацию N ^ 2, с которой я тестировал первоначально (я уверен, что это было намеренно неэффективно), чтобы перебирать соседей в отсортированном списке. Вызов sort() доминировал по времени, но был на 200 раз быстрее, чем самый быстрый тест N ^ 2, и выбор алгоритма сравнения больше не имел сколько-нибудь значимой разницы в производительности.

Или вы можете просто бинать слова хэшем, когда вы их получите.

Ответ 7

Как насчет этого решения? Это в С#, если вы не возражаете.

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;

}