多个资源加载步骤有依赖关系时,关键并不只是哪个单项最慢。有些步骤可以并行,有些必须等待前置完成,最终耗时由最长依赖链决定。
先确定规则与输入
任务按零到七编号,依赖只从较小编号指向较大编号,因此没有环。每项成本固定,所有已满足依赖的任务可立刻并行;不限制同时执行数量,也不计调度开销。
八项成本[8, 6, 7, 2, 8, 8, 2, 6] 依赖边[先,后][[0, 2], [0, 5], [0, 7], [1, 4], [1, 7], [2, 5], [3, 6], [3, 7], [4, 7], [6, 7]]
逐项算出过程
任务0成本8,前置[],最早开始/结束[0, 8],最晚开始/结束[0, 8],余量0。
任务1成本6,前置[],最早开始/结束[0, 6],最晚开始/结束[3, 9],余量3。
任务2成本7,前置[0],最早开始/结束[8, 15],最晚开始/结束[8, 15],余量0。
任务3成本2,前置[],最早开始/结束[0, 2],最晚开始/结束[13, 15],余量13。
任务4成本8,前置[1],最早开始/结束[6, 14],最晚开始/结束[9, 17],余量3。
任务5成本8,前置[0, 2],最早开始/结束[15, 23],最晚开始/结束[15, 23],余量0。
任务6成本2,前置[3],最早开始/结束[2, 4],最晚开始/结束[15, 17],余量13。
任务7成本6,前置[0, 1, 3, 4, 6],最早开始/结束[14, 20],最晚开始/结束[17, 23],余量3。
理想完成时刻23,零余量任务[0, 2, 5]。这些时间来自所有依赖链,不能把可并行的八项成本简单相加当成总时长。
复核时看什么
先向前求每项最早开始与结束,再从总体结束时间向后求最晚允许时刻。最晚开始减最早开始是余量,余量为零的任务处在至少一条最长链上;可枚举全部依赖路径独立检查。
练习时可以先遮住结果,沿用相同输入独立记录中间状态,再逐项比较。发现不同后先定位最早分歧,确认边界包含方式、编号起点、更新顺序以及是否提前取整。最后结果一致也不表示每个中间步骤都正确,因此保留过程记录有助于看清原因。
适用范围
这里给出理想并行条件下的时间界限。真实加载受磁盘、网络、线程数等资源限制,可能比此更慢。余量为零也不意味着可以只优化这一个任务,最长链可能不止一条。
