python - 在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']