Cómo acelerar el cálculo de la distancia Levenshtein

Estoy tratando de ejecutar una simulación para probar la distancia promedio de Levenshtein entre cadenas binarias aleatorias.

Mi progtwig está en python pero estoy usando esta extensión C. La función que es relevante y toma la mayor parte del tiempo calcula la distancia Levenshtein entre dos cadenas y es esta.

lev_edit_distance(size_t len1, const lev_byte *string1, size_t len2, const lev_byte *string2, int xcost) { size_t i; size_t *row; /* we only need to keep one row of costs */ size_t *end; size_t half; /* strip common prefix */ while (len1 > 0 && len2 > 0 && *string1 == *string2) { len1--; len2--; string1++; string2++; } /* strip common suffix */ while (len1 > 0 && len2 > 0 && string1[len1-1] == string2[len2-1]) { len1--; len2--; } /* catch trivial cases */ if (len1 == 0) return len2; if (len2 == 0) return len1; /* make the inner cycle (ie string2) the longer one */ if (len1 > len2) { size_t nx = len1; const lev_byte *sx = string1; len1 = len2; len2 = nx; string1 = string2; string2 = sx; } /* check len1 == 1 separately */ if (len1 == 1) { if (xcost) return len2 + 1 - 2*(memchr(string2, *string1, len2) != NULL); else return len2 - (memchr(string2, *string1, len2) != NULL); } len1++; len2++; half = len1 >> 1; /* initalize first row */ row = (size_t*)malloc(len2*sizeof(size_t)); if (!row) return (size_t)(-1); end = row + len2 - 1; for (i = 0; i < len2 - (xcost ? 0 : half); i++) row[i] = i; /* go through the matrix and compute the costs. yes, this is an extremely * obfuscated version, but also extremely memory-conservative and relatively * fast. */ if (xcost) { for (i = 1; i < len1; i++) { size_t *p = row + 1; const lev_byte char1 = string1[i - 1]; const lev_byte *char2p = string2; size_t D = i; size_t x = i; while (p  D) x = D; *(p++) = x; } } } else { /* in this case we don't have to scan two corner triangles (of size len1/2) * in the matrix because no best path can go throught them. note this * breaks when len1 == len2 == 2 so the memchr() special case above is * necessary */ row[0] = len1 - half - 1; for (i = 1; i = len1 - half) { size_t offset = i - (len1 - half); size_t c3; char2p = string2 + offset; p = row + offset; c3 = *(p++) + (char1 != *(char2p++)); x = *p; x++; D = x; if (x > c3) x = c3; *(p++) = x; } else { p = row + 1; char2p = string2; D = x = i; } /* skip the lower triangle */ if (i <= half + 1) end = row + len2 + i - half - 2; /* main */ while (p  c3) x = c3; D = *p; D++; if (x > D) x = D; *(p++) = x; } /* lower triangle sentinel */ if (i  c3) x = c3; *p = x; } } } i = *end; free(row); return i; } 

¿Se puede acelerar esto?

Ejecutaré el código en ubuntu de 32 bits en un procesador AMD FX ™ -8350 de ocho núcleos.

Aquí está el código de python que lo llama.

 from Levenshtein import distance import random for i in xrange(16): sum = 0 for j in xrange(1000): str1 = bin(random.getrandbits(2**i))[2:].zfill(2**i) str2 = bin(random.getrandbits(2**i))[2:].zfill(2**i) sum += distance(str1,str2) print i,sum/(1000*2**i) 

Podrías correr este paralelo tal vez. Genere una lista gigante de randoms al inicio, luego en su bucle, genere hilos (8 hilos) a la vez para cada proceso, una parte de la lista y agregue su resultado final a la variable de sum. O genera una lista de 8 a la vez y haz 8 a la vez.

El problema con la sugerencia de openmp es “Este algoritmo se paraliza pobremente, debido a una gran cantidad de dependencias de datos” – Wikipedia

 from threading import Thread sum = 0 def calc_distance(offset) : sum += distance(randoms[offset][0], randoms[offset][1]) #use whatever addressing scheme is best threads = [] for i in xrange(8) : t = new Thread(target=calc_distance, args=(i)) t.start() threads.append(t) 

luego….

 for t in threads : t.join() 

Creo que este método se portaría muy bien para abrir más tarde también si el kernel de distancia de levenshtein estuviera disponible (o codificable).

Esto es solo una publicación rápida de la memoria, por lo que probablemente haya algunos problemas que resolver.

Lo que yo haría:

1) Optimización muy pequeña: asigne una vez por todas las row para evitar la sobrecarga de administración de memoria. O puede probar realloc() , o puede hacer un seguimiento del tamaño de la row en una variable estática (y tener la row estática también). Sin embargo, esto ahorra muy poco, aunque cuesta poco ponerlo en marcha.

2) Estás tratando de calcular un promedio. Hacer el cálculo promedio en C también. Esto debería salvar algo en las llamadas. De nuevo, pequeño cambio, pero resulta barato.

3) Ya que no está interesado en los cálculos reales sino solo en los resultados, entonces, digamos que tiene tres PC y cada una de ellas es una máquina de cuatro núcleos. Luego, ejecute en cada una de ellas cuatro instancias del progtwig, con el bucle doce veces más corto. Obtendrá doce resultados en una doceava parte del tiempo: promedie esos, y Bob es su tío.

La opción # 3 no requiere ninguna modificación en absoluto, excepto el ciclo, y es posible que desee convertirlo en un parámetro de línea de comando, para poder implementar el progtwig en un número variable de computadoras. En realidad, es posible que desee generar tanto el resultado como su “peso”, para minimizar las posibilidades de errores cuando sume los resultados.

 for j in xrange(N): str1 = bin(random.getrandbits(2**i))[2:].zfill(2**i) str2 = bin(random.getrandbits(2**i))[2:].zfill(2**i) sum += distance(str1,str2) print N,i,sum/(N*2**i) 

Pero si está interesado en una estadística genérica de Levenshtein, no estoy tan seguro de que hacer el cálculo con solo 0 y 1 símbolos sea adecuado para su propósito. De la cadena 01010101, obtienes 10101010 ya sea cambiando ocho caracteres o soltando el primero y agregando un cero al final, con dos costos diferentes. Si tiene todas las letras del alfabeto, la segunda posibilidad se vuelve mucho menos probable, y esto debería cambiar algo en el escenario de costo promedio . ¿O me estoy perdiendo algo?

Lo que podría hacer es comenzar por aprender algunos conceptos y directivas de OpenMP de este sitio: Introducción para principiantes a OpenMP

Necesitas un comstackdor que sea compatible con OpenMP. Aquí hay una lista de comstackdores que funcionan . -fopenmp usar la opción -fopenmp cuando -fopenmp su código.

Solo he agregado la directiva del comstackdor #pragma omp parallel for a su código para decirle al comstackdor que los siguientes bloques de código se pueden ejecutar en paralelo. Podría ver mejoras adicionales en el rendimiento al cambiar los bucles while para bucles, o al aplicar el patrón OpenMP a través de esta función. Puede ajustar el rendimiento ajustando el número de subprocesos que se utilizan para ejecutar los bucles for utilizando la función omp_set_num_threads() antes de estos bloques. Un buen número para comenzar es 8, ya que se ejecutará en un procesador de 8 núcleos.

 lev_edit_distance(size_t len1, const lev_byte *string1, size_t len2, const lev_byte *string2, int xcost) { size_t i; size_t *row; /* we only need to keep one row of costs */ size_t *end; size_t half; // Set the number of threads the OpenMP framework will use to parallelize the for loops omp_set_num_threads(8); /* strip common prefix */ while (len1 > 0 && len2 > 0 && *string1 == *string2) { len1--; len2--; string1++; string2++; } /* strip common suffix */ while (len1 > 0 && len2 > 0 && string1[len1-1] == string2[len2-1]) { len1--; len2--; } /* catch trivial cases */ if (len1 == 0) return len2; if (len2 == 0) return len1; /* make the inner cycle (ie string2) the longer one */ if (len1 > len2) { size_t nx = len1; const lev_byte *sx = string1; len1 = len2; len2 = nx; string1 = string2; string2 = sx; } /* check len1 == 1 separately */ if (len1 == 1) { if (xcost) return len2 + 1 - 2*(memchr(string2, *string1, len2) != NULL); else return len2 - (memchr(string2, *string1, len2) != NULL); } len1++; len2++; half = len1 >> 1; /* initalize first row */ row = (size_t*)malloc(len2*sizeof(size_t)); if (!row) return (size_t)(-1); end = row + len2 - 1; #pragma omp parallel for for (i = 0; i < len2 - (xcost ? 0 : half); i++) row[i] = i; /* go through the matrix and compute the costs. yes, this is an extremely * obfuscated version, but also extremely memory-conservative and relatively * fast. */ if (xcost) { #pragma omp parallel for for (i = 1; i < len1; i++) { size_t *p = row + 1; const lev_byte char1 = string1[i - 1]; const lev_byte *char2p = string2; size_t D = i; size_t x = i; while (p <= end) { if (char1 == *(char2p++)) x = --D; else x++; D = *p; D++; if (x > D) x = D; *(p++) = x; } } } else { /* in this case we don't have to scan two corner triangles (of size len1/2) * in the matrix because no best path can go throught them. note this * breaks when len1 == len2 == 2 so the memchr() special case above is * necessary */ row[0] = len1 - half - 1; #pragma omp parallel for for (i = 1; i < len1; i++) { size_t *p; const lev_byte char1 = string1[i - 1]; const lev_byte *char2p; size_t D, x; /* skip the upper triangle */ if (i >= len1 - half) { size_t offset = i - (len1 - half); size_t c3; char2p = string2 + offset; p = row + offset; c3 = *(p++) + (char1 != *(char2p++)); x = *p; x++; D = x; if (x > c3) x = c3; *(p++) = x; } else { p = row + 1; char2p = string2; D = x = i; } /* skip the lower triangle */ if (i <= half + 1) end = row + len2 + i - half - 2; /* main */ while (p <= end) { size_t c3 = --D + (char1 != *(char2p++)); x++; if (x > c3) x = c3; D = *p; D++; if (x > D) x = D; *(p++) = x; } /* lower triangle sentinel */ if (i <= half) { size_t c3 = --D + (char1 != *char2p); x++; if (x > c3) x = c3; *p = x; } } } i = *end; free(row); return i; } 

También puede realizar operaciones de reducción en variables que están siendo operadas en sus bucles for también para proporcionar cálculos paralelos simples como sum, multiplicación, etc.

 int main() { int i = 0, j = 0, sum = 0; char str1[30]; // Change size to fit your specifications char str2[30]; #pragma omp parallel for for(i=0;i<16;i++) { sum = 0; // Could do a reduction on sum across all threads for(j=0;j<1000;j++) { // Calls will have to be changed // I don't know much Python so I'll leave that to the experts str1 = bin(random.getrandbits(2**i))[2:].zfill(2**i) str2 = bin(random.getrandbits(2**i))[2:].zfill(2**i) sum += distance(str1,str2) } printf("%d %d",i,(sum/(1000*2*i))); } } 

Alguien más hizo una gran cantidad de investigación hace uno o dos años e hizo pruebas en tiempo de ejecución también.

Se le ocurrió esto y básicamente usó un árbol de soluciones para acelerar las cosas.