이 Python 코드를 최적화하여 단어 차이 1으로 모든 단어를 생성하려면 어떻게해야합니까?
https://stackoverflow.com/questions/788084
-
16-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
프로파일 링 쇼 이것은 내가 쓴 작은 단어 게임에 대한 내 코드의 가장 느린 부분임을 보여줍니다.
def distance(word1, word2):
difference = 0
for i in range(len(word1)):
if word1[i] != word2[i]:
difference += 1
return difference
def getchildren(word, wordlist):
return [ w for w in wordlist if distance(word, w) == 1 ]
메모:
distance()5 백만 회 이상이라고 불리는데, 그 중 대다수는 GetChildren에서 나온 것입니다.word정확히 1 글자로.- Wordlist는 같은 수의 문자를 포함하는 단어 만 가지고 있도록 미리 필터링됩니다.
word그래서 그것은 그것을 보장합니다word1그리고word2숯 같은 수가 있습니다. - 저는 Python을 처음 접했습니다 (3 일 전에 배우기 시작). 이름 지정 규칙이나 다른 스타일에 대한 의견도 감사합니다.
- 단어 목록의 경우, 12 단어 단어 목록 "2+2lemma.txt"파일 사용
결과:
감사합니다. 다른 제안의 조합으로 프로그램을 두 배나 빠르게 실행했습니다 (묻기 전에 스스로 한 최적화 외에도 초기 구현에서 4 배 속도가 증가합니다).
나는 2 세트의 입력을 테스트하여 a와 b라고 부를 것입니다.
최적화 1 : 단어의 지수를 반복하여 1,2 ... 에서
for i in range(len(word1)):
if word1[i] != word2[i]:
difference += 1
return difference
에게 문자 페어를 사용하여 반복하십시오 zip(word1, word2)
for x,y in zip (word1, word2):
if x != y:
difference += 1
return difference
입력 A의 경우 11.92에서 9.18까지 실행 시간, 입력 B의 경우 79.30 ~ 74.59
Optimization2 : 거리 방법 외에도 다른 방법으로 별도의 방법을 추가했습니다 (A* 휴리스틱을 위해 여전히 다른 곳이 필요했습니다).
def is_neighbors(word1,word2):
different = False
for c1,c2 in zip(word1,word2):
if c1 != c2:
if different:
return False
different = True
return different
입력 A의 경우 9.18 ~ 8.83, 입력 B의 경우 74.59 ~ 70.14로 실행 시간이있었습니다.
최적화 3 : 여기에서 큰 승자가 사용해야했습니다 izip 대신에 zip
입력 A의 경우 8.83에서 5.02까지 실행 시간, 입력 B의 경우 70.14 ~ 41.69
나는 아마도 낮은 수준의 언어로 글을 더 잘 작성할 수 있지만 지금은 이것에 만족합니다. 모두 감사합니다!
다시 편집 : 첫 번째 문자가 일치하지 않는 경우를 확인하는 Mark의 방법을 사용한 더 많은 결과는 5.02-> 3.59 및 41.69-> 29.82에서 다운되었습니다.
그것과 그 위에 통합 izip 대신에 range, 나는 이것으로 끝났다 :
def is_neighbors(word1,word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
different = False
for x,y in izip(word1[1:],word2[1:]):
if x != y:
if different:
return False
different = True
return different
조금 더 짜여서 3.59-> 3.38 및 29.82-> 27.88에서 시간을 줄였습니다.
더 많은 결과!
Sumudu의 제안을 시도합니다 "Word"에서 1 글자를 끄는 모든 문자열 목록을 생성 한 다음 Wordlist에 어떤 문자열이 있는지 확인하십시오., is_neighbor 함수 대신에 나는 이것으로 끝났다 :
def one_letter_off_strings(word):
import string
dif_list = []
for i in xrange(len(word)):
dif_list.extend((word[:i] + l + word[i+1:] for l in string.ascii_lowercase if l != word[i]))
return dif_list
def getchildren(word, wordlist):
oneoff = one_letter_off_strings(word)
return ( w for w in oneoff if w in wordlist )
결국 느려졌지만 (3.38-> 3.74 및 27.88-> 34.40) 유망한 것처럼 보였습니다. 처음에 나는 최적화해야 할 부분이 "one_letter_off_strings"라고 생각했지만 프로파일 링은 달리 보여 주었고 느린 부분은 사실입니다.
( w for w in oneoff if w in wordlist )
"Oneoff"와 "Wordlist"를 전환하면 차이가있을 것이라고 생각하고 두 목록의 교차점을 찾고 있다는 것이 저를 때렸을 때 다른 방식으로 비교를했습니다. 나는 그것을 대체한다 글자에 대한 설정:
return set(oneoff) & set(wordlist)
멍청이! 3.74-> 0.23 및 34.40-> 2.25
이것은 원래 순진한 구현과의 완전하게 놀랍고 총 속도 차이 (23.79-> 0.23 및 180.07-> 2.25이므로 원래 구현보다 약 80 ~ 100 배 더 빠릅니다.
누구든지 관심이 있으시면 블로그 게시물을 만들었습니다 프로그램을 설명합니다 그리고 최적화를 설명합니다 여기에 언급되지 않은 것을 포함하여 만들어졌습니다 (코드의 다른 섹션에 있기 때문에).
위대한 토론 :
좋아, 나와 알 수없는 것은 큰 논쟁을 벌이고 있습니다. 그의 대답. 그는 C에 포팅 된 경우 원래 방법 (세트를 사용하는 대신 IS_Neighbor를 사용하여)을 사용하는 것이 더 빠를 것이라고 주장합니다. 나는 2 시간 동안 내가 쓴 C 모듈을 얻으려고 2 시간 동안 시도한 후에는 많은 성공을 거두지 않고 링크 할 수 있도록 시도했습니다. 따르다 이것 그리고 이것 예를 들어, 프로세스가 Windows에서 약간 다른 것처럼 보입니까? 모르겠지만 포기했습니다. 어쨌든 여기 프로그램의 전체 코드가 있으며 텍스트 파일은 12 단어 단어 목록 "2+2lemma.txt"파일 사용 코드가 조금 지저분하다면 죄송합니다. 이것은 내가 함께 해킹 한 것입니다. 또한 워드리스트에서 쉼표를 벗기는 것을 잊어 버렸습니다. 실제로 Cleanentries의 숯 목록에 쉼표를 추가하여 같은 비교를 위해 남겨 둘 수있는 버그입니다.
from itertools import izip
def unique(seq):
seen = {}
result = []
for item in seq:
if item in seen:
continue
seen[item] = 1
result.append(item)
return result
def cleanentries(li):
pass
return unique( [w.strip('[]') for w in li if w != "->"] )
def distance(word1, word2):
difference = 0
for x,y in izip (word1, word2):
if x != y:
difference += 1
return difference
def is_neighbors(word1,word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
different = False
for x,y in izip(word1[1:],word2[1:]):
if x != y:
if different:
return False
different = True
return different
def one_letter_off_strings(word):
import string
dif_list = []
for i in xrange(len(word)):
dif_list.extend((word[:i] + l + word[i+1:] for l in string.ascii_lowercase if l != word[i]))
return dif_list
def getchildren(word, wordlist):
oneoff = one_letter_off_strings(word)
return set(oneoff) & set(wordlist)
def AStar(start, goal, wordlist):
import Queue
closedset = []
openset = [start]
pqueue = Queue.PriorityQueue(0)
g_score = {start:0} #Distance from start along optimal path.
h_score = {start:distance(start, goal)}
f_score = {start:h_score[start]}
pqueue.put((f_score[start], start))
parent_dict = {}
while len(openset) > 0:
x = pqueue.get(False)[1]
if x == goal:
return reconstruct_path(parent_dict,goal)
openset.remove(x)
closedset.append(x)
sortedOpen = [(f_score[w], w, g_score[w], h_score[w]) for w in openset]
sortedOpen.sort()
for y in getchildren(x, wordlist):
if y in closedset:
continue
temp_g_score = g_score[x] + 1
temp_is_better = False
appended = False
if (not y in openset):
openset.append(y)
appended = True
h_score[y] = distance(y, goal)
temp_is_better = True
elif temp_g_score < g_score[y] :
temp_is_better = True
else :
pass
if temp_is_better:
parent_dict[y] = x
g_score[y] = temp_g_score
f_score[y] = g_score[y] + h_score[y]
if appended :
pqueue.put((f_score[y], y))
return None
def reconstruct_path(parent_dict,node):
if node in parent_dict.keys():
p = reconstruct_path(parent_dict,parent_dict[node])
p.append(node)
return p
else:
return []
wordfile = open("2+2lemma.txt")
wordlist = cleanentries(wordfile.read().split())
wordfile.close()
words = []
while True:
userentry = raw_input("Hello, enter the 2 words to play with separated by a space:\n ")
words = [w.lower() for w in userentry.split()]
if(len(words) == 2 and len(words[0]) == len(words[1])):
break
print "You selected %s and %s as your words" % (words[0], words[1])
wordlist = [ w for w in wordlist if len(words[0]) == len(w)]
answer = AStar(words[0], words[1], wordlist)
if answer != None:
print "Minimum number of steps is %s" % (len(answer))
reply = raw_input("Would you like the answer(y/n)? ")
if(reply.lower() == "y"):
answer.insert(0, words[0])
print "\n".join(answer)
else:
print "Good luck!"
else:
print "Sorry, there's no answer to yours"
reply = raw_input("Press enter to exit")
IS_Neighbors 메소드가 사용되지 않더라도 남았습니다. 이것은 C로 포팅되도록 제안 된 방법입니다.이를 사용하려면 getchildren을 이것으로 바꾸십시오.
def getchildren(word, wordlist):
return ( w for w in wordlist if is_neighbors(word, w))
C 모듈로 작동하도록하는 것에 관해서는 멀리 얻지 못했지만 이것이 제가 생각해 낸 것입니다.
#include "Python.h"
static PyObject *
py_is_neighbor(PyObject *self, Pyobject *args)
{
int length;
const char *word1, *word2;
if (!PyArg_ParseTuple(args, "ss", &word1, &word2, &length))
return NULL;
int i;
int different = 0;
for (i =0; i < length; i++)
{
if (*(word1 + i) != *(word2 + i))
{
if (different)
{
return Py_BuildValue("i", different);
}
different = 1;
}
}
return Py_BuildValue("i", different);
}
PyMethodDef methods[] = {
{"isneighbor", py_is_neighbor, METH_VARARGS, "Returns whether words are neighbors"},
{NULL, NULL, 0, NULL}
};
PyMODINIT_FUNC
initIsNeighbor(void)
{
Py_InitModule("isneighbor", methods);
}
나는 이것을 사용하여 이것을 프로파일했다 :
Python -M Crprofile "WordGame.py"
기록 된 시간은 Astar Method Call의 총 시간이었습니다. 빠른 입력 세트는 "구절 시인"이었고 긴 입력 세트는 "시인 구절"이었습니다. 타이밍은 분명히 다른 기계마다 다를 수 있으므로 누군가가이를 시도하면 C 모듈뿐만 아니라 프로그램을 그대로 비교할 수 있습니다.
해결책
Word 목록이 매우 길다면 'Word'에서 가능한 모든 1 글자 분류를 생성하는 것이 더 효율적 일 수 있습니다. 그러면 목록에 어떤 것이 있는지 확인하십시오. 파이썬은 모르지만 로그 타임 조회를 허용하는 WordList에 적합한 데이터 구조가 있어야합니다.
나는 당신의 단어가 합리적인 길이 (~ 10 글자)라면 250 개의 잠재적 단어 만 찾고 있기 때문에 이것을 제안합니다.이 단어 목록은 수백 단어보다 더 큰 경우 더 빠릅니다.
다른 팁
당신의 기능 distance 실제로 거리 = 1에만 관심이있을 때 총 거리를 계산하는 것입니다. 대부분의 사례는 몇 캐릭터 내에서> 1이라는 것을 알기 때문에 일찍 돌아와서 많은 시간을 절약 할 수 있습니다.
그 외에도 더 나은 알고리즘이있을 수 있지만 생각할 수는 없습니다.
편집하다: 또 다른 아이디어.
첫 번째 캐릭터가 일치하는지 여부에 따라 2 건을 만들 수 있습니다. 일치하지 않으면 나머지 단어는 정확히 일치해야하며 한 번으로 테스트 할 수 있습니다. 그렇지 않으면, 당신이하고있는 일과 유사하게 수행하십시오. 당신은 그것을 재귀 적으로 할 수도 있지만, 나는 그것이 더 빠를 것이라고 생각하지 않습니다.
def DifferentByOne(word1, word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
same = True
for i in range(1, len(word1)):
if word1[i] != word2[i]:
if same:
same = False
else:
return False
return not same
편집 2 : 중복이라고 말하면 문자열이 같은 길이인지 확인하기 위해 수표를 삭제했습니다. 달리기 라이언의 테스트 내 자신의 코드와 IS_Neighbors 함수에 Mizardx가 제공합니다, 나는 다음을 얻는다 :
- 원래 거리 () : 3.7 초
- 내 다른 byone () : 1.1 초
- Mizardx의 is_neighbors () : 3.7 초
편집 3 : (아마도 커뮤니티 위키 영토에 들어가지만 ...)
zip 대신 izip을 사용하여 iS_Neighbors ()의 최종 정의를 시도합니다. 2.9 초.
내 최신 버전은 다음과 같습니다. 여전히 1.1 초입니다.
def DifferentByOne(word1, word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
different = False
for i in range(1, len(word1)):
if word1[i] != word2[i]:
if different:
return False
different = True
return different
from itertools import izip
def is_neighbors(word1,word2):
different = False
for c1,c2 in izip(word1,word2):
if c1 != c2:
if different:
return False
different = True
return different
또는 아마도 라이닝을 할 수도 있습니다 izip 암호:
def is_neighbors(word1,word2):
different = False
next1 = iter(word1).next
next2 = iter(word2).next
try:
while 1:
if next1() != next2():
if different:
return False
different = True
except StopIteration:
pass
return different
그리고 다시 작성 getchildren:
def iterchildren(word, wordlist):
return ( w for w in wordlist if is_neighbors(word, w) )
사람들은 주로 더 빠른 기능을 작성하려고 노력함으로써 이것에 대해 노력하고 있지만 다른 방법이있을 수 있습니다 ..
"거리"는 5 백만 회 이상이라고합니다
왜 이런거야? 아마도 최적화하는 더 좋은 방법은 distance, 밀리 초의 면도보다는 distance's 실행 시간. 전체 스크립트를 보지 않고는 말할 수 없지만 특정 기능을 최적화하는 것은 일반적으로 불필요합니다.
불가능하다면 아마도 C 모듈로 쓸 수 있습니까?
동일한 인수로 거리 함수가 얼마나 자주 호출됩니까? 구현하기 쉬운 최적화는 사용하는 것입니다 메모 화.
아마도 당신은 아마도 문자의 냉소 세트와 단어별로 다른 단어 목록으로 일종의 사전을 만들 수 있으며 그 값을 찾아 볼 수도 있습니다. 이 데이터 구조는 피클을 통해 저장 및로드되거나 시작시 처음부터 생성 될 수 있습니다.
단락 회로 평가는 사용중인 단어가 매우 길면 이익을 얻을 수 있습니다. 왜냐하면 사용중인 해밍 거리 알고리즘은 기본적으로 O (n)이기 때문입니다. 여기서 n은 단어 길이입니다.
나는 설명 할 수있는 대안적인 접근법에 대해 TimeIT로 실험을했다.
시간이 타이어 결과
솔루션
d = """\
def distance(word1, word2):
difference = 0
for i in range(len(word1)):
if word1[i] != word2[i]:
difference += 1
return difference
"""
t1 = timeit.Timer('distance("hello", "belko")', d)
print t1.timeit() # prints 6.502113536776391
짧막 한 농담
d = """\
from itertools import izip
def hamdist(s1, s2):
return sum(ch1 != ch2 for ch1, ch2 in izip(s1,s2))
"""
t2 = timeit.Timer('hamdist("hello", "belko")', d)
print t2.timeit() # prints 10.985101179
바로 가기 평가
d = """\
def distance_is_one(word1, word2):
diff = 0
for i in xrange(len(word1)):
if word1[i] != word2[i]:
diff += 1
if diff > 1:
return False
return diff == 1
"""
t3 = timeit.Timer('hamdist("hello", "belko")', d)
print t2.timeit() # prints 6.63337
차이가 2 이상이면 루프 브레이크를 시작할 수 있습니다.
또한 변경할 수 있습니다
for i in range(len(word1)):
에게
for i in xrange(len(word1)):
Xrange는 한 번에 전체 범위의 숫자를 생성하는 대신 주문시 시퀀스를 생성하기 때문입니다.
더 빠른 단어 길이를 비교할 수도 있습니다. 또한 Word1이 Word2보다 큰 경우 코드가 작동하지 않습니다.
그 후 알고리즘 적으로 할 수있는 것은 많지 않습니다. 즉, 해당 섹션을 C로 포팅하여 더 많은 속도를 찾을 수있을 것입니다.
편집 2
Char의 차이를 확인하는 것과 비교하여 Sumudu 알고리즘에 대한 나의 분석을 설명하려고 시도합니다.
길이 L의 단어가 있으면 생성 할 "하나의 다른"단어의 수는 25L입니다. 우리는 현대 컴퓨터에서 세트를 구현하여 검색 속도가 대략 로그 (n)베이스 2, 여기서 n은 검색 할 요소의 수입니다.
당신이 테스트하는 5 백만 단어의 대부분이 ~ 아니다 세트에서 대부분의 경우 전체 세트를 가로 지르며 실제로는 로그 (25L) 로그 (25L)/2 대신. (그리고 이것은 문자열별로 문자열을 비교하는 세트에 대한 최상의 사례 시나리오를 가정합니다.
이제 우리는 "하나의 다른"을 결정하기위한 시간 복잡성을 살펴 봅니다. 전체 단어를 확인해야한다고 가정하면 단어 당 작업 수가됩니다. 엘. 우리는 대부분의 단어가 2가 매우 빠르게 다르다는 것을 알고 있습니다. 그리고 대부분의 접두사가 단어의 작은 부분을 차지한다는 것을 알고, 우리는 당신이 대부분의 시간을 L/2, 또는 단어의 절반 (그리고 이것은 보수적 인 추정치입니다).
이제 우리는 두 개의 검색 인 L/2와 Log (25L)의 시간 복잡성을 계획하고 이것은 숯 일치와 같은 속도와 일치하는 문자열을 고려하고 있습니다. (세트에 유리하게). 방정식 로그 (25*L)> L/2가 있으며 로그 (25)> L/2 -LOG (L)까지 단순화 할 수 있습니다. 그래프에서 볼 수 있듯이 도달 할 때까지 숯 일치 알고리즘을 사용하는 것이 더 빠릅니다. 매우 많은 L.
또한 최적화에서 2 개 이상의 차이에 대해 계산하는지 모르겠지만 Mark의 답변에서 이미 2 개 이상의 차이를 깰 수 있습니다. 실제로 첫 글자의 차이가 있으면 It 첫 글자 이후에 휴식을 취하고 모든 최적화에도 불구하고 세트를 사용하는 것으로 바뀌면 물에서 날아갔습니다. 그래도 당신의 아이디어를 시도하는 데 관심이 있습니다
나는이 질문에서 2 개 이상의 차이를 깨는 것을 제안한 첫 번째 사람이었습니다. 문제는 그 마크의 문자열 슬라이스 (If Word1 [0]! = Word2 [0] : return Word1 [1 :] == Word2 [1 :])에 대한 아이디어가 우리가하고있는 일을 C에 넣는 것입니다. 생각한다 Word1 [1 :] == Word2 [1 : 계산 되었습니까? 우리가하는 것과 같은 방식.
나는 당신의 설명을 몇 번 읽었지만 그것을 따르지 않았습니다. 조금 더 독창적이라고 설명 하시겠습니까? 또한 나는 C에 크게 익숙하지 않으며 지난 몇 년 동안 고급 언어로 일해 왔습니다 (6 년 전 고등학교에서 C ++를 배우고 있습니다.
C 코드를 생산하는 것은 조금 바쁘다. 나는 당신이 전에 C로 작성한 이후로 당신이 그것을 할 수있을 것이라고 확신합니다. 유사한 성능 특성을 가진 C#을 시도 할 수도 있습니다.
더 많은 설명
다음은 Davy8에 대한 더욱 심각한 설명입니다
def getchildren(word, wordlist):
oneoff = one_letter_off_strings(word)
return set(oneoff) & set(wordlist)
One_letter_off_strings 함수는 25L 문자열 세트를 만듭니다 (여기서 L은 문자 수).
WordList에서 세트를 작성하면 D 문자열 세트가 생성됩니다 (여기서 D는 사전의 길이). 이것으로부터 교차로를 만들어 해야 하다 각각을 반복하십시오 일원 그리고 그것이 존재하는지 확인하십시오 단어 목록.
이 작업의 시간 복잡성은 위에서 자세히 설명되어 있습니다. 이 작업은 비교하는 것보다 덜 효율적입니다 단어 당신은 각 단어를 원합니다 단어 목록. Sumudu의 방법은 알고리즘보다는 C의 최적화입니다.
더 많은 설명 2
4500 개의 총 단어 만 있습니다 (단어 목록은 알고리즘에 전달되기 전에 5 개의 글자 단어에 대해 미리 필터링되기 때문에 125 개의 한 글자 오프 단어와 교차합니다. 교차로가 로그 (작은) 또는 다른 단어 로그 (125, 2)라고 말하는 것 같습니다. L/2 글자로 단어가 깨지는 것을 비교하는 곳에서 이것을 다시 비교하면 5 글자 단어의 경우 3 일 가능성이 높지만이 비교는 4500 번 이루어집니다. 로그 (125,2)는 약 6.9이고 로그 (4500,2)는 약 12입니다. lemme는 내가 당신의 숫자를 잘못 해석했는지 알고 있습니다.
4500 사전으로 125 개의 1 글자 오프 단어의 교차로를 만들려면 125 * 4500 비교를 만들어야합니다. 이것은 로그 (125,2)가 아닙니다. 사전이 사전이 선별되었다고 가정 할 때 가장 기껏해야 125 * log (4500, 2)입니다. 세트 할 마법 바로 가기가 없습니다. 당신은 또한 숯 비교 대신 문자열로 문자열을하고 있습니다.
그것이 당신의 속도에 크게 영향을 미칠지는 모르겠지만, 목록 이해력을 발전기 표현식으로 바꾸는 것으로 시작할 수 있습니다. 여전히 반복 할 수 있으므로 사용이 크게 다르지 않아야합니다.
def getchildren(word, wordlist):
return [ w for w in wordlist if distance(word, w) == 1 ]
에게
def getchildren(word, wordlist):
return ( w for w in wordlist if distance(word, w) == 1 )
주요 문제는 목록 이해력이 메모리에서 자체적으로 구성되어 상당한 공간을 차지할 것이라는 점입니다. 반면 발전기는 즉시 목록을 만들므로 모든 것을 저장할 필요가 없습니다.
또한, 미지의 답변에 따라, 이것은 더 "pythonic"방법 일 수 있습니다 () :
def distance(word1, word2):
difference = 0
for x,y in zip (word1, word2):
if x == y:
difference += 1
return difference
그러나 Len (Word1)! = len (word2)이있을 때 의도 한 내용을 혼란스럽게합니다. Zip의 경우 가장 짧은 단어만큼 많은 문자 만 반환합니다. (최적화로 판명 될 수 있습니다 ...)
이 시도:
def distance(word1, word2):
return sum([not c1 == c2 for c1, c2 in zip(word1,word2)])
또한 게임 링크가 있습니까? 나는 단어 게임에 의해 파괴되는 것을 좋아합니다
나에게 가장 먼저 일어날 일 :
from operator import ne
def distance(word1, word2):
return sum(map(ne, word1, word2))
사람들이 게시 한 다른 기능보다 더 빨리 갈 가능성이 높습니다. 루프가 해석되지 않고 Python Primitives를 호출하기 때문입니다. 그리고 발신자에 합리적으로 인라인을 인화 할 수있을 정도로 짧습니다.
높은 수준의 문제에 대해서는 메트릭 공간에서 유사성 검색을 위해 개발 된 데이터 구조를 살펴 보겠습니다. 이 종이 또는 이 책, 내가 읽은 어느 쪽도 (내가 읽은 논문을 찾아서 나왔지만 기억할 수 없음).
이 스 니펫의 경우 :
for x,y in zip (word1, word2):
if x != y:
difference += 1
return difference
나는 이것을 사용할 것이다 :
return sum(1 for i in xrange(len(word1)) if word1[i] == word2[i])
동일한 패턴이 제공된 코드 주변의 모든 것을 따를 것입니다 ...
다른 모든 사람들은 거리 1 후보를 구성하는 것에 대해 아무것도하지 않고 명시적인 거리 계산에 집중했습니다. 당신은 a라는 잘 알려진 데이터 구조를 사용하여 개선 할 수 있습니다 트리 병합 암시 적 거리-계산 작업과 함께 모든 거리 1 이웃 단어를 생성합니다. 트리는 각 노드가 문자를 나타내는 링크리스트이며, '다음'필드는 다음 노드를 가리키는 최대 26 개의 항목이있는 덕트입니다.
여기 유사 코드는 다음과 같습니다. 각 노드에서 모든 거리 -0 및 거리 1 이웃을 결과에 추가합니다. 거리의 카운터를 유지하고 줄이십시오. 재귀가 필요하지 않고 추가 거리 _so_far 정수 인수를 사용하는 조회 함수 만 있습니다.
O (N) 공간 증가에 대한 추가 속도의 경미한 트레이드 오프는 길이 3, 길이 -4, 길이 -5 등에 대한 별도의 시도를 구축하면 얻을 수 있습니다.
