在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

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

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结构的内存效率并不高。您的示例也进行了排序，这将使操作更加容易。在