¿Puede este código de Python ser más eficiente?

He escrito algún código para encontrar cuántas subcadenas de una cadena son pares de anagtwigs. La función para encontrar anagram(anagramSolution) es de complejidad O (N). La función de subcadena tiene una complejidad menor que N cuadrada. Pero, este código aquí es el problema. ¿Se puede optimizar más?

 for i in range(T): x = raw_input() alist = get_all_substrings(x) for k, j in itertools.combinations(alist,2): if(len(k) == len(j)): if(anagramSolution(k,j)): counter +=1 counterlist.append(counter) counter = 0 

La alist puede tener miles de artículos (subconjuntos). El principal problema es el bucle. Se está tardando mucho tiempo en iterar sobre todos los elementos. ¿Hay alguna forma más rápida o más eficiente de hacer esto?

Defina la clase de anagtwig de una cadena para que sea el conjunto de conteos de cuántas veces aparece cada letra en la cadena. Por ejemplo, 'banana' tiene clase de anagtwig a: 3, b: 1, n: 2 . Dos cadenas son anagtwigs entre sí si tienen la misma clase de anagtwig. Podemos contar la cantidad de subcadenas de la cadena en cada clase de anagtwig, luego calcular el número de pares al computar (n choose 2) para cada clase de anagtwig con n subcadenas:

 from collections import Counter anagram_class_counts = Counter() for substring in get_all_substrings(x): anagram_class_counts[frozenset(Counter(substring).viewitems())] += 1 anagram_pair_count = sum(x*(x-1)/2 for x in anagram_class_counts.viewvalues()) 

frozenset(Counter(substring).viewitems()) construye una representación hashable de la clase de anagtwig de una cadena.

  • Counter toma un iterable y crea un mapeo que representa cuántas veces apareció cada elemento, por lo que
  • Counter(substring) crea una asignación que representa la clase de anagtwig de una cadena.
  • viewitems() proporciona una colección de pares de letras: contar, y
  • frozenset convierte eso en un conjunto inmutable que se puede usar como una tecla dict.

Estos pasos juntos toman un tiempo proporcional al tamaño de la subcadena; en promedio, las subcadenas son aproximadamente un tercio del tamaño de toda la cadena, por lo que en promedio, procesar cada subcadena lleva tiempo O(len(x)) . Existen subcadenas O(len(x)**2) , por lo que procesar todas las subcadenas lleva tiempo O(len(x)**3) .

Si hay x subcadenas con la misma clase de anagtwigs, se pueden emparejar en x*(x-1)/2 formas, de modo que la sum pase por el número de ocurrencias de cada clase de anagtwigs y calcule el número de pares. Esto lleva O(len(x)**2) tiempo, ya que tiene que pasar por cada clase de anagtwig una vez, y no puede haber más clases de anagtwigs que subcadenas.

En general, este algoritmo lleva O(len(x)**3) tiempo, lo cual no es excelente, pero es mucho mejor que el original. Todavía hay espacio para optimizar esto, por ejemplo, al calcular las clases de anagtwigs de manera que se aproveche la superposición entre las subcadenas o mediante el uso de una representación de clases de anagtwigs más eficiente.

No creo que pueda escapar por completo a las iteraciones de este problema, pero al menos puede hacer que la tarea en cuestión sea más pequeña por un factor de O (2 ^ nC2 / 2 ^ n).

Desea agrupar las subcadenas en sus respectivas longitudes antes de comenzar a iterar ya que está agregando muchos más casos para verificar.

El método actual compara todos los pares de un conjunto, lo que toma 2 ^ nC2 = comparaciones. Este es un número enorme (2^n)! / ((2^n-2)! * 2!) (2^n)! / ((2^n-2)! * 2!) .

Si primero hacemos una lista de subcadenas de 1-n de longitud y luego comparamos, gastamos:

  1. 2 ^ n operaciones pasando por todas las subcadenas.
  2. Operaciones nC2 pasando por subcadena de longitud 1.

Es decir, estamos logarítmicamente mejor.

Edición: Me di cuenta de que las cadenas no son conjuntos y las subcadenas no son subconjuntos, pero eso solo afecta el número de subconjuntos y no afecta el argumento principal.