我有以下树形数据结构存储在字典中：
我希望遍历它并在到达每个叶子时进行一些计算。在进行计算时，我需要知道到叶子的路径。 即给定回调函数。
以下是我尝试过的方法: 1. 内联代码。 这是最快的方法，但在实践中不可用，因为树的深度不是静态的。
This runs 3.5 seconds average using Python 3.4.2 on my laptop.
2. 递归方法
这很通用，但速度慢了两倍！ 3. 非递归方法 我认为递归、
这是泛型方法，它可以工作，但与递归相比性能有所提升，即仍然比内联版本慢两倍。
那么如何以泛型方式实现我的遍历？内联版本为什么会快那么多？
附言：上面的代码适用于Python 3.3+。我已经改编成Python 2，结果类似。
解决方案和分析
我对所有解决方案和优化进行了比较分析。代码和结果可从 the gist获得。
简而言之，最快的解决方案是使用经过优化的基于循环的版本：
- 它是最快的支持从回调中方便地报告结果的版本 - 它只比内联版本慢30%（在Python3.4上） - 在PyPy上运行时，其速度得到了巨大的提升，甚至超过了内联版本
基于循环的迭代在PyPy上拥有一切。
在非pypy上，主要减速是由于从回调中报告结果：
1
2
3
4 -> ["a", "b", "c"]
5 -> ["x", "y", "z"]
3
5
7 -> ["e", "f", "j"]
以下是我在Python中构建其示例的方法：
tree = dict()
for i in range(100):
tree[i] = dict()
for j in range(10):
tree[i][j] = dict()
for k in range(10):
tree[i][j][k] = dict()
for l in range(10):
tree[i][j][k][l] = dict()
for m in range(10):
tree[i][j][k][l][m] = dict()
for n in range(10):
tree[i][j][k][l][m][n] = ["a", "b", "c", "d", "e", "f", "g"]
我希望遍历它并在到达每个叶子时进行一些计算。在进行计算时，我需要知道到叶子的路径。 即给定回调函数。
def callback(p1, p2, p3, p4, leaf):
...
我希望使用我的树示例，将它命名为以下方式：
callback(1, 2, 3, 4, ["a", "b", "c"])
callback(1, 2, 3, 5, ["x", "y", "z"])
callback(1, 3, 5, 7, ["e", "f", "j"])
以下是我尝试过的方法: 1. 内联代码。 这是最快的方法，但在实践中不可用，因为树的深度不是静态的。
def callback(*args):
assert isinstance(args[-1], list)
start = time.time()
for k1, leafs1 in tree.items():
for k2, leafs2 in leafs1.items():
for k3, leafs3 in leafs2.items():
for k4, leafs4 in leafs3.items():
for k5, leafs5 in leafs4.items():
for k6, val in leafs5.items():
callback(k1, k2, k3, k4, k5, k6, val)
print("inline: %f" % (time.time() - start))
This runs 3.5 seconds average using Python 3.4.2 on my laptop.
2. 递归方法
from functools import partial
def iterate_tree(tree, depth, callback):
if depth:
for k, subtree in tree.items():
cb = partial(callback, k)
yield from iterate_tree(subtree, depth-1, cb)
else:
for k, v in tree.items():
rv = callback(k, v)
yield rv
start = time.time()
for i in iterate_tree(tree, 5, callback):
pass
print("iterate_tree: %f" % (time.time() - start))
这很通用，但速度慢了两倍！ 3. 非递归方法 我认为递归、
yield from和partial可能会拖慢速度。所以我尝试将其扁平化：def iterate_tree2(tree, depth, callback):
iterators = [iter(tree.items())]
args = []
while iterators:
try:
k, v = next(iterators[-1])
except StopIteration:
depth += 1
iterators.pop()
if args:
args.pop()
continue
if depth:
args.append(k)
iterators.append(iter(v.items()))
depth -= 1
else:
yield callback(*(args + [k, v]))
start = time.time()
for i in iterate_tree2(tree, 5, callback):
pass
print("iterate_tree2: %f" % (time.time() - start))
这是泛型方法，它可以工作，但与递归相比性能有所提升，即仍然比内联版本慢两倍。
那么如何以泛型方式实现我的遍历？内联版本为什么会快那么多？
附言：上面的代码适用于Python 3.3+。我已经改编成Python 2，结果类似。
解决方案和分析
我对所有解决方案和优化进行了比较分析。代码和结果可从 the gist获得。
简而言之，最快的解决方案是使用经过优化的基于循环的版本：
- 它是最快的支持从回调中方便地报告结果的版本 - 它只比内联版本慢30%（在Python3.4上） - 在PyPy上运行时，其速度得到了巨大的提升，甚至超过了内联版本
基于循环的迭代在PyPy上拥有一切。
在非pypy上，主要减速是由于从回调中报告结果：
yield的结果最慢，比内联慢约30％。请参见iterate_tree6（循环版本）和iterate_tree3（递归版本）- 通过从回调中调用回调进行报告略好于内联 - 在Python3.4上比内联慢17％。请参见
iterate_tree3_noyield - 完全不报告可能比内联更好。请参见
iterate_tree6_nofeedback
对于基于递归的版本，请使用元组进行参数累积而不是列表。性能差异相当显着。
感谢所有为此主题做出贡献的人。
items()返回一份键值对的副本，而在Python 3中它返回一个“视图”，而不复制任何内容。 - jedwards