순열을 빨리 만드는 데 도움이 필요합니다.

Question

여기에 제 작업 코드가 있습니다. 유효한 단어를 빨리 찾는 방법을 찾으려고 노력하고 있습니다. 각 단어에 대해 별도의 사전 목록을 만드는 것에 대해 생각하고있었습니다. yall은 무엇을 생각합니까?

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 % 더 빠르게 수행하고있다.

그것의 지금 개까지 기본적으로 O입니다 (n 개 *의 m!) n은 단어 목록의 크기이며, m은 문자의 번호입니다 문제는 알고리즘 함께

---

>>> 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을 만드는 단어의 모든 순열을 만들 때! words 여기서 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) 

죄송합니다. 내 파이썬은 약간 녹슬었지만 잘하면 당신은 아이디어를 얻을 수 있습니다. 로 내부 루프를 교체

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 (log (n) * m!)의 성능을 향상시킬 수 있습니다.

그러나 실제로 성능을 향상 시키려면 검색을 위해 문자를 완전히 삭제해야합니다. 알파벳순으로 단어 목록에있는 각 단어의 문자를 먼저 정렬하십시오. p가 평균 단어 길이 인 경우 O (n * p log (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() 개체를 serialize하면 스크립트를 시작할 때마다 트리를 작성할 필요가 없습니다.

SIL International (총 109582 단어)의 단어 목록을 사용하여 나무를 만들려고했습니다.

타이밍을 timeit으로 지정하면 처음부터 dict를 작성하는 대신 오브젝트 파일을 unpickle 할 때 실행 시간이 ~ 50 % 감소합니다.

순열만을 확인하려면 add_word() 방법을 Tree()으로 변경하여 문자를 먼저 정렬해야합니다. Tree.is_word()에 대한 인수를 입력해야합니다.