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 作为键同样有效。

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