Как я могу реализовать алгоритм в стиле make-файла в Python

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)}

Я сейчас только рисуюбланк о том, что именно делает алгоритм make-файла и как его реализовать. Мой google-fu, кажется, не очень полезенздесь тоже.Если кто-то хотя бы может дать мне указание на хорошее обсуждение алгоритма make-файла, это, вероятно, будет хорошим началом.

Answer 1

Топологическая сортировка

Answer 2

Для кода на многих языках, включая Python, воспользуйтесь следующими ссылками кода Rosetta: Топологическая сортировка и Топологическая сортировка / Извлеченный верхний элемент .

Answer 3

Как уже отметили другие полезные авторы, мне нужна топологическая сортировка , но я думаю, что мой конкретный случай немного проще, поскольку график функции всегда должен начинаться с input и заканчивается в output.

Итак, вот что я в итоге сделал (я немного отредактировал это, чтобы удалить некоторые контекстно-зависимые вещи, так что это может быть не совсем правильно):

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

blocks является в основном представлением списка смежности (ациклического) графа зависимостей. Следовательно, чтобы получить правильный порядок обработки блоков, вы можете выполнить топологическую сортировку.