Ответ 1
Не заходя слишком далеко от вашего базового кода, вот несколько довольно простых оптимизаций:
Во-первых, измените ваш читатель слов следующим образом:
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)
и назовите его
words = word_reader('/usr/share/dict/words', len(rack))
Это дает самое большое улучшение всех моих предложенных изменений. Он устраняет слишком длинные или короткие слова, прежде чем мы заберем слишком далеко. Помните, что word не содержит новых символов строки в моих сравнениях. Я предположил разделители строк "\n". Кроме того, может возникнуть проблема с последним словом в списке, потому что у него, вероятно, не будет новой строки в конце, но на моем компьютере последнее слово - это те, которые в любом случае не будут найдены с помощью нашего метода. Конечно, вы могли бы просто создать свой собственный словарь заранее из оригинала, который удаляет те, которые не являются допустимыми: те, которые не соответствуют длине или имеют буквы, превышающие a-z.
Затем Ферран предложил переменную для набора стойки, что является хорошей идеей. Тем не менее, вы также получаете довольно значительное замедление от создания набора из каждого слова. Цель использования комплектов заключалась в том, чтобы отсеять многие из тех, у кого вообще нет никакого выстрела, и тем самым ускорить процесс. Тем не менее, я обнаружил, что было еще быстрее проверить, была ли первая буква слова в стойке, прежде чем называть заклинание:
rackset = frozenset(rack)
scored = [(score_word(word), word) for word in words if word[0] in rackset \
and spellable(word, rack)]
Однако это должно сопровождаться изменением на заклинание. Я изменил его на следующее:
def spellable(word, rack):
return all( [rack.count(letter) >= word.count(letter) \
for letter in set(word)] )
который даже без изменений на предыдущем шаге быстрее, чем у вас в настоящее время.
С тремя приведенными выше изменениями код был примерно в 3 раза быстрее моих простых тестов.
На лучший алгоритм
Поскольку то, что вы действительно делаете, ищет анаграммы, имеет смысл использовать словарь анаграмм. Словарь анаграммы принимает каждое слово в словаре и группирует их, если они являются анаграммами. Например, "принимает" и "конь" - это анаграммы друг друга, потому что при сортировке они равны "aekst". Я создал словарь анаграмм в виде текстового файла с форматом, который на каждой строке составляет запись. Каждая запись имеет отсортированную версию отсортированной версии анаграмм, а затем самих анаграмм. Для примера я использую запись будет
aekst skate takes
Затем я могу просто взять комбинации букв в стойке и выполнить двоичный поиск каждого из них в словаре анаграмм, чтобы узнать, есть ли совпадение. Для 7-буквенной стойки существует не более 120 уникальных комбинаций букв. Выполнение двоичного поиска - O (log (N)), поэтому это будет очень быстро.
Я реализовал алгоритм в двух частях. Первый делает словарь анаграмм, а второй - реальной программой обмана.
Код создателя словаря анаграмм
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()
Scrabble cheating code
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)
Создатель словаря анаграмм занимает около полутора секунд на моей машине. Когда словарь уже создан, запуск программы scrabble cheating примерно 15x быстрее, чем код OP, и в 5 раз быстрее, чем OP-код после моих вышеупомянутых изменений. Кроме того, время загрузки словаря намного больше, чем на самом деле поиск слов из стойки, поэтому это намного лучший способ для выполнения нескольких поисков одновременно.