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

其实不需要做所有的排列组合，这样会浪费内存和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包，这样就不用花时间去实现二叉树了。

Answer 2

wordList 应该是一个 set。

在一个列表中检查某个元素是否存在，需要逐个查看列表里的每个元素，看看它们是不是你生成的那个词。而在一个集合中检查元素是否存在，通常不需要考虑集合的大小。

下一个明显的优化是，一旦你检查过一个词，就可以把它的所有变体从 wordList 中移除，因为它们在 createList 中会产生完全相同的结果。如果使用 set，这个操作非常简单——实际上，你只需要用一个二元减法就可以了。

Answer 3

下面的内容在处理一个小字典时似乎效果不错。通过对单词中的字母进行排序，我们可以很容易地判断两个单词是否是变位词。从这个出发点开始，只需要以某种方式将单词收集起来就可以了。如果想要报告所有匹配的单词，而不仅仅是第一个，这个方法也不难修改。

如果你需要限制字母的数量，使用迭代器是一种方便的方法，可以用来筛选出一些单词。

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 作为键也是完全可以的。

max 函数的 key 参数让你可以根据某个条件找到集合中的最大元素。所以这句 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