우선 파이썬에서의 계산 - 최대?

Question

나는 파이썬에서 다음 "게임"을 구현하기 위해 노력하고있어 :

시작 단어를 감안할 때,에 성공 단어를 찾아 수정 단계에 따라 변경 허용 : 제거하거나 편지를 추가하고

작업을 뒤 바꿔 최소한의 단계로 시작부터 끝까지 길을 찾는 것입니다.

내 접근 방식은 글자를 추가/제거하고, 결과 글자를 바꾸고, 사전에서 각 순열을 찾는다.

이렇게하면 빠르게 실행 시간이 길어집니다 (9 글자 단어 및 첫 번째 단계는 약 60 초).

여기 내 코드입니다.

import time 
from itertools import permutations 
startword = 'croissant' 

nodes = list() 

nodes.append(startword) 

dicts = set([line.rstrip('\n') for line in open('wordList.txt')]) 
alpha = set([chr(i) for i in range(ord('a'),ord('z')+1)]) 


def step(nodes): 
    nnodes = list() 
    for word in nodes: 
     for s in word: 
      new_word = word.replace(s, '', 1) 
      perms = [''.join(p) for p in permutations(new_word)] 
      for per in perms: 
       if per in dicts: 
        nnodes.append(per) 
     for s in alpha: 
      new_word = word + s 
      perms = [''.join(p) for p in permutations(new_word)] 
      for per in perms: 
       if per in dicts: 
        nnodes.append(per) 
return set(nnodes) 


btime = time.time() 
step(nodes) 
print time.time() - btime 

어떻게 성능/로직을 향상시킬 수 있습니까? 우리는 폭 넓은 첫 번째 검색을 사용하도록 특별히 요청받습니다.

Answer 1

흥미로운 질문입니다! 성능을 극적으로 향상시킬 수있는 방법이 있습니다. 단어 목록을 탐색하고 단어 목록을 탐색하여 각 단어를 확인하는 대신 단어 목록의 각 단어에 대한 문자를 알파벳순으로 정렬하여 알파벳순으로 짧게/늘린 단어와 직접 비교할 수 있습니다.

예를 들어 croissant을 사용하면 문자를 영문자 순화하여 acinorsst을 생성 할 수 있습니다. 그런 다음 문자가 제거되거나 추가 된 acinorsst이 키가 알파벳순 문자열 인 목록의 defaultdict에 있는지 확인하고 해당 값 (해당 사전 순 정렬에 해당하는 실제 단어 목록)을 검색합니다.

그것은 훨씬 덜 혼란 코드에서 설명하는 것입니다, 그래서 아래에 게시 한 :

from collections import defaultdict 
import itertools as its 
import time 

def get_alpha_dicts(): 
    wa_dict = {}#word: alphabetized dict 
    aw_dict = defaultdict(list)#alphabetized: corresponding WORDS dict 
    for line in open('wordList.txt'): 
     word = line.rstrip('\n') 
     alpha_word = ''.join(sorted(word)) 
     wa_dict[word] = alpha_word 
     aw_dict[alpha_word].append(word) 
    return wa_dict, aw_dict  

def step(nodes, aw_dict): 
    alpha = set([chr(i) for i in range(ord('a'),ord('z')+1)]) 
    nnodes = list() 
    for word in nodes: 
     alpha_word = ''.join(sorted(word)) 
     #remove a char from word 
     short_words = set([''.join(w) for w in its.combinations(alpha_word, len(start_word)-1)]) 
     for short_word in short_words: 
      nnodes.extend(aw_dict[short_word]) 
     #add a char to word 
     long_words = [''.join(sorted(alpha_word + s)) for s in alpha] 
     for long_word in long_words: 
      nnodes.extend(aw_dict[long_word]) 
    return set(nnodes) 

if __name__ == "__main__": 
    start_word = 'croissant' 
    nodes = list() 
    nodes.append(start_word) 
    wa_dict, aw_dict = get_alpha_dicts() 
    btime = time.time() 
    print step(nodes, aw_dict) 
    print time.time() - btime 

는 희망이 도움이!