-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 回答