在python中按一定顺序排列任务

Question

我有一个口述，描述了一堆工作，这些工作将按一定顺序处理：

jobs = {
"job_a": {"commands": ["ls -a", "echo $LANG"], "dependencies": []}
"job_b": {"commands": ["ps aux", "find -name xxx"], "dependencies": []}
"job_c": {"commands": ["umask", "cat yyy"], "dependencies": ["job_a"]}
"job_d": {"commands": ["kill -9 www", "sed zzz"], "dependencies": ["job_b", "job_c"]}
}

每个作业项中的依赖项列表决定了它们应该执行的顺序：例如job_d应该在job_b和job_c之后执行。你知道吗

我需要的是一个指示这些作业顺序的列表，在上面的示例中，该列表可以是

jobs_order = ["job_a", "job_b", "job_c", "job_d"]
# or 
jobs_order = ["job_a", "job_c", "job_b", "job_d"]
# or 
jobs_order = ["job_b", "job_a", "job_c", "job_d"]

最简单的方法是一遍又一遍地遍历jobs.items()列表，每次都将依赖项插入前面的位置。你知道吗

这里的工作岗位可能非常多。我们能用更小的空间和更短的时间做得更好吗？你知道吗

Answer 1

可能是这样的：

#!/usr/bin/env python3

from collections import defaultdict
from queue import SimpleQueue


def get_order(jobs):
    q = SimpleQueue()
    subtasks = defaultdict(list)
    n_deps = {}
    for key, job in jobs.items():
        dependencies = job.get('dependencies', [])

        n_deps[key] = len(dependencies)
        if len(dependencies) == 0:
            q.put(key)

        for parent in dependencies:
            subtasks[parent].append(key)

    order = []
    while not q.empty():
        job = q.get()
        order.append(job)
        for key in subtasks[job]:
            n_deps[key] -= 1
            if n_deps[key] == 0:
                q.put(key)

    return order


def main():
    jobs = {
        "job_d": {"commands": ["kill -9 www", "sed zzz"], "dependencies": ["job_b", "job_c"]},
        "job_c": {"commands": ["umask", "cat yyy"], "dependencies": ["job_a"]},
        "job_b": {"commands": ["ps aux", "find -name xxx"], "dependencies": []},
        "job_a": {"commands": ["ls -a", "echo $LANG"], "dependencies": []},
    }
    print(get_order(jobs))


if __name__ == '__main__':
    main()

输出：

['job_b', 'job_a', 'job_c', 'job_d']