파이썬 - 트리 검색

Question

파이썬에서 가장 효율적인 트리 검색 구현을 찾고 있습니다. 트리 검색에 길이 n의 시퀀스를 지정하고 브랜치가 이미 생성되었는지 감지해야합니다. 그렇지 않은 경우 브랜치를 생성해야합니다.

예 :

I1 : 서열 1 0.89,0.43,0.28]

 0.89 check 
     | 
     0.43 check 
     | 
     0.28 check(last branch, last number of sequence == found) 

I2 : 서열 2 0.89,0.43,0.99]

 0.89 check 
     | 
     0.43 check 
     |           | 
     0.28 missing(Creating new branch)   0.99 

시퀀스 내의 순서를 고려하는 것이 중요합니다.

목표는 거대한 범위의 시퀀스 (보이는 보이지 않는)를 추적하는 것입니다.

누구 아이디어가 있으십니까?

Answer 1

여기에 무한대로 중첩 된 collections.defaultdict을 사용할 수 있습니다. 다음 함수는 defaultdict을 생성합니다. 요청 된 값이 없을 때마다 동일한 함수를 다시 호출하여 defaultdict을 무한대로 생성합니다.

import collections 
nested = lambda: collections.defaultdict(nested) 
dic = nested() 

이제는 중첩 된 기본값에 시퀀스를 추가 할 수 있습니다. 당신은 루프에서이 작업을 수행하거나, 반복적으로, 또는 단순히 reduce 사용할 수 있습니다

s1 = [0.89,0.43,0.28] 
s2 = [0.89,0.43,0.99] 

from functools import reduce # Python 3 
reduce(lambda d, x: d[x], s1, dic) 
reduce(lambda d, x: d[x], s2, dic) 

이후, dic는 다음과 같습니다

: (사실, 조금 다른 외모,하지만 또한 기능을 인쇄 할 경우에만 때문에 defaultdict의의 로 만들었습니다.)

{0.89: {0.43: {0.28: {}, 0.99: {}}}} 

---

"시퀀스의 순서가 중요하다"에 의해 당신은 시퀀스 내에서 시퀀스가 ​​추가되는 순서, 그리고 순서 을 의미하는 경우 대신 collections.OrderedDict을 사용해야합니다. 이 경우, 새로운 요소를 추가하는 것은 좀 더 복잡하지만 많지는 않습니다.

dic = collections.OrderedDict() 

def putall(d, s): 
    for x in s: 
     if x not in d: 
      d[x] = collections.OrderedDict() 
     d = d[x] 

putall(dic, s1) 
putall(dic, s2)