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)