-3

我正在寻找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

考虑序列中的顺序很重要。

目标是跟踪大量序列（可见、不可见）。

有没有人想法？

4

1 回答 1

0

您可以为此使用无限嵌套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: {}}}}

如果“序列的顺序很重要”是指添加序列的顺序，而不是序列中的顺序，则必须使用 acollections.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)
于 2017-02-13T16:38:14.807 回答