Cómo optimizar el código Python (de ThinkPython, el ejercicio 10.10)

Question

estoy trabajando a través de Allen Downey Cómo Pensar como un Informático, y he escrito lo que yo creo que es una solución funcionalmente correcta al ejercicio 10.10 . Pero me llevó algo más de 10 horas (!) Ejecutar, así que me pregunto si me falta algo de optimización realmente obvia y útil.

Aquí está el ejercicio:..

" 'enclavamiento' Dos palabras si tomar cartas alternando de cada uno forma una nueva palabra Por ejemplo, 'zapato' y el enclavamiento de 'frío' para formar 'educado' Escribir un programa que encuentra todos los pares de palabras que se entrelazan. Sugerencia: ¡No enumere todos los pares! "

(.. Para estos problemas lista de palabras, Downey ha suministrado un archivo con 113809 palabras Podemos suponer que estas palabras están en una lista, una palabra por elemento de la lista)

aquí está mi solución:

from bisect import bisect_left 

def index(lst, target): 
    """If target is in list, returns the index of target; otherwise returns None""" 
    i = bisect_left(lst, target) 
    if i != len(lst) and lst[i] == target: 
     return i 
    else: 
     return None 

def interlock(str1, str2): 
    "Takes two strings of equal length and 'interlocks' them." 
    if len(str1) == len(str2): 
     lst1 = list(str1) 
     lst2 = list(str2) 
     result = [] 
     for i in range(len(lst1)): 
      result.append(lst1[i]) 
      result.append(lst2[i]) 
     return ''.join(result) 
    else: 
     return None 

def interlockings(word_lst): 
    """Checks each pair of equal-length words to see if their interlocking is a word; prints each successful pair and the total number of successful pairs.""" 
    total = 0 
    for i in range(1, 12): # 12 because max word length is 22 
     # to shorten the loops, get a sublist of words of equal length 
     sub_lst = filter(lambda(x): len(x) == i, word_lst) 
     for word1 in sub_lst[:-1]: 
      for word2 in sub_lst[sub_lst.index(word1)+1:]: # pair word1 only with words that come after word1 
       word1word2 = interlock(word1, word2) # interlock word1 with word2 
       word2word1 = interlock(word2, word1) # interlock word2 with word1 
       if index(lst, word1word2): # check to see if word1word2 is actually a word 
        total += 1 
        print "Word 1: %s, Word 2: %s, Interlock: %s" % (word1, word2, word1word2) 
       if index(lst, word2word1): # check to see if word2word1 is actually a word 
        total += 1 
        print "Word 2, %s, Word 1: %s, Interlock: %s" % (word2, word1, word2word1) 
    print "Total interlockings: ", total 

Las declaraciones de impresión no son el problema; mi programa encontró solo 652 de esos pares. El problema son los bucles anidados, ¿verdad? Quiero decir, aunque estoy revisando listas que contienen solo palabras de la misma longitud, hay (por ejemplo) 21727 palabras de longitud 7, lo que significa que mi programa debe verificar más de 400 millones de "enclavamientos" para ver si ' re palabras reales --- y eso es solo para la longitud-7 palabras.

De nuevo, este código tardó 10 horas en ejecutarse (y no encontró pares con palabras de longitud 5 o superior, en caso de que tuviera curiosidad). ¿Hay una mejor manera de resolver este problema?

Gracias de antemano por cualquier idea. Soy consciente de que "la optimización prematura es la raíz de todo mal" --- y quizás ya he caído en esa trampa --- pero en general, aunque normalmente puedo escribir código que se ejecuta correctamente, a menudo me cuesta escribir código que funciona bien

Answer 1

Hazlo al revés: itera por todas las palabras y divídelas en dos palabras tomando las letras pares e impares. Luego busca esas dos palabras en el diccionario.

Como un nodo lado, las dos palabras que enclavamiento no debe necesariamente tener la misma longitud - las longitudes también podría diferir en 1.

Algunos (no probado) código:

words = set(line.strip() for line in open("words")) 
for w in words: 
    even, odd = w[::2], w[1::2] 
    if even in words and odd in words: 
     print even, odd 

Answer 2

definición Alternativa de enclavamiento:

import itertools 

def interlock(str1, str2): 
    "Takes two strings of equal length and 'interlocks' them." 
    return ''.join(itertools.chain(*zip(str1, str2))) 

Answer 3

Una cosa importante es su función index: es la función que se ejecuta más de una función. Cuando no necesita el índice de la palabra encontrada, ¿por qué definir una función para encontrar ese índice?

if word1word2 in lst: es suficiente en lugar de if index(lst, word1word2):.

Lo mismo para if index(lst, word2word1):.

OK. la bisección funciona realmente más rápido que la sintaxis in. Para mejorar un poco más la velocidad, sugiero usar la función bisect_left directamente en su función interlockings.

Por ejemplo en lugar de:

 if index(lst, word1word2): # check to see if word1word2 is actually a word 
      total += 1 
      print "Word 1: %s, Word 2: %s, Interlock: %s" % (word1, word2, word1word2) 

Uso:

 q = bisect_left(lst, word1word2) 
     if q != len(lst) and lst[q] == word1word2: 
      total += 1 
      print "Word 1: %s, Word 2: %s, Interlock: %s" % (word1, word2, word1word2) 

una muy ligera mejora en la velocidad.

Answer 4

Una versión alternativa:

with open('words.txt') as inf: 
    words = set(wd.strip() for wd in inf) 

word_gen = ((word, word[::2], word[1::2]) for word in words) 
interlocked = [word for word,a,b in word_gen if a in words and b in words] 

En mi máquina esta se ejecuta en 0.16 segundos y devuelve 1254 palabras.

---

Editar: como señaló @ John Machin en Why is this program faster in Python than Objective-C? Esto se puede mejorar aún más por la ejecución perezoso (sólo realizan la segunda rebanada si los primeros resultados en una palabra válida):

with open('words.txt') as inf: 
    words = set(wd.strip() for wd in inf) 
interlocked = [word for word in words if word[::2] in words and word[1::2] in words] 

Esto reduce el tiempo de ejecución en un tercio, a 0.104 segundos.