Profiling muestra que este es el segmento más lento de mi código para un pequeño juego de palabras que escribí:

def distance(word1, word2):
    difference = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            difference += 1
    return difference

def getchildren(word, wordlist):
    return [ w for w in wordlist if distance(word, w) == 1 ]

Notas:

distance() se llama más de 5 millones de veces, la mayoría de las cuales proviene de getchildren, que se supone que debe obtener todas las palabras en la lista de palabras que difieren deword por exactamente 1 letra.wordlist se filtra previamente para tener solo palabras que contengan la misma cantidad de letras queword así que está garantizado queword1 yword2 tienen el mismo número de caracteres. Soy bastante nuevo en Python (comencé a aprenderlo hace 3 días), así que también agradezco los comentarios sobre convenciones de nombres u otras cosas de estilo.para la lista de palabras, tome la 12dict lista de palabras utilizando el archivo "2 + 2lemma.txt"

Resultados:

Gracias a todos, con combinaciones de diferentes sugerencias, puse el programa funcionando dos veces más rápido ahora (además de las optimizaciones que hice por mi cuenta antes de preguntar, por lo que 4 veces la velocidad aumenta aproximadamente desde mi implementación inicial)

Probé con 2 conjuntos de entradas que llamaré A y B

Optimización1: iterar sobre los índices de word1,2 ... desd

for i in range(len(word1)):
        if word1[i] != word2[i]:
            difference += 1
    return difference

aiterate en pares de letras usandozip(word1, word2)

for x,y in zip (word1, word2):
        if x != y:
            difference += 1
    return difference

Tengo tiempo de ejecución de 11.92 a 9.18 para la entrada A, y de 79.30 a 74.59 para la entrada B

Optimización2: se agregó un método separado para diferir por uno además del método de distancia (que todavía necesitaba en otro lugar para la heurística A *)

def is_neighbors(word1,word2):
    different = False
    for c1,c2 in zip(word1,word2):
        if c1 != c2:
            if different:
                return False
            different = True
    return different

Tengo tiempo de ejecución de 9.18 a 8.83 para la entrada A, y de 74.59 a 70.14 para la entrada B

Optimización3: El gran ganador aquí fue usarizip en lugar dezip

Tengo tiempo de ejecución de 8.83 a 5.02 para la entrada A, y de 70.14 a 41.69 para la entrada B

Probablemente podría hacerlo mejor escribiendo en un idioma de nivel inferior, pero estoy contento con esto por ahora. ¡Gracias a todos

Edit nuevamente: más resultados El uso del método de Mark para verificar el caso donde la primera letra no coincide bajó de 5.02 -> 3.59 y 41.69 -> 29.82

onstruyendo sobre eso yincorporatingizip en lugar derange, Terminé con esto:

def is_neighbors(word1,word2):
    if word1[0] != word2[0]:
        return word1[1:] == word2[1:]
    different = False
    for x,y in izip(word1[1:],word2[1:]):
        if x != y:
            if different:
                return False
            different = True
    return different

Lo que apretó un poco más, bajando los tiempos de 3.59 -> 3.38 y 29.82 -> 27.88

¡Incluso más resultados!

Probar la sugerencia de Sumudu de que yogenere una lista de todas las cadenas que están a 1 letra de "word" y luego verifique cuáles estaban en la lista de palabras, en lugar de la función is_neighbor, terminé con esto:

def one_letter_off_strings(word):
    import string
    dif_list = []
    for i in xrange(len(word)):
        dif_list.extend((word[:i] + l + word[i+1:] for l in string.ascii_lowercase if l != word[i]))
    return dif_list

def getchildren(word, wordlist):
    oneoff = one_letter_off_strings(word)
    return ( w for w in oneoff if w in wordlist )

Lo que terminó siendo más lento (3.38 -> 3.74 y 27.88 -> 34.40) pero parecía prometedor. Al principio, pensé que la parte que necesitaba optimizar era "one_letter_off_strings", pero el perfil mostró lo contrario y que la parte lenta era, de hecho,

( w for w in oneoff if w in wordlist )

Pensé que habría alguna diferencia si cambiaba "oneoff" y "wordlist" e hiciera la comparación de la otra manera cuando me di cuenta de que estaba buscando la intersección de las 2 listas. Reemplazo eso con set-intersection en las letras:

return set(oneoff) & set(wordlist)

Bam! 3.74 -> 0.23 y 34.40 -> 2.25

Esto es realmente sorprendente, la diferencia de velocidad total con respecto a mi implementación ingenua original: 23.79 -> 0.23 y 180.07 -> 2.25, por lo tanto, aproximadamente 80 a 100 veces más rápido que la implementación original.

Si alguien está interesado, hice una publicación en el blogdescribiendo el programa ydescribiendo las optimizaciones hecho incluyendo uno que no se menciona aquí (porque está en una sección de código diferente).

El gran debate:

Ok, Desconocido y yo estamos teniendo un gran debate que puedes leer en los comentarios desu respuesta. Afirma que sería más rápido usar el método original (usar is_neighbor en lugar de usar los conjuntos) si se transfiriera a C. Intenté durante 2 horas obtener un módulo C que escribí para construir y ser enlazable sin mucho éxito después de intentar sigueest yest ejemplo, y parece que el proceso es un poco diferente en Windows? No lo sé, pero me di por vencido. De todos modos, aquí está el código completo del programa, y el archivo de texto proviene de 12dict lista de palabras utilizando el archivo "2 + 2lemma.txt". Lo siento si el código es un poco desordenado, esto fue algo que pirateé juntos. Además, olvidé eliminar las comas de la lista de palabras, por lo que en realidad es un error que puede dejar en aras de la misma comparación o solucionarlo agregando una coma a la lista de caracteres en las entradas de limpieza.

from itertools import izip
def unique(seq):  
    seen = {} 
    result = [] 
    for item in seq: 
        if item in seen:
            continue 
        seen[item] = 1 
        result.append(item) 
    return result
def cleanentries(li):
    pass
    return unique( [w.strip('[]') for w in li if w != "->"] )
def distance(word1, word2):
    difference = 0
    for x,y in izip (word1, word2):
        if x != y:
            difference += 1
    return difference
def is_neighbors(word1,word2):
    if word1[0] != word2[0]:
        return word1[1:] == word2[1:]
    different = False
    for x,y in izip(word1[1:],word2[1:]):
        if x != y:
            if different:
                return False
            different = True
    return different
def one_letter_off_strings(word):
    import string
    dif_list = []
    for i in xrange(len(word)):
        dif_list.extend((word[:i] + l + word[i+1:] for l in string.ascii_lowercase if l != word[i]))
    return dif_list

def getchildren(word, wordlist):
    oneoff = one_letter_off_strings(word)
    return set(oneoff) & set(wordlist)
def AStar(start, goal, wordlist):
    import Queue
    closedset = []
    openset = [start]
    pqueue = Queue.PriorityQueue(0)
    g_score = {start:0}         #Distance from start along optimal path.
    h_score = {start:distance(start, goal)}
    f_score = {start:h_score[start]}
    pqueue.put((f_score[start], start))
    parent_dict = {}
    while len(openset) > 0:
        x = pqueue.get(False)[1]
        if x == goal:
            return reconstruct_path(parent_dict,goal)
        openset.remove(x)
        closedset.append(x)
        sortedOpen = [(f_score[w], w, g_score[w], h_score[w]) for w in openset]
        sortedOpen.sort()
        for y in getchildren(x, wordlist):
            if y in closedset:
                continue
            temp_g_score = g_score[x] + 1
            temp_is_better = False
            appended = False
            if (not y in openset): 
                openset.append(y)
                appended = True
                h_score[y] = distance(y, goal)
                temp_is_better = True
            elif temp_g_score < g_score[y] :
                temp_is_better = True
            else :
                pass
            if temp_is_better:
                parent_dict[y] = x
                g_score[y] = temp_g_score
                f_score[y] = g_score[y] + h_score[y]
                if appended :
                    pqueue.put((f_score[y], y))
    return None


def reconstruct_path(parent_dict,node):
     if node in parent_dict.keys():
         p = reconstruct_path(parent_dict,parent_dict[node])
         p.append(node)
         return p
     else:
         return []        

wordfile = open("2+2lemma.txt")
wordlist = cleanentries(wordfile.read().split())
wordfile.close()
words = []
while True:
    userentry = raw_input("Hello, enter the 2 words to play with separated by a space:\n ")
    words = [w.lower() for w in userentry.split()]
    if(len(words) == 2 and len(words[0]) == len(words[1])):
        break
print "You selected %s and %s as your words" % (words[0], words[1])
wordlist = [ w for w in wordlist if len(words[0]) == len(w)]
answer = AStar(words[0], words[1], wordlist)
if answer != None:
    print "Minimum number of steps is %s" % (len(answer))
    reply = raw_input("Would you like the answer(y/n)? ")
    if(reply.lower() == "y"):
        answer.insert(0, words[0])
        print "\n".join(answer)
    else:
        print "Good luck!"
else:
    print "Sorry, there's no answer to yours"
reply = raw_input("Press enter to exit")

Dejé el método is_neighours aunque no se usa. Este es el método que se propone portar a C. Para usarlo, simplemente reemplace getchildren con esto:

def getchildren(word, wordlist):
    return ( w for w in wordlist if is_neighbors(word, w))

En cuanto a que funcione como un módulo C, no llegué tan lejos, pero esto es lo que se me ocurrió:

#include "Python.h"

static PyObject *
py_is_neighbor(PyObject *self, Pyobject *args)
{
    int length;
    const char *word1, *word2;
    if (!PyArg_ParseTuple(args, "ss", &word1, &word2, &length))
        return NULL;

    int i;
    int different = 0;
    for (i =0; i < length; i++)
    {
        if (*(word1 + i) != *(word2 + i))
        {
            if (different)
            {
                return Py_BuildValue("i", different);
            }
            different = 1;
        }
    }
    return Py_BuildValue("i", different);
}

PyMethodDef methods[] = {
    {"isneighbor", py_is_neighbor, METH_VARARGS, "Returns whether words are neighbors"},
    {NULL, NULL, 0, NULL}
};

PyMODINIT_FUNC
initIsNeighbor(void)
{
    Py_InitModule("isneighbor", methods);
}

Perfilé esto usando:

python -m cProfile "Wordgame.py"

Y el tiempo registrado fue el tiempo total de la llamada al método AStar. El conjunto de entrada rápida fue "poetas versos" y el conjunto de entrada largo fue "versos poetas". Los tiempos obviamente variarán entre las diferentes máquinas, por lo que si alguien termina probando esto, obtendrá una comparación de resultados del programa tal como es, así como con el módulo C.