2011-05-21 131 views
2

我解決了使用這個(效率極其低下的方法)問題的所有字典,有效字謎遊戲:Python-代碼優化幫助 - 查找字

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分鐘,發現五個字母的單詞這是字典有效的字典。我想用沒有字母限制的單詞來運行它,但需要花費大量的時間。無論如何要優化這個嗎?

回答

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返回一個整數,因爲我們真的不關心關鍵,只要我們總是可以唯一地恢復所有相關的字謎。使用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 
+0

+1不錯的展示實際問題如何在數據採集步驟中解決,這使查找/查詢步驟幾乎微不足道。強調初始數據表示的影響。 – ThomasH 2011-05-21 11:27:31

+0

這太棒了;我理解這個想法,儘管我很困惑這些行具體做什麼: d [hash(sortedWord)] .append(word) maxKey = max(d.keys(),key = lambda k:len(d [k])) 你能解釋一下 – Parseltongue 2011-05-21 20:18:34

+0

@Parseltongue,我希望編輯回答你的問題 – 2011-05-22 05:03:36

2

wordList應該是set

測試列表中的成員資格需要您掃描列表中的所有元素,檢查它們是否是您生成的單詞。測試集合中的成員資格不(平均)取決於集合的大小。

下一個顯而易見的優化是,一旦你測試了一個單詞,你可以從wordList中刪除它的所有排列,因爲它們將在createList中給出完全相同的設置。如果一切都用set s完成,那麼這是一個非常簡單的操作 - 實際上,您只需使用二進制減號。

+0

這肯定是有幫助的,但接受的答案是更加優化。 – Parseltongue 2011-05-21 20:41:46

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包,以避免對二叉樹實現花時間。