c++ - cómo - Optimizar la función de anagrama muy a menudo utilizada

anagramas

Question

He escrito una función que determina si dos palabras son anagramas. La palabra A es un anagrama de la palabra B si puedes construir la palabra B de A simplemente cambiando la forma de las letras, por ejemplo:

lead is anagram of deal

Esta es mi función:

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

Esto funciona bien, pero a medida que aumenta el número de palabras (y esta función se usa varios millones de veces en mi aplicación), muy pronto se convirtió en un cuello de botella importante de mi aplicación.

¿Alguien tiene una idea de cómo acelerar esta función?

Answer 1

¿Qué hay de esta solución? Está en C # si no te importa.

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;

}

Answer 2

Además de todas las otras sugerencias, si intenta encontrar pares de anagramas en un conjunto, llamará is_anagram sobre los mismos argumentos (aunque no los mismos pares de argumentos) repetidamente.

La mayoría de las soluciones constan de dos pasos:

1. mapear los argumentos de cadena a algún otro objeto (una cadena ordenada, una matriz de longitud 26, un mapa como en su propia solución)
2. comparar estos objetos entre sí

Si tiene un conjunto de N cadenas y desea buscar todos los pares que son anagramas entre sí, estará llamando is_anagram O(N^2) veces.

Puede ahorrar mucho calculando primero el paso 1 anterior para cada una de las N cadenas y luego comparando los resultados.

Answer 3

Aquí hay una selección de funciones que realizan análisis de anagramas:

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

Y los resultados:

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

Está bastante claro que la verificación directa con una matriz que cuenta arriba / abajo según la ocurrencia de cada personaje es el ganador. Tomé el código original y eliminé el find , y solo usé el hecho de que un map::operator[] creará un valor cero si no hay ninguna entrada allí en is_anagram1 , que también muestra una mejora decente.

Los resultados son de MI máquina, estos pueden o no reflejar los resultados en otras máquinas, pero dudo que el "ganador vs perdedor" vaya a ser significativamente diferente.

Editar:

Pensó en la operación "buscar" y decidió usarla de otra manera:

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

Mejora un poco la función original, pero no lo suficiente como para competir con la solución de matriz que ofrece el mejor resultado.

Answer 4

La creación del mapa y su llamada a std::map::find dentro de la iteración, es bastante costosa.

En este caso, puede usar el hecho de que std::string comporta en muchos aspectos como std::vector<char> , lo que significa que puede ordenarlo usando 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;
}

En lugar de los dos mapas que estás creando, tomo una copia de las cadenas (pasándolas por valor en lugar de referencia constante) y ordenándolas, por lo que

sort("lead") => "adel"
sort("deal") => "adel"

Este cambio ya debería acelerar tu algoritmo bastante. Una cosa más que puede afectar en gran medida el rendimiento si tiende a comparar palabras arbitrarias:

bool is_anagram(std::string s1, std::string s2)
{
if(s1.length() != s2.length())
return false;
/* as above */
}

Si la longitud de las dos cuerdas difiere, obviamente no puede ser un anagrama. std::string::length() es una operación muy rápida (necesita almacenar el tamaño de la cadena de todos modos), así que nos ahorramos el ajetreo de O(N*log(N)) al ordenar las dos cadenas.

Answer 5

Propongo una solución que clasifica solo una de las dos cadenas:

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

Esta solución podría ser ventajosa en situaciones en las que tiene un carácter en una cadena que no está en la otra, porque si no encuentra ese carácter en la otra cadena, puede acortar la evaluación (en contraste con todas las demás soluciones que se muestran aquí, donde siempre se evalúan ambas cadenas completas). Especialmente si este personaje exclusivo de un lado ocurre temprano en una larga secuencia ...

Una ventaja sobre la solución de clasificación también es el espacio de almacenamiento requerido: la solución de clasificación requiere que se copien las dos cadenas, mientras que en mi solución solo se crea una copia. Para longitudes de cadena más cortas (dependiendo del tipo de int utilizado para contar, pero al menos hasta 256 caracteres), también requiere menos memoria que la solución de "contar arriba / abajo".

Para cadenas más largas que son anagramas, por otro lado, comienza a quedar atrás de la solución "contar arriba / abajo".

Análisis

Vea el código y los resultados a continuación. Como se puede ver fácilmente, mi solución (is_anagram3) es bastante rápida para anagramas cortos (solo superada por el método de conteo ascendente / descendente de 26 caracteres que no es totalmente funcionalmente equivalente), y también es más rápida para el caso no anagram largo con no- juego de caracteres; pero tiende a ser más lento que los métodos de conteo ascendente / descendente para cadenas más largas que son anagramas, o para no anagramas largos que solo difieren según el recuento de caracteres.

Resumen

Al final, realmente dependería de los datos de entrada esperados sobre cuál es la solución ideal:

• Para llamadas individuales, las soluciones de "contar hacia arriba / abajo" generalmente darán el mejor rendimiento en muchos casos.
• Dependiendo de las circunstancias (por ejemplo, con qué probabilidad las cadenas contienen caracteres diferentes, como se mencionó anteriormente), mi solución podría ser más rápida
• Aún no se ha probado, pero parece seguro: en el caso en que tenga muchas verificaciones de anagramas, y cuando implemente un caché para las cadenas ordenadas, la solución de clasificación y comparación se convertirá en la más rápida.

Código:

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

Salida

Medido en mi máquina Atom lenta, los resultados pueden variar un poco en diferentes sistemas, pero en general debería dar una buena imagen de los rendimientos relativos:

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

Answer 6

Suponiendo que la mayoría de los pares de palabras no son anagramas, el caso que más necesita optimizar es el caso de falla.

Obviamente, si las longitudes son diferentes, las cadenas no pueden ser anagramas, y la longitud es una propiedad que se calcula una vez cuando se crea la cadena, por lo que es una cosa muy eficiente para comparar como una salida rápida.

Si cambia su clase de cadena para incluir más de estas propiedades, puede mejorar la precisión del caso de salida rápida. En lugar de comenzar la función de prueba con:

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

Podrías usar:

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

y cuando crea la cadena (o después de modificarla), calcularía un valor para hash que es único (o casi único) para todas las cadenas con ese conjunto de letras en orden arbitrario.

Usted solo calcula este hash cuando cambia una cadena; no por cada comparación que haces.

Una forma muy simple de calcular el hash es:

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

esto es rápido de calcular, pero es propenso a las colisiones.

Un método más avanzado:

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;

Tenga en cuenta que dos se omite de la lista de primos. Esto asegura que el prod esté siempre en el coprendido con el rango posible de unsigned long . Esto maximiza la distribución de resultados frente al desbordamiento numérico.

Si la tabla está dispuesta para poner números primos pequeños en posiciones de letra frecuentes, entonces se pueden minimizar los casos en los que se produce un desbordamiento (que puede provocar colisiones de hash). Si no hay desbordamiento, entonces tienes un hash perfecto (para estos fines) y tendrías absoluta certeza en ambos sentidos (devuelve true o false inmediatamente) simplemente comparando el hash .

En consecuencia, calcular el hash de esta manera funciona mucho mejor:

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;

con salidas rápidas:

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

La línea central solo es segura de usar si la codificación de caracteres no es de varios bytes. Si está trabajando con un esquema de codificación de varios bytes, el hash aún eliminará la mayoría de los no anagramas, pero tendrá muchos falsos positivos, ya que algunos ordenamientos de bytes no se pueden ignorar.

Hacking el código de prueba de Mats Petersson para leer de un diccionario, y probar este y otros algoritmos en la entrada real del diccionario de inglés, vemos aproximadamente un factor de mejora cuatro sobre el siguiente mejor algoritmo (fue un factor de diez, pero modifiqué el otro código )

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

(El número de visitas es diferente porque los dos últimos algoritmos no distinguen entre mayúsculas y minúsculas y es probable que mi diccionario incluya acrónimos que colisionan con palabras naturales)

actualización : aunque no es lo que se preguntó, fue negligente por mi parte no señalarlo. No sé si no lo detecté o si me cansé de tipear o si no quería hacer suposiciones sobre el código de llamada ...

Una vez que has hasheado todas las palabras, una forma trivial de minimizar el número de pruebas es ordenar la lista por ese hash. Luego puede limitar trivialmente las comparaciones a partes de la lista que probablemente coincidan (de acuerdo con el hash). Esto también puede hacer que la predicción de ramas sea más eficiente también.

Solo traté de cambiar la iteración N ^ 2 que probé originalmente (estoy seguro de que fue deliberadamente ineficiente) para iterar sobre los vecinos en una lista ordenada. La llamada a sort() dominó el tiempo, pero fue 200 veces más rápida que la prueba N ^ 2 más rápida, y la elección del algoritmo de comparación ya no produjo ninguna diferencia significativa en el rendimiento.

O bien, puede simplemente bin palabras por hash a medida que los reciba.

Answer 7

Tiene 26 caracteres, hace una matriz del tamaño de 26, luego itera a través de ambas palabras y mientras introduce caracteres en palabras, incrementa un elemento de matriz correspondiente para los caracteres en la primera palabra y disminuye el elemento de matriz correspondiente para charaacters en el segundo palabra. Si las palabras son anagramas, todos los elementos de la matriz serán 0 al final. La complejidad será solo O (N) donde N es la longitud de las palabras.