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

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

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

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

Результаты получены на МОЕЙ машине, они могут отражать или не отражать результаты на других машинах, но я сомневаюсь, что «победитель против проигравшего» будет существенно отличаться.

Редактировать:

Подумал об операции «найти» и решил использовать ее по-другому:

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

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

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

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

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

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

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

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

 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

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

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

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

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;

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

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

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() call доминировал во времени, но был в 200 раз быстрее, чем самый быстрый тест N ^ 2, и выбор алгоритма сравнения больше не оказывал существенного влияния на производительность.

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

Как насчет этого решения? Это в 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;

}