python - 如何使这个 Python Scrabble 单词查找器变得更快？

Question

我没有真正需要改进它，这只是为了好玩。现在，在大约 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

Answer 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' 行分隔符。此外，列表中的最后一个单词可能有问题，因为它的末尾可能没有新行，但在我的计算机上，最后一个单词是 études，无论如何我们的方法都找不到。当然，您可以事先从原始字典中创建自己的字典，删除那些无效的字典:那些长度不正确或字母超出 a-z 的字典。

接下来，Ferran 为机架组建议了一个变量，这是个好主意。但是，从每个单词中制作一个集合，你也得到了相当大的减速。完全使用这些装置的目的是清除许多根本没有任何镜头的装置，从而加快速度。但是，我发现在调用可拼写之前检查单词的第一个字母是否在机架中会更快:

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

然后我可以只取机架字母的组合，然后在 anagram 字典中对每个字母进行二分搜索，看看是否有匹配项。对于 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 倍。此外，加载字典的启动时间比实际从机架中搜索单词的时间要长得多，因此这是一次进行多个搜索的更好方法。