如何在 python 中实现 makefile 风格的算法

Question

我正在用 python 实现一个声学特征提取系统，我需要实现一个 makefile 风格算法以确保特征提取系统中的所有块都以正确的顺序运行，并且不重复任何特征提取阶段。

该特征提取系统的输入将是一个图表，详细说明特征提取块之间的链接，我想根据该图表确定要运行哪些函数。

这种系统的一个例子可能如下：

            ,-> [B] -> [D] ----+
input --> [A]           ^      v
            `-> [C] ----+---> [E] --> output

函数调用（假设每个块X是一个output = X(inputs)形式的函数）可能类似于：

a = A(input)
b = B(a)
c = C(a)
d = D(b,c)  # can't call D until both b and c are ready
output = E(d,c)   # can't call E until both c and d are ready

我已经以字典的形式加载了函数图，每个字典条目的形式为 (inputs, function) ，如下所示：

blocks = {'A' : (('input'), A),
          'B' : (('A'), B),
          'C' : (('A'), C),
          'D' : (('B','C'), D),
          'output' : (('D','C'), E)}

我目前只是在 makefile 算法的作用上画一个空白确切地说，以及如何去实现它，我的 google-fu 在这里似乎也不是很有帮助。

Answer 1

拓扑排序

Answer 2

blocks 基本上是（非循环）依赖图的邻接列表表示。因此，为了获得处理块的正确顺序，您可以执行拓扑排序。

Answer 3

正如其他有用的回答者已经指出的那样，我追求的是 拓扑排序，但是我认为我的特殊情况更简单一些，因为函数图必须始终从输入开始并以输出结束。

所以，这就是我最终所做的（我稍微编辑了它以删除一些依赖于上下文的内容，所以它可能不完全正确）：

def extract(func_graph):
    def _getsignal(block,signals):
        if block in signals:
            return signals[block]
        else:
            inblocks, fn = func_graph[block]
            inputs = [_getsignal(i,signals) for i in inblocks]
            signals[block] = fn(inputs)
            return signals[block]

    def extract_func (input):
        signals = dict(input=input)
        return _getsignal('output',signals)

    return extract_func

所以现在我可以设置该函数

fn = extract(blocks)

并使用它多次我喜欢：

list_of_outputs = [fn(i) for i in list_of_inputs]

我可能还应该对循环进行一些检查，但这是另一天的问题。

Answer 4

对于包括 Python 在内的多种语言的代码，请尝试以下 Rosetta 代码链接：拓扑排序 和 拓扑排序/提取顶部项目。