在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个）时，这个处理速度会变得很慢。有没有更快的方法来实现这个呢？

Answer 1

理论上，每个算法都可以用循环的方式和递归的方式来写。但这其实是个误区（就像图灵完备性一样）。在实际操作中，通过循环来遍历一个任意嵌套的树结构通常是不可行的。我怀疑能优化的地方不多（至少你是在原地修改子树的向量）。对成千上万的元素做某件事本身就是非常耗费资源的，无论你是用循环还是递归。最多也就是在具体实现上做一些微小的优化，这样的优化最多也只能提高不到5%。如果你需要多次使用相同的数据，最好的办法是使用缓存或记忆化。也许有人对你特定的树结构有个很炫的O(log n)算法，但我甚至不知道是否可能（我猜不太可能，因为树的操作不是我的强项）。

Answer 2

我觉得问题不在于递归本身，而是在每一步都要对所有元素进行很多宽泛的操作。想想看：

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

这段代码会遍历所有元素，计算每个匹配元素的索引，然后只使用第一个匹配的索引。这个操作在列表、元组和数组中都有提供，使用起来更快。如果ID是唯一的，init_vector实际上就是ids==newRootElement。

if sum(self.id_successors(newRootElement))==0:

又是对每个元素进行线性扫描，然后对整个数组进行归约，只是为了检查是否有匹配项。对于这种操作，可以使用any，但我们其实不需要检查所有元素——“if newRootElement not in self.parent_ids”就能完成这个工作，而且在空列表上使用for循环也是完全可以的。

最后是最后一个循环：

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

这次，id_successors的调用被重复了，然后结果不必要地与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])

你需要的确切结构会依赖于更多因素，比如树的变化频率、大小、分支情况，以及你需要请求的子树的大小和数量。例如，上面的字典+列表结构在内存使用上并不是特别高效。你的例子也是有序的，这可能会让操作变得更简单。

Answer 3

你有没有试过在使用Python 2.6时用psyco模块？这个模块有时候能让代码运行得快很多。

你有没有考虑过使用递归数据结构，比如列表？

你的例子其实也是一个标准的列表：

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

或者

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

通过我的美化打印工具：

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

子树已经准备好了，插入值到正确的树里会花费一些时间。还值得检查一下heapq模块是否符合你的需求。

而且Guido本人在http://python.org/doc/essays/graphs.html中也提供了一些关于遍历和树的见解，也许你已经知道了。

这里有一些看起来比较复杂的树结构，实际上是作为Python的基本列表类型替代方案提出的，但在那个功能上被拒绝了。Blist模块