Как сделать этот инструмент поиска слов Python Scrabble быстрее?

Не заходя слишком далеко от вашего базового кода, вот несколько довольно простых оптимизаций:

Во-первых, измените ваш читатель слова как:

 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». Кроме того, может возникнуть проблема с последним словом в списке, потому что у него, вероятно, не будет новой строки в конце, но на моем компьютере последнее слово – это те, которые в любом случае не будут найдены с помощью нашего метода. Конечно, вы могли бы просто создать свой собственный словарь заранее из оригинала, который удаляет те, которые недействительны: те, которые не имеют правильной длины или имеют буквы, не относящиеся к az.

Затем Ферран предложил переменную для набора стойки, что является хорошей идеей. Тем не менее, вы также получаете довольно значительное замедление от создания набора из каждого слова. Цель использования комплектов заключалась в том, чтобы отсеять многие из тех, у кого вообще нет никакого выстрела, и тем самым ускорить процесс. Тем не менее, я обнаружил, что было еще быстрее просто проверить, была ли первая буква слова в стойке, прежде чем называть заклинание:

 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 обманывающий код

 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 примерно на 15 раз быстрее, чем код OP и в 5 раз быстрее, чем код OP после моих вышеупомянутых изменений. Кроме того, время загрузки словаря намного больше, чем поиск слов из стойки, поэтому это гораздо лучший способ для выполнения нескольких поисков одновременно.

Вы можете использовать тот факт, что словарь / usr / dict / share / words отсортирован, чтобы вы могли пропустить много слов в словаре, не считая их вообще.

Например, слова словаря начинаются с «А», и у вас нет «А» в стойке. Вы можете выполнить двоичный поиск в списке слов для первого слова, начинающегося с буквы «B», и пропустить все слова между ними. В большинстве случаев это будет иметь большое значение – вы пропустите половину слов.

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

Генерирование trie занимает немного времени, но после создания списка слов должно быть намного быстрее, чем цикл по списку.

Если кто-то знает способ сериализации trie, который станет отличным дополнением.

Просто продемонстрировать, что генерация trie – это то, что занимает время …

  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} 

вы можете конвертировать больше списков в генераторы:

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

в

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

В цикле вместо создания набора расов на каждой итерации вы можете создать его заранее, и это может быть фризонсет.

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

То же самое можно сделать с помощью словаря rack_count. Его не нужно создавать на каждой итерации.

 rack_count = count_letters(rack) 

Организуйте свои данные лучше . Вместо того, чтобы читать линейный словарь и сравнивать его, вы можете предварительно построить древовидную структуру с векторами векторов (ну, «векторы») и сохранить их в файле.