Python-代码优化帮助 - 查找字

Question

我解决了使用这个（效率极其低下的方法）问题的所有字典，有效字谜游戏：

def createList(word, wordList): 
    #Made a set, because for some reason permutations was returning duplicates. 
    #Returns all permutations if they're in the wordList 

    return set([''.join(item) for item in itertools.permutations(word) if ''.join(item) in wordList]) 

def main(): 

    a = open('C:\\Python32\\megalist.txt', 'r+') 
    wordList = [line.strip() for line in a] 
    maximum = 0 
    length = 0 
    maxwords = "" 

    for words in wordList: 
     permList = createList(words, wordList) 
     length = len(permList) 
     if length > maximum: 
      maximum = length 
      maxwords = permList 
    print (maximum, maxwords) 

花了类似10分钟，发现五个字母的单词这是字典有效的字典。我想用没有字母限制的单词来运行它，但需要花费大量的时间。无论如何要优化这个吗？

Answer 1

对于一本小字典，这下面的工作似乎可行。通过对单词中的字母进行排序，可以轻松测试两个单词是否是一个字谜。从这个出发点来看，这只是一个以某种方式积累话语的问题。如果您确实需要在字母数量上添加约束条件，那么使用迭代器可以很方便地过滤掉某些字词。

def wordIterator(dictionaryFilename): 
    with open(dictionaryFilename,'r') as f: 
     for line in f: 
      word = line.strip() 
      yield word 

def largestAnagram(words): 
    import collections 
    d = collections.defaultdict(list) 
    for word in words: 
     sortedWord = str(sorted(word)) 
     d[ hash(sortedWord) ].append(word) 
    maxKey = max(d.keys(), key = lambda k : len(d[k])) 
    return d[maxKey] 

iter = wordIterator('C:\\Python32\\megalist.txt') 
#iter = (word for word in iter if len(word) == 5) 
print largestAnagram(iter) 

编辑：

在回应的意见，该hash(sortedWord)，是一个节省空间的优化，在这种情况下可能为时过早，减少sortedWord返回一个整数，因为我们真的不关心关键，只要我们总是可以唯一地恢复所有相关的字谜。使用sortedWord作为关键是同样有效的。

key关键字参数为max可让您根据谓词查找集合中的最大元素。所以语句maxKey = max(d.keys(), key = lambda k : len(d[k]))是一个简洁的python表达式，用于回答查询，给出了字典中的键，哪个键具有最大长度的关联值？。在这方面，以max该呼叫可能已被写入（更冗长）为valueWithMaximumLength(d)，其中该功能被定义为：

def valueWithMaximumLength(dictionary): 
    maxKey = None 
    for k, v in dictionary.items(): 
     if not maxKey or len(dictionary[maxKey]) < len(v): 
      maxKey = k 
    return maxKey 

Answer 2

wordList应该是set。

测试列表中的成员资格需要您扫描列表中的所有元素，检查它们是否是您生成的单词。测试集合中的成员资格不（平均）取决于集合的大小。

下一个显而易见的优化是，一旦你测试了一个单词，你可以从wordList中删除它的所有排列，因为它们将在createList中给出完全相同的设置。如果一切都用set s完成，那么这是一个非常简单的操作 - 实际上，您只需使用二进制减号。

Answer 3

没有必要做所有的排列，这是浪费内存和CPU。 所以，首先你的字典中应保持在一个二叉树，像这样：

e.g. Dict = ['alex', 'noise', 'mother', 'xeal', 'apple', 'google', 'question'] 

    Step 1: find the "middle" word for the dictionary, e.g. "mother", because "m" 
      is somewhere in the middle of the English alphabet 
      (this step is not necessary, but it helps to balance the tree a bit) 

    Step 2: Build the binary tree: 

       mother 
      / \ 
      /  \ 
     alex   noise 
      \   /\ 
      \  / \ 
      apple question xeal 
      \ 
       \ 
      google 

    Step 3: start looking for an anagram by permutations: 
    alex: 1. "a"... (going deeper into binary tree, we find a word 'apple') 
     1.1 # of, course we should omit apple, because len('apple') != len('alex') 
      # but that's enough for an example: 
     2. Check if we can build word "pple" from "lex": ("a" is already reserved!) 
      -- there is no "p" in "lex", so skipping, GOTO 1    
     ... 
     1. "l"... - nothing begins with "l"... 
     1. "l"... - nothing begins with "e"... 
     1. "x" - going deeper, "xeal" found 
     2. Check if "eal" could be built from "ale" ("x" is already reserved) 
      for letter in "eal": 
       if not letter in "ale": 
        return False 
      return True 

就是这样:)这个算法应该工作得更快。

编辑：

检查bintrees包，以避免对二叉树实现花时间。