python - que - mezclador de palabras

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

Question

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é (usar una generación de generadores en lugar de comprensión 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 <yourrack>"""
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

Answer 1

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 hará una gran diferencia en la mayoría de los casos, ya que omitirá la mitad de las palabras.

Answer 2

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)

Answer 3

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, acelerar. 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 spellable:

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 lo 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 anagramas, tiene sentido usar un diccionario de anagramas. Un diccionario de anagramas toma cada palabra de un diccionario y las agrupa si son anagramas. Por ejemplo, ''take'' y ''skate'' son anagramas entre sí porque ambos son iguales a ''aekst'' cuando están ordenados. Creé un diccionario de anagramas 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 anagramas y luego los mismos anagramas. 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 anagramas 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 anagramas y el segundo es el programa real de scrabble.

Código creador del diccionario anagrama

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()

Codigo scrabble trampa

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 <yourrack>"""
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 anagramas toma alrededor de medio segundo en mi máquina. Cuando el diccionario ya está creado, ejecutar el programa de trampas 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.

Answer 4

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 (bueno, "vectores"), y guardarla en un archivo.

Answer 5

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 debería 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 el 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(<genexpr>)
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(<module>)
1 0.000 0.000 0.000 0.000 trie.py:1(<module>)
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 <string>:1(<module>)
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}