拓扑排序:先完成依赖,再启动任务¶
把一个依赖完成事件变成一次入度修改¶
数据和运行环境都准备好后才能训练,训练结束后才能评估。画箭头从每个前置任务指向训练,训练起初有两条箭头指进来。节点收到的箭头数叫**入度**。先完成运行环境,就划掉对应的一条箭头,计数由 2 变成 1。数据也完成后减到 0,才把训练加入存放可启动任务的**就绪队列**。按这种先后关系排出顺序,就叫**拓扑排序**。
若数据任务失败了,可以照样减 1 吗?
如果依赖要求成功,不能把失败算作满足。执行器需要单独处理重试、取消或向后传播失败。
读完能做:从依赖关系找出当前可运行的任务,检查有没有一组任务沿着依赖箭头最终又绕到自身(形成**环**)。
假设有四项工作:下载数据 D、打包程序运行环境(构建镜像)I、训练 T 和评估 E。T 等 D 和 I,E 等 T。把边画成「前置任务 → 后续任务」,就有 D → T、I → T、T → E。拓扑序只要求每条边的起点出现在终点之前,所以 D、I、T、E 与 I、D、T、E 都合法。
从入度推导算法¶
用入度记录每项任务还有多少前置任务。先把所有入度为零的任务放进队列。每取出一个任务,就把它的每个直接受它影响的后续任务(后继)的剩余计数减 1,减到零就加入队列。可以用邻接表让每个任务记录自己有哪些后继。
| 已取出 | 接下来可取 | 原因 |
|---|---|---|
| 无 | D、I | 两者都无需等待 |
| D | I | T 还缺 I |
| D、I | T | T 的两个依赖都已结束 |
| D、I、T | E | E 的依赖已结束 |
只要有任何任务未输出、队列却为空,只看剩下的任务,每项就都还在等其中另一项(前驱)。一路倒着追「它在等谁」,任务数有限,迟早会追到见过的点,找到一圈互相等待的依赖。若有 \(V\) 项任务和 \(E\) 条依赖,算法只扫描节点和边各一遍,时间 \(O(V+E)\),计数表与队列占用 \(O(V)\) 额外空间。
从顺序过渡到运行¶
拓扑排序给出合法顺序。真正负责启动任务并处理结果的程序叫作**执行器**。它在前置任务成功结束后,才更新后续任务的等待计数。任务刚启动时,后继仍需等待。就绪集合中还要考虑可用 GPU、任务优先级和重试策略,两个都就绪的任务也可能同时运行。
自测¶
如果增加 E → I,算法最初还能取出谁?最后打印出的序列意味着什么?
参考思路
D 仍然没有入边,可以先取出。I、T 和 E 仍各自依赖环里的另一个任务,队列变空时只输出了 D,说明整张图不能拓扑排序。