在python中，有没有比标准的“递归”更快地从树型结构中获取子树的方法？

Question

假设下面的数据结构有三个numpy数组（id，parent_id）（根元素的parent_id是-1）：

import numpy as np
class MyStructure(object):
  def __init__(self):
    """
    Default structure for now:

          1
         / \
        2   3
           / \
          4   5
    """
    self.ids = np.array([1,2,3,4,5])
    self.parent_ids = np.array([-1, 1, 1, 3, 3])

  def id_successors(self, idOfInterest):
    """
    Return logical index.
    """
    return self.parent_ids == idOfInterest

  def subtree(self, newRootElement):
    """
    Return logical index pointing to elements of the subtree.
    """
    init_vector = np.zeros(len(self.ids), bool)
    init_vector[np.where(self.ids==newRootElement)[0]] = 1
    if sum(self.id_successors(newRootElement))==0:
      return init_vector
    else:
      subtree_vec = init_vector
      for sucs in self.ids[self.id_successors(newRootElement)==1]:
        subtree_vec += self.subtree(sucs)
      return subtree_vec

对于许多id（>；1000），此get非常慢。有没有更快的方法来实现这一点？在

Answer 1

理论上，每个算法都可以迭代编写，也可以递归编写。但这是一个谬论（就像图灵完全性）。在实践中，通过迭代遍历任意嵌套的树通常是不可行的。我怀疑有很多东西需要优化（至少你在适当的地方修改了子树）。在数千个元素上执行x是非常昂贵的，无论是迭代还是递归。在具体的实现上，最多可以进行一些微优化，最多可以获得5%的改进。如果您多次需要相同的数据，最好的选择是缓存/记忆。也许有人对你的特定树结构有一个奇特的O（logn）算法，我甚至不知道是否有可能（我假设没有，但树操作不是我的工作人员）。在

Answer 2

我认为不是递归本身伤害了你，而是每一步都有大量非常广泛的操作（覆盖所有元素）。考虑：

init_vector[np.where(self.ids==newRootElement)[0]] = 1

它对所有元素运行扫描，计算每个匹配元素的索引，然后只使用第一个元素的索引。这个特定的操作可以作为列表、元组和数组的方法索引，而且速度更快。如果id是唯一的，init_vector就是IDs==newRootElement。在

^{pr2}$

再次对每个元素进行线性扫描，然后对整个数组进行缩减，以检查是否存在匹配项。将any用于这种类型的操作，但我们再次重申，我们甚至不需要对所有元素进行检查-“如果newRootElement不在自父项_ID“可以，但这不是必需的，因为在空列表上执行for循环是完全有效的。在

最后一个循环是：

for sucs in self.ids[self.id_successors(newRootElement)==1]:

这一次，重复一个id\u后续调用，然后不必要地将结果与1进行比较。只有在这之后才进行递归，确保对每个分支重复上面的所有操作（对于不同的newRootElement）。在

整个代码是对单向树的反向遍历。我们有父母，需要孩子。如果我们要做像numpy这样的广泛的操作，我们最好让它们有价值——因此我们关心的唯一操作就是为每个家长建立一个子列表。一次迭代并不难做到：

import collections
children=collections.defaultdict(list)
for i,p in zip(ids,parent_ids):
  children[p].append(i)

def subtree(i):
  return i, map(subtree, children[i])

您需要的确切结构将取决于更多的因素，例如树的更改频率、大小、分支数量以及需要请求的子树的大小和数量。例如，上面的dictionary+list结构的内存效率并不高。您的示例也进行了排序，这将使操作更加容易。在

Answer 3

如果您使用的是python2.6，您是否尝试过使用psyco模块？它有时可以显著提高代码的速度。在

你考虑过递归数据结构：列表吗？在

您的示例也是标准列表：

[1, 2, [3, [4],[5]]]

或者

[1, [2, None, None], [3, [4, None, None],[5, None, None]]]

由我的pretty printer：

[1, 
  [2, None, None], 
  [3, 
    [4, None, None], 
    [5, None, None]]]

子树已经准备好了，需要花费一些时间将值插入到右树中。同样值得检查一下heapq module是否符合您的需要。在

另外，Guido自己也对http://python.org/doc/essays/graphs.html中的遍历和树给出了一些见解，也许您已经知道了。在

下面是一些看起来很高级的树，实际上是为Python建议的基本列表类型替换，但在该函数中被拒绝了。Blist module