Python - Поиск дерева

Question

Я ищу наиболее эффективную реализацию поиска дерева в python. Я даю дереву поиск последовательности длины 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() 

Теперь вы можете добавить последовательности к вложенному defaultdict. Вы можете сделать это в цикле или рекурсивно, или просто использовать 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)