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: {}}}}

如果 "the order of the sequences is important" 是指序列添加的顺序，而不是在序列中的顺序，则必须使用 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)

Python - 树搜索

Python - Tree Search

sequence

tree-search