需要幫助使排列更快

Question

這裏是我的工作代碼，我試圖找到方法使其更快地找到有效的單詞，我正在考慮可能爲每個單詞做單獨的詞典列表，你覺得怎麼樣？

import random 
import itertools 

file_name='words.txt' 

def load_words(): 
    try: 
     f=open(file_name,'r') 
     str1=f.read() 
     f.close() 
    except: 
     print('Problem opening the file',file_name) 
    list1=[] 
    list1=str1.split() 
    return(list1) 

def is_valid(str1,list1): 
    valid=False 
    if str1 in list1: 
     valid=True 
    return valid 

def generate(words,letters): 
    answers=[] 
    for length in range(2,len(letters)+1): 
     for x in itertools.permutations(letters,length): 
      word='' 
      for let in x: 
       word+=let 
      if is_valid(word.upper(),words): 
       answers.append(word) 
       print(word) 
    print(answers) 

def main(): 
    words=load_words() 
    letters = input('Enter your letters') 
    answers = generate(words,letters) 

main() 

Answer 1

如果你是在使它的可讀性，你可以嘗試的成本增加速度過於激烈以下

def is_valid(str1,list1): 
    return str1 in list1 
words=["BAD","CAB","BEC"] 
def generate2(words,letters): 
    answers=[] 
    [[answers.append(''.join(x).upper()) for x in itertools.permutations(letters,length) if ''.join(x).upper() in words] for length in range(2,len(letters)+1)] 
    #print(answers) 
    return answers 

List comprehension is faster than loops。因此，將這兩個循環結合到一個單一的理解。除了該聲明

 word='' 
     for let in x: 
      word+=let 
     if is_valid(word.upper(),words): 

可以結合起來，如果is_valid(''.join(x).upper,words)甚至''.join(x).upper in words，記得函數調用是昂貴的。

我已經在速度上做了一個比較，看起來列表的理解速度提高了50％。

它現在高達你來決定

---

>>> stmt1=""" 
def is_valid(str1,list1): 
    valid=False 
    if str1 in list1: 
     valid=True 
    return valid 
words=["BAD","CAB","BEC"] 
def generate1(words,letters): 
    answers=[] 
    for length in range(2,len(letters)+1): 
     for x in itertools.permutations(letters,length): 
      word='' 
      for let in x: 
       word+=let 
      if is_valid(word.upper(),words): 
       answers.append(word) 
       #print(word) 
    #print(answers) 
    return answers 
generate1(words,['A','B','C','D','E']) 
""" 
>>> 
>>> stmt2=""" 
def is_valid(str1,list1): 
    return str1 in list1 
words=["BAD","CAB","BEC"] 
def generate2(words,letters): 
    answers=[] 
    [[answers.append(''.join(x).upper()) for x in itertools.permutations(letters,length) if ''.join(x).upper() in words] for length in range(2,len(letters)+1)] 
    #print(answers) 
    return answers 
generate2(words,['A','B','C','D','E']) 
""" 
>>> 
>>> t1=timeit.Timer(stmt=stmt1) 
>>> t2=timeit.Timer(stmt=stmt2) 
>>> t1.repeat(number=1000) 
>>> t2=timeit.Timer(stmt=stmt2) 
>>> t1.repeat(number=1000) 
[0.47923321640178074, 0.4353549521401874, 0.4362746333173959] 
>>> t2.repeat(number=1000) 
[0.2536238984591819, 0.2470974750062851, 0.24726312027155473] 

Answer 2

更改您的list1一組：

set1 = set(list1) 

測試str1 in set1會比str1 in list1快多如果你頻繁的測試，名單很長。

Answer 3

首先，剖析代碼。這會告訴你哪裏的部件很慢。其次，你可能會考慮將單詞列表轉換爲一個集合，它應該有一個更快的'in'運算符來檢查單詞是否在那裏。

第三，考慮簡化代碼以刪除不必要的語句，例如。

def is_valid(str1,list1): 
    return str1 in list1 

Answer 4

你到底想要完成什麼？看起來你有一些你正在閱讀的有效詞彙的字典。你爲什麼要排列從用戶給出的輸入中可以構建的所有單詞的組合？

你需要考慮一下你的算法。你創建的每個置換都是遍歷字典中的每個已知單詞（list1）。當你創建你正在創建的單詞的所有排列！其中m個字母是用戶給出的字母。

你基本上有O（n * m！）。對於像7這樣的少數事情來說，這是非常大的。通過使用一個集合而不是一個列表，你可以把這個n項縮短到一個常數，它將你的算法改變爲O（m！），這仍然太大。 如果我不得不猜測這個算法在做什麼，我會說你想知道你可以從你給出的字母中創建多少個已知單詞。你再也沒有這樣說，但我們假設這就是你的意思。

更快的算法是遍歷字典中的每個單詞，並查看是否可以通過從輸入中選擇字母來製作該單詞。所以你只能一次O（n * m）遍歷字典。這消除了排列輸入的需要。這裏的算法：

user_input = input("Give me some words") 
for word in list1: 
    current = user_input 
    found = True 
    for letter in word: 
     if letter in current: 
      current.remove(letter) 
     else 
      found = False 
      break; 
    if found: 
     answers.add(word) 
print(answers) 

對不起，我的python有點生疏，但希望你會明白。

Answer 5

嘗試更換內部循環：

for x in itertools.permutations(letters,length): 
    word = ''.join(x) 
    if word.upper() in words: 
     answers.append(word) 
     print(word) 

Answer 6

的問題是與你的算法基本上是O（N * M個！），其中n是字表的大小，m是字母數字。將單詞列表更改爲一個集合應該使搜索日誌時間和的性能提高到O（log（n）* m！），正如其他人在這裏推薦的那樣。

然而，真正的性能增益將來自完全消除排列搜索字母。首先按字母順序排列單詞列表中每個單獨單詞的字母;它應該採用O（n * p log（p））時間，其中p是平均字長。然後在O（n * log（n））時間內按字母順序對整個列表進行排序。還要跟蹤原始單詞，以便您可以從已排序單詞列表中的字符串轉到O（1）中的原始單詞。接下來按字母順序排序推算字母，並在排序的字詞列表中搜索它們。

上述算法中最慢的操作是對按字母排序的字符串列表進行排序，即O（n Log（n））。搜索這樣的列表是Log（n），並且在O（n Log（n））時間中執行整個算法的結果爲。它應該線性縮放到m，即輸入的字母數量。

實施留給讀者。

Answer 7

如果你打算經常查找單詞，你應該從你的數據中建立一個tree。

簡單的例子如下。代碼應該是不言而喻的，但請詢問是否有不清楚的地方。

import pickle 


class Tree: 
    def __init__(self): 
     self.letters = dict() 

    def add_words(self, words): 
     for word in words: 
      self.add_word(word) 

    def add_word(self, word): 
     chars = list(word.lower()) 
     l = chars.pop(0) 
     try: 
      self.letters[l].add_word(chars) 
     except KeyError: 
      self.letters[l] = Letter(l) 
      self.letters[l].add_word(chars) 

    def is_word(self, word): 
     chars = list(word.lower()) 
     l = chars.pop(0) 
     try: 
      return self.letters[l].is_word(chars) 
     except KeyError: 
      return False 


class Letter: 
    def __init__(self, letter): 
     self.letter = letter 
     self.sub_letters = dict() 
     self.is_a_word = False 

    def add_word(self, word): 
     if len(word) == 0: 
      self.is_a_word = True 
      return 
     l = word.pop(0) 
     try: 
      self.sub_letters[l].add_word(word) 
     except KeyError: 
      self.sub_letters[l] = Letter(l) 
      self.sub_letters[l].add_word(word) 

    def is_word(self, word): 
     if len(word) == 0: 
      return self.is_a_word 
     l = word.pop(0) 
     try: 
      return self.sub_letters[l].is_word(word) 
     except KeyError: 
      return False 


def get_dict(obj_file, dict_file): 
    try: 
     with open(obj_file, 'rb') as my_dict: 
      return pickle.load(my_dict) 
    except IOError: 
     my_tree = Tree() 
     with open(dict_file, 'rb') as in_file: 
      for word in in_file: 
       my_tree.add_word(word.strip()) 
     with open(obj_file, 'wb') as outfile: 
      pickle.dump(my_tree, outfile, pickle.HIGHEST_PROTOCOL) 
     return my_tree 


obj_file = 'mydict.pk' 
dict_file = 'wordlist.txt' 
my_tree = get_dict(obj_file, dict_file) 

（有很多不同種類的樹木，這只是一個很簡單的例子）

當樹已經建成，這將只需要len(word)函數調用，以確定輸入的字是有效的。這是一個巨大的改進，從if word in wordlist，這需要O(len(wordlist))。

這種方法的不足之處在於生成樹可能需要一些時間。通過使用pickle序列化Tree()對象，每次啓動腳本時都不必構建樹。

我試圖用SIL International（總共109582字）的單詞表建立一棵樹。

使用timeit進行計時時，在取消對象文件而不是從頭開始構建字典時，執行時間減少了約50％。

如果你只想檢查排列，你應該改變add_word()方法Tree()排序的第一個字母。輸入參數Tree.is_word()當然也應該排序。