需要帮助使排列更快

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()当然也应该排序。