python之有没有比标准 "recursive"更快的方法从 python 中的树状结构获取子树

假设以下数据结构具有三个 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)，这个获取真的很慢。有没有更快的方法来实现它？

请您参考如下方法:

如果您使用的是 Python 2.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