在 Python 中将函数应用于树的所有元素

Question

有一个树状数据结构，其节点包含标量值（整数）、列表和字典、np.array。 我需要编写一个函数（在 Python 中），将聚合函数应用于树的较低级别，并用聚合结果替换较低级别。该函数的结果是一个新的数据结构。

示例。

Initial data structure: {“a”: [1, [2, 3, 4], [5, 6, 7]], “b”: [{“c”:8, “d”:9}, {“ e”:3, “f”:4}, 8]}
Aggregation function:   sum

First use:  {“a”: [1, 9, 18]], “b”: [17, 7, 8]}
Second use: {“a”: 28, “b”: 32}
Third use:  60
Fourth use: 60

Answer 1

sum

是一个特别简单的示例，因为您可以按任何顺序求和，并且始终会得到相同的结果。

例如，您可以首先使用深度优先搜索或广度优先搜索将树折叠成线性集合，然后对所有内容求和，您会得到相同的结果。

但是使用不同的聚合函数，事物的分组方式可能很重要。

我建议使用两个不同的函数，

collapse_then_aggregate

和

aggregate_recursively

，它们对于像

sum

这样的简单聚合函数返回相同的结果，但对于更复杂的聚合函数可以返回不同的结果。

注意

depth_first_search

和

aggregate_recursively

如何使用相同的逻辑通过对可迭代的每个元素进行递归调用来递归地遍历树。字典用

if isinstance(tree, dict)

单独处理，因为您关心的是值而不是键。可迭代对象使用 try/ except 进行处理。字符串也是可迭代的，但想必您不想迭代它们的单个字符，因此我编写了一个特殊情况

if isinstance(tree, (str, bytes))

，以便字符串不会被视为可迭代。

def depth_first_search(tree):
    if isinstance(tree, dict):
        for subtree in tree.values():
            yield from depth_first_search(subtree)
    elif isinstance(tree, (str, bytes)):
        yield tree
    else:
        try:
            tree_iter = iter(tree)
        except TypeError:
            yield tree
        else:
            for subtree in tree_iter:
                yield from depth_first_search(subtree)

def collapse_then_aggregate(f, tree):
    return f(depth_first_search(tree))

def aggregate_recursively(f, tree):
    if isinstance(tree, dict):
        return f(aggregate_recursively(f, subtree) for subtree in tree.values())
    elif isinstance(tree, (str, bytes)):
        return tree
    else:
        try:
            tree_iter = iter(tree)
        except TypeError:
            return tree
        return f(aggregate_recursively(f, subtree) for subtree in tree_iter)

应用示例：

from math import prod
from statistics import mean, geometric_mean

tree = {'a': [1, [2, 3, 4], [5, 6, 7, 8]], 'b': [{'c':8, 'd':9}, {'e':3, 'f':4}, 8]}

for f in (sum, prod, mean, geometric_mean, list):
    for fold in (collapse_then_aggregate, aggregate_recursively):
        result = fold(f, tree)
        print(f'{f.__name__:4.4}  {fold.__name__:23}  {result}')

结果：

sum   collapse_then_aggregate  68
sum   aggregate_recursively    68
prod  collapse_then_aggregate  278691840
prod  aggregate_recursively    278691840
mean  collapse_then_aggregate  5.230769230769231
mean  aggregate_recursively    5.083333333333334
geom  collapse_then_aggregate  4.462980019474007
geom  aggregate_recursively    4.03915728944794
list  collapse_then_aggregate  [1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 3, 4, 8]
list  aggregate_recursively    [[1, [2, 3, 4], [5, 6, 7, 8]], [[8, 9], [3, 4], 8]]

请注意

sum

和

prod

如何为我们的两种聚合方法提供相同的结果，但

mean, geometric_mean

和

list

给出不同的结果。