<p>在不过分偏离基本代码的情况下,下面是一些相当简单的优化:</p>
<p>首先,将你的单词阅读器改为:</p>
<pre><code>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)
</code></pre>
<p>并称之为</p>
<pre><code>words = word_reader('/usr/share/dict/words', len(rack))
</code></pre>
<p>这是我所建议的所有更改中最大的改进。它消除了在我们在这个过程中走得太远之前太长或太短的单词。请记住,在我的比较中,<code>word</code>是未压缩的新行字符。我假设是“\n”行分隔符。另外,列表中的最后一个单词可能有问题,因为它的结尾可能没有新行,但在我的计算机上,最后一个单词是词组,无论如何我们的方法都找不到。当然,你可以事先创建自己的字典,从原始字典中删除那些无效的:那些长度不对或字母大小超过a-z的字典</p>
<p>接下来,费兰提出了一个机架设置变量,这是一个好主意。然而,你也会在每一个单词的编排上慢下来。使用这些镜头的目的是为了剔除很多根本没有镜头的镜头,从而加快拍摄速度。不过,我发现,在调用可拼写之前,检查单词的第一个字母是否在机架中更快:</p>
<pre><code>rackset = frozenset(rack)
scored = [(score_word(word), word) for word in words if word[0] in rackset \
and spellable(word, rack)]
</code></pre>
<p>然而,这必须伴随着拼写的改变。我改为:</p>
<pre><code>def spellable(word, rack):
return all( [rack.count(letter) >= word.count(letter) \
for letter in set(word)] )
</code></pre>
<p>即使没有上一步的改变,也比你现在拥有的要快。</p>
<p>通过上面的三个修改,代码比我的简单测试快了大约3倍。</p>
<p><strong>使用更好的算法</p>
<p>因为你真正要做的是寻找字谜,所以使用字谜字典是有意义的。一本字谜字典把字典里的每个字都取出来,如果它们是字谜,就把它们分组。例如,“takes”和“skate”是彼此的anagrams,因为它们在排序时都等于“aekst”。我创建了一个anagram字典作为一个文本文件,其格式是每行组成一个条目。每个条目都有排序版本的anagrams,然后是anagrams本身。例如我使用的条目</p>
<pre><code>aekst skate takes
</code></pre>
<p>然后我就可以把这些字母组合起来,在anagram字典中对每一个字母进行二进制搜索,看看是否匹配。对于7个字母的机架,最多有120个字母的唯一拼字有效组合。执行二进制搜索是O(log(N))所以速度非常快。</p>
<p>我分两部分实现了算法。第一个是拼字词典,第二个是真正的拼字作弊程序。</p>
<p><strong>Anagram字典创建者代码</strong></p>
<pre><code>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()
</code></pre>
<p><strong>拼字作弊代码</strong></p>
<pre><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)
</code></pre>
<p>在我的机器上,造字法词典的创作者花了大约半秒钟的时间。当字典已经创建好时,运行scrabble作弊程序比OP的代码快15倍,比OP的代码快5倍。此外,加载字典的启动时间比从机架中实际搜索单词的时间要长得多,因此这是同时执行多个搜索的更好方法。</p>