我没有真正需要改进它，只是为了好玩。现在，在大约 20 万个单词的列表上大约需要一秒钟。
我已经尽我所能地尝试优化它（使用生成器而不是列表理解产生了很大的不同），但我已经没有想法了。
你有吗？
#!/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
在不脱离基本代码的情况下，这里有一些相当简单的优化：
首先，将您的文字阅读器更改为：
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接下来，费兰建议为机架设置一个变量，这是一个好主意。然而，从每个单词中创建一个集合也会显着减慢你的速度。使用这些集合的目的是为了淘汰许多根本没有任何镜头的集合，从而提高速度。然而，我发现在调用可拼写之前检查单词的第一个字母是否在机架中甚至更快：
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 倍。
更好的算法
由于您真正要做的是寻找字谜词，因此使用字谜词词典是有意义的。字谜词典采用字典中的每个单词，如果它们是字谜词，则将它们分组。例如，“takes”和“skate”是彼此的字谜词，因为它们在排序时都等于“aekst”。我创建了一个字谜词典作为文本文件，其格式为每行构成一个条目。每个条目都有字谜排序版本的排序版本，然后是字谜本身。对于我正在使用的示例，该条目是
aekst skate takes
然后我可以采用机架字母的组合，并对字谜词典中的每个字母进行二分搜索，看看是否有匹配项。对于 7 个字母的机架，最多有 120 个独特的拼字游戏有效字母组合。执行二分查找的时间复杂度为 O(log(N))，因此速度会非常快。
我分两部分实现了该算法。第一个是制作字谜词典，第二个是实际的拼字游戏作弊程序。
Anagram 字典创建者代码
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()
拼字游戏作弊代码
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)
字谜词典创建器在我的机器上大约需要半秒。当字典已经创建时，运行拼字游戏作弊程序大约比 OP 的代码快 15 倍，比我上述更改后的 OP 代码快 5 倍。此外，加载词典的启动时间比实际从机架中搜索单词的时间要长得多，因此这是一次进行多个搜索的更好方法。
您可以利用 /usr/dict/share/words 字典已排序的事实来允许您跳过字典中的许多单词而根本不考虑它们。
例如，假设字典中的单词以“A”开头，而您的机架中没有“A”。您可以在单词列表中进行二分搜索，查找以“B”开头的第一个单词，并跳过中间的所有单词。在大多数情况下，这会产生巨大的差异 - 你可能会跳过一半的单词。
生成特里树需要一点时间，但是一旦生成，获取单词列表应该比循环列表快得多。
如果有人知道序列化 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 )
在循环中，不用每次迭代都创建rask集，而是可以提前创建，并且它可以是frozenset。
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)
。您可以使用这些字母计数向量（好吧，“向量”）预先构建一个树结构，并将其保存到文件中，而不是阅读线性字典并进行比较。