¿Cómo se puede hacer este buscador de palabras de Scrabble en Python más rápido?

No tengo una necesidad real de mejorarlo, es solo por diversión. En este momento se está demorando un segundo en una lista de aproximadamente 200 mil palabras.

He intentado optimizarlo tanto como sé (el uso de generadores en lugar de la comprensión de listas hizo una gran diferencia), y me he quedado sin ideas.

¿Usted tiene alguna?

#!/usr/bin/env python # let's cheat at scrabble def count_letters(word): count = {} for letter in word: if letter not in count: count[letter] = 0 count[letter] += 1 return count def spellable(word, rack): word_count = count_letters(word) rack_count = count_letters(rack) return all( [word_count[letter] <= rack_count[letter] for letter in word] ) score = {"a": 1, "c": 3, "b": 3, "e": 1, "d": 2, "g": 2, "f": 4, "i": 1, "h": 4, "k": 5, "j": 8, "m": 3, "l": 1, "o": 1, "n": 1, "q": 10, "p": 3, "s": 1, "r": 1, "u": 1, "t": 1, "w": 4, "v": 4, "y": 4, "x": 8, "z": 10} def score_word(word): return sum([score[c] for c in word]) def word_reader(filename): # returns an iterator return (word.strip() for word in open(filename)) if __name__ == "__main__": import sys if len(sys.argv) == 2: rack = sys.argv[1].strip() else: print """Usage: python cheat_at_scrabble.py """ exit() words = word_reader('/usr/share/dict/words') scored = ((score_word(word), word) for word in words if set(word).issubset(set(rack)) and len(word) > 1 and spellable(word, rack)) for score, word in sorted(scored): print str(score), '\t', word 

Sin ir demasiado lejos de su código básico, aquí hay algunas optimizaciones bastante simples:

Primero, cambia tu lector de palabras para que sea:

 def word_reader(filename, L): L2 = L+2 # returns an iterator return (word.strip() for word in open(filename) \ if len(word) < L2 and len(word) > 2) 

y llamalo como

 words = word_reader('/usr/share/dict/words', len(rack)) 

Esto da la mayor mejora de todos mis cambios sugeridos. Elimina las palabras que son demasiado largas o cortas antes de llegar demasiado lejos en el proceso. Recuerda que en mis comparaciones la word tiene caracteres de nueva línea. Asumí ‘\ n’ separadores de línea. Además, podría haber un problema con la última palabra en la lista porque probablemente no tendrá una nueva línea al final, pero en mi computadora la última palabra es études que no se encontrará con nuestro método de todos modos. Por supuesto, puede crear su propio diccionario de antemano a partir del original que elimina aquellos que no son válidos: aquellos que no tienen la longitud correcta o tienen letras de tamaño demasiado grande.

A continuación, Ferran sugirió una variable para el conjunto de bastidores, lo cual es una buena idea. Sin embargo, también está disminuyendo su velocidad al hacer un conjunto de cada palabra. El propósito de usar los sets fue eliminar a muchos de los que no tienen ninguna inyección y, por lo tanto, acelerarlos. Sin embargo, descubrí que era incluso más rápido comprobar si la primera letra de la palabra estaba en el estante antes de llamar a la etiqueta:

 rackset = frozenset(rack) scored = [(score_word(word), word) for word in words if word[0] in rackset \ and spellable(word, rack)] 

Sin embargo, esto tiene que ir acompañado de un cambio a spellable. Lo cambié a lo siguiente:

 def spellable(word, rack): return all( [rack.count(letter) >= word.count(letter) \ for letter in set(word)] ) 

lo cual, incluso sin los cambios en el paso anterior, es más rápido que el que tiene actualmente.

Con los tres cambios anteriores, el código fue 3 veces más rápido que con mis pruebas simples.

A un mejor algoritmo

Ya que lo que realmente estás haciendo es buscar anagtwigs, tiene sentido usar un diccionario de anagtwigs. Un diccionario de anagtwigs toma cada palabra de un diccionario y las agrupa si son anagtwigs. Por ejemplo, ‘take’ y ‘skate’ son anagtwigs entre sí porque ambos son iguales a ‘aekst’ cuando están ordenados. Creé un diccionario de anagtwigs como un archivo de texto con el formato donde en cada línea constituye una entrada. Cada entrada tiene la versión ordenada de la versión ordenada de los anagtwigs y luego los propios anagtwigs. Para el ejemplo que estoy usando la entrada sería

 aekst skate takes 

Luego, solo puedo tomar combinaciones de las letras del estante y hacer una búsqueda binaria para cada una en el diccionario de anagtwigs para ver si hay una coincidencia. Para un rack de 7 letras, hay un máximo de 120 combinaciones únicas de letras válidas para scrabble. Realizar una búsqueda binaria es O (log (N)), por lo que será muy rápido.

Implementé el algoritmo en dos partes. El primero hace el diccionario de anagtwigs y el segundo es el progtwig real de scrabble.

Código creador del diccionario anagtwig

 f = open('/usr/share/dict/words') d = {} lets = set('abcdefghijklmnopqrstuvwxyz\n') for word in f: if len(set(word) - lets) == 0 and len(word) > 2 and len(word) < 9: word = word.strip() key = ''.join(sorted(word)) if key in d: d[key].append(word) else: d[key] = [word] f.close() anadict = [' '.join([key]+value) for key, value in d.iteritems()] anadict.sort() f = open('anadict.txt','w') f.write('\n'.join(anadict)) f.close() 

Código de engaño de Scrabble

 from bisect import bisect_left from itertools import combinations from time import time def loadvars(): f = open('anadict.txt','r') anadict = f.read().split('\n') f.close() return anadict scores = {"a": 1, "c": 3, "b": 3, "e": 1, "d": 2, "g": 2, "f": 4, "i": 1, "h": 4, "k": 5, "j": 8, "m": 3, "l": 1, "o": 1, "n": 1, "q": 10, "p": 3, "s": 1, "r": 1, "u": 1, "t": 1, "w": 4, "v": 4, "y": 4, "x": 8, "z": 10} def score_word(word): return sum([scores[c] for c in word]) def findwords(rack, anadict): rack = ''.join(sorted(rack)) foundwords = [] for i in xrange(2,len(rack)+1): for comb in combinations(rack,i): ana = ''.join(comb) j = bisect_left(anadict, ana) if j == len(anadict): continue words = anadict[j].split() if words[0] == ana: foundwords.extend(words[1:]) return foundwords if __name__ == "__main__": import sys if len(sys.argv) == 2: rack = sys.argv[1].strip() else: print """Usage: python cheat_at_scrabble.py """ exit() t = time() anadict = loadvars() print "Dictionary loading time:",(time()-t) t = time() foundwords = set(findwords(rack, anadict)) scored = [(score_word(word), word) for word in foundwords] scored.sort() for score, word in scored: print "%d\t%s" % (score,word) print "Time elapsed:", (time()-t) 

El creador del diccionario de anagtwigs lleva aproximadamente medio segundo en mi máquina. Cuando el diccionario ya está creado, ejecutar el progtwig de engaño de scrabble es aproximadamente 15 veces más rápido que el código del OP y 5 veces más rápido que el código del OP después de los cambios mencionados anteriormente. Además, el tiempo de inicio de la carga del diccionario es mucho mayor que la búsqueda de palabras en un rack, por lo que esta es una forma mucho mejor de realizar varias búsquedas a la vez.

Puede utilizar el hecho de que el diccionario / usr / dict / share / words está ordenado para permitirle omitir muchas palabras en el diccionario sin tener en cuenta en absoluto.

Por ejemplo, suponga que una palabra del diccionario comienza con “A” y no tiene “A” en el bastidor. Puede hacer una búsqueda binaria en la lista de palabras para la primera palabra que comienza con una “B” y omitir todas las palabras intermedias. Esto marcará una gran diferencia en la mayoría de los casos: omitirás quizás la mitad de las palabras.

 import trie def walk_trie(trie_node, rack, path=""): if trie_node.value is None: yield path for i in xrange(len(rack)): sub_rack = rack[:i] + rack[i+1:] if trie_node.nodes.has_key(rack[i]): for word in walk_trie(trie_node.nodes[rack[i]], sub_rack, path+rack[i]): yield word if __name__ == "__main__": print "Generating trie... " # You might choose to skip words starting with a capital # rather than lower-casing and searching everything. Capitalised # words are probably pronouns which aren't allowed in Scrabble # I've skipped words shorter than 3 characters. all_words = ((line.strip().lower(), None) for line in open("/usr/share/dict/words") if len(line.strip()) >= 3) word_trie = trie.Trie(mapping=all_words) print "Walking Trie... " print list(walk_trie(word_trie.root, "abcdefg")) 

Generar el trie toma un poco de tiempo, pero una vez generado, obtener la lista de palabras debe ser mucho más rápido que recorrer una lista.

Si alguien sabe una manera de serializar un trie sería una gran adición.

Solo para demostrar que generar el trie es lo que lleva su tiempo …

  ncalls tottime percall cumtime percall filename:lineno(function) 98333 5.344 0.000 8.694 0.000 trie.py:87(__setitem__) 832722 1.849 0.000 1.849 0.000 trie.py:10(__init__) 832721 1.501 0.000 1.501 0.000 {method 'setdefault' of 'dict' objects} 98334 1.005 0.000 1.730 0.000 scrabble.py:16() 1 0.491 0.491 10.915 10.915 trie.py:82(extend) 196902 0.366 0.000 0.366 0.000 {method 'strip' of 'str' objects} 98333 0.183 0.000 0.183 0.000 {method 'lower' of 'str' objects} 98707 0.177 0.000 0.177 0.000 {len} 285/33 0.003 0.000 0.004 0.000 scrabble.py:4(walk_trie) 545 0.001 0.000 0.001 0.000 {method 'has_key' of 'dict' objects} 1 0.001 0.001 10.921 10.921 {execfile} 1 0.001 0.001 10.920 10.920 scrabble.py:1() 1 0.000 0.000 0.000 0.000 trie.py:1() 1 0.000 0.000 0.000 0.000 {open} 1 0.000 0.000 0.000 0.000 trie.py:5(Node) 1 0.000 0.000 10.915 10.915 trie.py:72(__init__) 1 0.000 0.000 0.000 0.000 trie.py:33(Trie) 1 0.000 0.000 10.921 10.921 :1() 1 0.000 0.000 0.000 0.000 {method 'split' of 'str' objects} 1 0.000 0.000 0.000 0.000 trie.py:1(NeedMore) 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 

Puedes convertir más listas a generadores:

 all( [word_count[letter] <= rack_count[letter] for letter in word] ) ... sum([score[c] for c in word]) 

a

 all( word_count[letter] <= rack_count[letter] for letter in word ) ... sum( score[c] for c in word ) 

En el bucle, en lugar de crear el conjunto rask en cada iteración, puede crearlo de antemano y puede ser un conjunto de archivos.

 rack_set = frozenset(rack) scored = ((score_word(word), word) for word in words if set(word).issubset(rask_set) and len(word) > 1 and spellable(word, rack)) 

Lo mismo se puede hacer con el diccionario rack_count. No es necesario crearlo en cada iteración.

 rack_count = count_letters(rack) 

Organiza tus datos mejor . En lugar de leer a través de un diccionario lineal y comparar, puede pre-construir una estructura de árbol con esos vectores de conteo de letras (bien, “vectores”), y guardarla en un archivo.