如何讓這個程序運行得更快？

-1

所以這是我用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

我理解這個跳開了不少，但我不知道什麼是更好的方法來做到這一點，以便它的可擴展性？

來源

2012-08-13 MickJuice

我有一種感覺，這將是更適合http://codereview.stackexchange.com/。 – 2012-08-13 03:46:13

入口點在哪裏？ – 2012-08-13 03:50:03

你確實意識到itertools.permutations對於長度爲8的東西會給你大約40k個排列。 – 2012-08-13 03:53:46

一些快速的想法：使所有的排列都將O（n！），這是沒有辦法的。即使你優化你的代碼，當n接近更大的數字時，你仍然會碰壁。如果你有一個有效的詞彙的字典，這個問題有點不同。在病態輸入集（您的字典包含所有排列）下，您無法做到比這更好。

但是，你可以做以下

保持有效字的字典中的前綴樹
手動生成排列的遞歸而不是通過itertools.ie，選擇一個字母，開始一個字，遞歸
在每一步中，檢查前綴是否有效，否則修剪搜索樹。

的這個性能在實踐中爲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'

如果您需要更多幫助，請提出問題。

來源

2012-08-13 03:52:36 dfb

如何讓這個程序運行得更快？

回答

相關問題