如何提升这个Python拼字游戏单词查找器的速度?
我其实没什么必要去改进它,只是为了好玩。目前在处理大约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
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"))
生成这个字典树(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}
你可以利用/usr/dict/share/words这个字典是排好序的这个特点,来跳过很多字典里的单词,而根本不需要考虑它们。
举个例子,假设字典里的一个单词是以"A"开头的,但你手里没有"A"这个字母。你可以在单词列表中进行二分查找,找到第一个以"B"开头的单词,这样就可以跳过中间所有以"A"开头的单词。这在大多数情况下会有很大的帮助——你可能会跳过一半的单词。
在不改变你基本代码的情况下,这里有一些相对简单的优化建议:
首先,把你的单词读取器改成:
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'作为行分隔符。此外,列表中的最后一个单词可能会有问题,因为它可能没有换行符在后面,但在我的电脑上,最后一个单词是études,而我们的方式也找不到它。当然,你可以提前从原始数据中创建自己的字典,去掉那些不合法的单词:比如长度不对或者包含不在a-z范围内的字母。
接下来,Ferran建议为字母架设置一个变量,这个主意不错。不过,你在每次从每个单词创建集合时也会导致明显的速度下降。使用集合的目的就是为了排除那些根本没有机会的单词,从而提高速度。然而,我发现直接检查单词的第一个字母是否在字母架中比调用spellable更快:
rackset = frozenset(rack)
scored = [(score_word(word), word) for word in words if word[0] in rackset \
and spellable(word, rack)]
不过,这需要对spellable进行一些改动。我把它改成了:
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)),所以这个过程会非常快。
我把这个算法分成了两个部分。第一部分是创建字谜字典,第二部分是实际的拼字作弊程序。
字谜字典创建代码
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)
字谜字典创建在我的机器上大约需要半秒钟。当字典已经创建好后,运行拼字作弊程序的速度大约是15倍于原始代码,且比我之前提到的改动后的代码快5倍。此外,加载字典的启动时间远大于从字母架中搜索单词的时间,所以这种方法在进行多次搜索时要好得多。