如何让这个程序运行得更快？

Question

所以这是我用Python写的第一个程序。我想要一个字符串，并输出所有真正的单词。我已经完成了（我需要找到一个包含更多单词的参考文件），但它不具有可扩展性，因为如果没有Python花费很长时间才能返回某些内容，我无法输入超过8个字符。

def lower_and_remove_spaces(fill_string): 
    ''' 
    function takes a string of 2 or more characters and prints out all the permutations 
    of words that the characters can make. 
    ''' 
    lower_string = '' 

    for i in fill_string: 
     if i.isalpha(): 
      lower_string += i.lower() 

    return lower_string  

def fill_list(input_string): 
    iter_list = [] 
    string_list = [] 
    this_string = lower_and_remove_spaces(input_string) 
    for num in range(2,len(this_string)+1): 
     iter_list.append(itertools.permutations(this_string,num)) 

    for iters in iter_list: 
     for lists in iters: 
     string_list.append(list(lists)) 

    return string_list 

def word_list(string): 
    string_list = fill_list(string) 
    a_word_list = [] 
    a_string = '' 
    for i in string_list: 
     if not a_string == '': 
     a_word_list.append(a_string) 
     a_string = '' 
     for y in i: 
     a_string += y 
    return a_word_list 

我理解这个跳开了不少，但我不知道什么是更好的方法来做到这一点，以便它的可扩展性？

Answer 1

一些快速的想法：使所有的排列都将O（n！），这是没有办法的。即使你优化你的代码，当n接近更大的数字时，你仍然会碰壁。如果你有一个有效的词汇的字典，这个问题有点不同。在病态输入集（您的字典包含所有排列）下，您无法做到比这更好。

但是，你可以做以下

1. 保持有效字的字典中的前缀树
2. 手动生成排列的递归而不是通过itertools.ie，选择一个字母，开始一个字，递归
3. 在每一步中，检查前缀是否有效，否则修剪搜索树。

的这个性能在实践中为O好得多（N！）

如果你不熟悉的前缀树，这里的模拟与Python的哈希同样的事情的方式

def prefix_hash(list_o_words): 
     ret = {} 
     for word in list_o_words: 
      for i in range(2,len(word)-1): 
       ret[word[:i]] = 'prefix' # this should check if it's a word first.. 
     ret[word] = 'word' 

如果您需要更多帮助，请提出问题。