16.3　综合项目：一个任务调度器

学习目标：学完本节，你能

• 把拓扑排序、优先队列、哈希表三块拼成一个可运行的项目；
• 说清"换个容器"在真实系统里的双重含义（既定顺序，也定快慢）；
• 用四项验收检查验证一个调度器的正确性，而不是"看着对"；
• 认出贪心调度的局限，并说清"求最优"和"给个能用的解"之间的取舍。

先修：13.1（拓扑排序）、11.4（优先队列）、第 6 章（哈希表）、16.1–16.2。 固定术语：拓扑排序、入度、优先队列、哈希表、贪心算法。 环境与版本：.NET 8 / C# 12。 预计阅读：60 分钟。

一、需求与约束

这是全书的最后一节，也是唯一一个"从零做东西"的节。

需求：写一个任务调度器。

给它一批任务，每个任务有：

• 一个优先级（数字越大越该先做）
• 一串依赖（这些任务必须【先】完成）

要求输出一个执行顺序，满足：

1. 每条依赖都被满足（前置任务排在前面）
2. 每个任务恰好执行一次
3. 在【当前所有能做的任务】里，永远挑优先级最高的那个
4. 如果依赖里出现环，要能检测出来并报错

小陈一眼就认出了这个问题的两个部分：

这一节没有什么新知识 —— 它要做的是把三块已有的东西拼起来，并且证明它真的对。

二、设计：把 Kahn 的队列换成优先队列

回忆 13.1 节的 Kahn 算法：

  1. 统计每个顶点的入度
  2. 把所有入度为 0 的顶点放进【队列】
  3. 反复：出队一个，输出它，把它的邻居入度减 1，减到 0 的入队

那个"队列"里装的是什么？

"当前所有前置任务都已完成的任务" —— 也就是此刻可以开始做的任务。

而需求第 3 条要求：在这个集合里，永远挑优先级最高的。

所以改动只有一处：

13.1 节说过："Kahn 换个容器就换个输出顺序" —— 当时换的是队列 / 栈 / 最小堆， 那是一次"为了看差别"的实验。

这一节是这个结论的落地：换成优先队列，输出顺序就从"随便一个合法顺序"变成了"业务真正要的顺序"。

三个结构的职责分工：

注意前两项都是哈希表 —— 因为任务的名字是字符串，不是整数下标。

这正是 6.4 节提醒过的：字符串键比 int 键慢 7.84 倍。 如果性能真的吃紧，第一步就该把任务名映射成整数 ID。

三、核心代码

调度主循环：

var ready = new PriorityQueue<string, (int, string)>();   // 键是 (-优先级, 名字)

// 初始化：所有没有依赖的任务都就绪
foreach (var job in _jobs)
    if (job.DependsOn.Length == 0)
        ready.Enqueue(job.Name, (-job.Priority, job.Name));

var order = new List<string>();
while (ready.Count > 0)
{
    var name = ready.Dequeue();          // ★ 取优先级最高的
    order.Add(name);

    foreach (var next in _dependents[name])       // 解锁它的后继
        if (--_remaining[next] == 0)              // 入度归零
            ready.Enqueue(next, (-_priority[next], next));
}

和 13.1 的 Kahn 对照着看：

只有容器换了，骨架一模一样。

那个 (-优先级, 名字) 的元组键值得说一句：PriorityQueue 是最小堆， 所以优先级要用负数（越大越先出）；再加上名字做次键， 是为了"优先级相同时结果也确定" —— 否则两次运行可能给出不同顺序（16.1 节踩过这个坑）。

四、实测一：跑通一个构建系统，并验收

场景：一个小构建系统，8 个模块：

    utils     优先级 5  依赖 []
    core      优先级 8  依赖 [utils]
    db        优先级 6  依赖 [utils]
    api       优先级 9  依赖 [core, db]
    ui        优先级 3  依赖 [core]
    docs      优先级 1  依赖 []
    tests     优先级 7  依赖 [api, ui]
    package   优先级 2  依赖 [tests]

调度结果：

    utils -> core -> db -> api -> ui -> tests -> package -> docs

这个顺序对吗？ 肉眼检查一遍：

• utils 最先 ✓（它是 core/db 的前置）
• core、db 都在 api 前面 ✓
• api、ui 都在 tests 前面 ✓
• docs 排最后 —— 它没有依赖，优先级又最低（1），所以一直被压着 ✓

看起来对。但"看起来对"不是验收。

四项验收检查

    [1] 每个任务恰好执行一次：True
    [2] 所有依赖都被满足（前置任务都排在前面）：True
    [3] 每一步执行的都是「当前可执行任务里优先级最高的」：True
    [4] 没有环（任务全部被调度完）：True

四项检查分别是怎么做的：

第 [3] 项是本节最值得学的验收方式：

它没有去"看"输出序列（那样只能靠人眼判断）， 而是【用一个独立的实现，把规则重新检查一遍】。

这就是本书从 12.3 节开始的"独立实现交叉校验" —— 240 组暴力验证、Floyd-Warshall 对拍、 暴力枚举对拍……同一个手法，用在了这里。

有环的情况：

    调度器返回的剩余任务：[a, b, c]
    判定有环：True

注意这里返回的是"剩余的任务"，不是"环上的任务" —— 13.1 节实测过：这两者不是一回事（剩余集合包含"被环挡住的下游"）。

要精确报出环，得用 12.4 节的三色标记。

五、实测二：换个容器，差 108 倍

如果把优先队列换回"线性扫描"（每次遍历整个就绪集合找最大的），会怎样？

规模：10 万个任务，其中 5000 个是"源头"（没有任何依赖）。

为什么要特意造 5000 个源头？ 因为就绪集合的大小决定了这个对比的结论 —— 后面会看到，这是本节最实用的一条。

    实现                        耗时        调度结果
    ------------------------    ---------   --------
    优先队列（堆）                 74.0 ms   100,000 个任务
    线性扫描（每次找最大）       8009.1 ms   100,000 个任务

  两者结果一致：True
  堆版比扫描版快 108.2 倍

108 倍 —— 而两段代码的调度逻辑一个字没改，只是换了个容器。

为什么差这么多？

扫描版每执行一个任务，要做两件 O(就绪集合大小) 的事：

1. 扫一遍就绪集合，找优先级最大的 —— $O(k)$
2. 从列表中间删掉它 —— 也是 $O(k)$（数组搬移）

而堆版这两件事都是 $O(\log k)$。

累计 $n$ 个任务，扫描版是 $O(n \cdot k)$，堆版是 $O(n \log k)$ —— 比值约 $k / \log k$。

当 $k = 3000$ 左右时，$k / \log k \approx 3000 / 11.5 \approx 260$ —— 量级对得上实测的 108 倍（实际就绪集合不是恒定的 5000）。

但这条结论有个前提

如果图是一条链（每个任务只有一个后继），就绪集合始终只有 1 个 —— 两种写法的耗时几乎一样。

所以"该不该上堆"取决于【就绪集合有多大】，而不是【任务总数有多少】。

这个前提值得单独强调，因为它和 16.1 节那条规矩对得上：

16.1 节说"复杂度说明趋势，实测才是当前答案"； 这里更进一步：连"哪个复杂度成立"本身都取决于数据的形状。

换个说法：

六、实测三：贪心调度的局限

"每次挑当前优先级最高的"是一个贪心算法 —— 而第 14 章讲过，贪心要满足两个前提。

先检查这两个前提：

"贪心选择性质"说的是：每一步的局部最优选择，一定属于某个全局最优解。

构造一个反例：

    key (优先级 5)  <- 无依赖，但它是下面三个的前置
    hot1/hot2/hot3 (优先级 100)  <- 都依赖 key
    solo (优先级 6) <- 无依赖

注意 key 的优先级（5）比 solo（6）低一点点，但它是三个高优先级任务的共同前置。

实测（目标：加权完成时间 $\sum(\text{优先级} \times \text{完成序号})$ 最小）：

  贪心调度：solo -> key -> hot1 -> hot2 -> hot3
    加权完成时间 = 1216

  暴力枚举全部合法顺序里的最优：key -> hot1 -> hot2 -> hot3 -> solo
    加权完成时间 = 935

  贪心比最优差 1.30 倍

贪心错在哪？

第 1 步可执行的是 {key(5), solo(6)}，贪心选了 solo —— 因为 6 > 5，这个判断本身没错。

但它没看到：key 一旦做完，会【同时解锁三个优先级 100 的任务】。

为了那 1 点优先级的便宜，它把三个 100 都往后推了。

这正是 14.1 节说的"贪心选择性质不成立"：

那该怎么办？

先看清楚这个问题的性质：

带依赖的加权调度问题，求全局最优是 NP 难的。

也就是说：不存在多项式时间的精确算法。

所以工程上的做法不是"换个更聪明的贪心"，而是：

这一条是全书最后一次出现"取舍"这个主题 ——

1.3 节说"SLA 按最坏情况定"，16.1 节说"n 不大时可读性更值钱"， 这里说"NP 难时接受启发式但要说明"：

工程决策从来不是在"对"和"错"之间选，而是在"代价不同的几个可行解"之间选。

七、验收标准清单

把这个项目"做完"的标准，不是"能跑"，而是这五条：

  [ ] 1. 功能正确
        · 每个任务恰好执行一次
        · 所有依赖都被满足
        · 每一步都取当前就绪集合里优先级最高的
  [ ] 2. 异常可控
        · 有环时检测出来并报错（而不是死循环或给出残缺结果）
        · 依赖了不存在的任务时有明确行为
  [ ] 3. 性能达标
        · 用 16.2 的七步清单测（预热、多轮取最快、报告分配量、报告区间）
        · 明确写清【测的是什么形状的图】—— 因为结论依赖图的结构
  [ ] 4. 边界清楚
        · 空任务集、单个任务、全是源头、一条长链 —— 都试过
  [ ] 5. 局限写明
        · 文档里写清"这是启发式，不保证全局最优"

第 5 条最容易被跳过，也最容易被误解成"自曝其短"。

它不是。它是在给下游的人一个正确的预期 ——

14.1 节说过"贪心的错误是静默的"：一个不说明局限的实现， 会让使用者以为它是精确的，然后在某个输入上悄悄给出次优解。

八、练习

练习 16.3.1（改需求） 给调度器加一条新需求："如果两个任务优先级相同，先做【能解锁更多任务】的那个"。

(a) 这需要改哪里？优先队列的键要怎么变？ (b) 用实验三那个反例验证：加上这条规则后，贪心还能得到最优解（935）吗？ (c) 这条规则能保证所有输入上都最优吗？

练习 16.3.2（判断） 判断对错并说明理由：

(a) 这个调度器用的是 Kahn 算法，只是把队列换成了优先队列。 (b) 因为用了优先队列，所以它保证"总完成时间最短"。 (c) "就绪集合的大小"不影响"该用堆还是用扫描"这个决定。 (d) 有环时返回的"剩余任务"就是"环上的任务"。

练习 16.3.3（挑战·把项目做完） 真实需求往往更复杂。选一个方向扩展这个调度器，并说明它需要哪块新知识：

(a) 任务有耗时，多个任务可以并行执行（有 N 个工人），求最短总工期。 (b) 任务会失败，失败后要重试，且重试时要跳过依赖它的任务。 (c) 任务可以在运行时动态添加（比如构建过程中发现了新的依赖）。

九、练习答案

16.3.1

(a) 只改优先队列的键。

现在的键是 (-优先级, 名字)，改成 (-优先级, -解锁数, 名字)：

// 预先算好每个任务的"出度"（它解锁多少个任务）
// 键：(负优先级, 负解锁数, 名字)
ready.Enqueue(job.Name, (-job.Priority, -_dependents[job.Name].Count, job.Name));

注意加了第三项"名字" —— 否则两个任务优先级和解锁数都相同时，结果又不确定了（16.1 的教训）。

(b) 能。

用实验三那个反例验一遍：

• 第 1 步就绪集合是 {key(5, 解锁3), solo(6, 解锁0)}
• 按新规则：先比优先级，solo(6) > key(5) —— 还是选 solo ✗

等等 —— 这条规则救不了它！

因为"解锁数"是【次键】，只在优先级相同时才起作用。 而 solo 的优先级（6）本来就比 key（5）高。

所以要让这条规则生效，得改成【主键】按"解锁数"，或者用一个综合分数：

// 综合分数：优先级 + 解锁数 × 权重
ready.Enqueue(name, (-(job.Priority + _dependents[name].Count * 10), name));

这样 key 的分数是 5 + 3×10 = 35，solo 是 6 + 0 = 6 —— key 胜出 ✓

但"权重取 10"是我拍的。换个图、换个权重，可能又不对了。

(c) 不能。

这就是"启发式"的本质：没有一条固定的规则能保证在所有输入上都最优 —— 因为这个问题是 NP 难的。

任何"看起来能补救"的规则，都只是在【某个方向】上更接近最优， 同时可能在另一个方向上更远。

这道题的真正价值是让人亲身体会"NP 难"意味着什么：

不是"我想不出好算法"，而是"没有多项式时间的精确算法存在" —— 所以策略只能是：接受次优，并且说清它次优。

16.3.2

(b) 是本节最容易搞混的一条： "每次挑当前最优的"是【局部】规则，"总完成时间最短"是【全局】目标 —— 中间隔着一个第 14 章讲了一整章的鸿沟。

16.3.3

(a) 并行调度（N 个工人，求最短总工期）

需要的新知识：关键路径法（CPM）。

为什么不能直接用本节这套：

本节假设"一次只能做一个任务"，所以执行顺序就是完成顺序。 一旦允许多个任务同时跑，"第几个完成"就不再是执行序号了 —— 每个任务的完成时刻 = 它的前置全部完成的时刻 + 它自己的耗时。

这需要：在拓扑序上做一遍递推（本质上是 15.2 节的 DP）：

$$完工[v] = \max_{u \in \text{前置}(v)} 完工[u] + 耗时[v]$$

最短总工期 = 所有任务完工时刻的最大值 —— 这条最长的链叫"关键路径"。

(b) 失败重试

需要的新知识：不需要新算法，但需要重新定义"状态机"。

关键点：一个任务失败了，它的所有下游都不能做 —— 这等价于"把那个任务及其下游从图里删掉"，用 DFS 标记一遍就行（12.2 节的骨架）。

注意"状态"从 4 个变成了 6 个 —— 这正是 15.2 节第一问的又一次应用： "我需要的状态够吗？"

(c) 运行时动态添加任务

需要的新知识：增量拓扑排序。

难点：

本节的做法是"先算一遍全图，再开始调度" —— 图变了就得重算。

如果新任务频繁加入，重算的代价是 $O(V+E)$ 每次 —— 可能无法接受。

增量算法要处理的是：新加一条边之后，只更新受影响的那部分（通常是"这条边的两端在拓扑序里的位置"）。

工程上的简化做法：把新任务插入到"当前调度位置之后" —— 如果它能被排在那里，就不用重算；如果它的依赖还没做完，就退化成一次局部重排。

十、常见错误

十一、本节总结

1. 这个调度器没有新算法 —— 它是 Kahn（13.1）+ 优先队列（11.4）+ 哈希表（第 6 章）的拼装。
2. 唯一的改动：把 Kahn 的队列换成优先队列 —— 骨架一模一样，容器换了，输出顺序就从"随便一个合法序"变成"业务要的序"。
3. 实测一：8 个模块的构建系统跑通，四项验收全过（每个任务一次 / 依赖满足 / 优先级规则 / 无环）。 第 [3] 项验收用"独立实现重放规则"完成 —— 这是全书贯穿的交叉校验手法。
4. 实测二（本节最有力的一条）：10 万任务、5000 个源头 —— 堆版 74.0 ms vs 扫描版 8009.1 ms，差 108.2 倍。 调度逻辑一个字没改，只换了容器。
5. 但这条结论有前提：差距取决于【就绪集合有多大】 —— 链状图上两者没差别，源头多的图上差两个数量级。
6. 实测三："每次挑当前优先级最高的"是贪心，不保证全局最优 —— 贪心 1216 vs 最优 935（1.30 倍）。原因：为了 1 点优先级，把三个 100 推到了后面。
7. 而这个问题（带依赖的加权调度）求最优是 NP 难的 —— 所以工程做法是"接受启发式 + 在文档里写清它不最优"。
8. 验收清单五条：功能正确 / 异常可控 / 性能达标（按 16.2 的清单测）/ 边界清楚 / 局限写明。

全书结语

63 节写完了。 最后不再逐章复述，只说贯穿全书的三条主线 —— 它们在第 1 章埋下，在每一章被验证，在这里收束。

主线一：大 O 不等于实际性能

这本书里出现了 25 处"实测和教科书说法不符"的结论，其中一大半都是这一条的不同面貌：

复杂度告诉你"规模涨上去之后谁会被甩开" —— 它不告诉你"现在谁快"。

而"现在谁快"由常数因子决定：缓存、分支预测、JIT、GC。

所以本书从 1.1 节起就定了一条规矩：结论必须实测，而且要说清怎么测的。 这条规矩最后在 16.2 节被整理成一份七步清单。

主线二：换容器，换的是能力

这本书里最重要的几个算法，本质上都是"换个容器"：

  BFS        —— 队列
  0-1 BFS    —— 双端队列        （能表达的代价从"1 种"变成"2 种"）
  Dijkstra   —— 优先队列        （变成"任意非负代价"）
  Bellman-Ford —— 干脆不用容器  （能处理负权、能检测负环）
  Kahn 拓扑排序 —— 队列换成优先队列（从"随便一个序"变成"业务要的序"）
  0/1 背包    —— 内层循环反向    （同一份代码，从"完全背包"变成"0/1 背包"）

每换一次容器，能表达的东西就宽一档，代价是复杂度升一档。

16.3 节把这个规律用到了极致：调度逻辑一个字没改，只换了容器，快了 108 倍。

主线三：错误常常是静默的

这条主线最容易被忽略，但可能最有用。

会崩溃的 bug 一小时内就会被发现；静默出错的算法可能要等几个月。

这就是为什么本书花了那么多篇幅在" 怎么验证（12.3 的 240 组暴力对拍、13.3 的 Floyd-Warshall 对拍、16.3 的四项验收）"上 —— 因为对这类错误，"看着对"是没用的。

你现在能做什么

回到全书开头列的五个目标，逐条对照：

接下来学什么

这本书砍掉的东西，按"值得接着学的顺序"排：

但比"学什么"更重要的是保持这本书的习惯：

每写一个算法，问自己三个问题：

1. 它的复杂度是多少？（趋势）
2. 它在这个规模、这种数据上实际多快？（实测）
3. 如果它错了，会怎么错？会报错，还是静默地给出次优解？（边界）

全书完

最后一句留给小陈。

他在第 1 章问的是："为什么同样的功能，换个写法能差 8.5 万倍？"

现在他能自己回答了：

因为"换个写法"换掉的往往是数据结构 —— 而不同的结构，把不同的操作做成了 $O(1)$、$O(\log n)$ 或 $O(n)$。

而更要紧的是第二层：他还知道，这个答案本身也得实测过才算数。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "16.3",
  "title": "综合项目：一个任务调度器",
  "covered": [
    "需求与约束（优先级 + 依赖 + 状态跟踪 + 环检测）",
    "设计：Kahn 的队列换成优先队列；三块结构的职责分工",
    "核心代码与 13.1 节 Kahn 的逐行对照",
    "实测一：8 模块构建系统跑通 + 四项验收检查（含「独立实现重放规则」的手法）",
    "实测二：10 万任务、5000 源头 —— 堆版 74.0 ms vs 扫描版 8009.1 ms（108.2 倍）",
    "「差距取决于就绪集合大小」这一前提（链状图上无差别）",
    "实测三：贪心调度 1216 vs 最优 935（1.30 倍），NP 难与启发式的取舍",
    "五项验收标准清单",
    "全书结语：三条主线（大 O ≠ 实际性能 / 换容器换能力 / 错误常常是静默的）",
    "五个学习目标的自查对照",
    "六个后续学习方向的推荐"
  ],
  "unresolved": [
    "并行调度（关键路径）未展开",
    "增量拓扑排序未展开",
    "并查集、字符串算法、A*、计算复杂性等留在「接下来学什么」",
    "本节的调度器是启发式，不保证全局最优（已在正文与练习中说明）"
  ],
  "canonical_terms": {
    "基于优先队列的拓扑排序": "把 Kahn 算法的队列换成优先队列，得到「每次取当前可执行任务中优先级最高」的调度顺序",
    "加权完成时间": "Σ(优先级 × 完成序号)，衡量一个调度顺序好坏的指标"
  },
  "symbols_units": {
    "V": "任务数",
    "E": "依赖边数",
    "k": "就绪集合的大小"
  },
  "assumptions": [
    "读者已掌握 13.1 的 Kahn 算法、11.4 的优先队列、第 6 章的哈希表",
    "读者理解 16.2 的测量清单与噪声区间规则",
    "任务之间没有并行（一次只做一个），耗时不计"
  ],
  "word_count_actual": 3911,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑（AMD Ryzen 7 9700X），输出见正文",
    "项目文件：99-tools/samples/Ch16/Sec163/",
    "实验一：8 模块调度结果 utils -> core -> db -> api -> ui -> tests -> package -> docs，四项验收全 True，为实测",
    "实验一：三任务成环时返回剩余 [a, b, c] 并判定有环，为实测",
    "实验二：10 万任务（5000 源头）堆版 74.0 ms vs 扫描版 8009.1 ms（108.2 倍），两者结果一致，为实测",
    "实验三：贪心 1216 vs 暴力枚举最优 935（1.30 倍），为实测",
    "第 [3] 项验收（优先级规则）用独立实现重放调度过程，不依赖被测代码"
  ],
  "known_issues": [
    "实验二初版用「链式 + 随机补边」生成图，就绪集合长期只有几十个，堆版只快 1.1 倍（在噪声范围内），完全没有演示出「换容器」的价值 —— 改为「前 5000 个任务作为源头」，就绪集合维持在几千，差距变成 108.2 倍",
    "扫描版在改造后的图上要跑 8 秒，5 轮取最快会让程序跑近一分钟 —— 把扫描版的轮数从 5 降到 3",
    "初版把所有类型声明（enum JobState / class Scheduler）放在了局部函数之前，触发 CS8803（顶级语句必须位于类型声明之前）—— 已把类型声明整体移到文件末尾",
    "练习 16.3.1(b) 初版以为「按解锁数排序」能救回那个反例，写答案时发现【次键】只在优先级相同时才生效，而 solo 的优先级本来就更高 —— 保留了这个「发现自己想错」的过程，并指出必须改成主键加权才有效（而加权值又是拍脑袋的）"
  ],
  "next": "（全书完）"
}