这是一个相当模糊的问题。
我有一个脚本执行的开始/停止时间列表,其中可能包括嵌套的脚本调用。
| script | start | stop | duration | time executing |
| ------ | ----- | ---- | -------------- | ----------------------------------- |
| A | 1 | 8 | 7 i.e. (8-1) | 3 i.e. ((8-1) - (6-2) - (5-4)) |
| ->B | 2 | 6 | 4 i.e. (6-2) | 3 i.e. ((6-2) - (5-4)) |
| ->->C | 4 | 5 | 1 i.e. (5-4) | 1 |
| D | 9 | 10 | 1 i.e. (10-9) | 1 |
| E | 11 | 12 | 1 i.e. (12-11) | 1 |
| F | 9 | 16 | 7 i.e. (16-9) | 5 i.e. ((16-9) - (14-13) - (16-15)) |
| ->G | 13 | 14 | 4 i.e. (14-13) | 1 i.e. (14-13) |
| ->H | 15 | 16 | 1 i.e. (15-14) | 1 i.e. (16-15) |
持续时间是在脚本中花费的总时间。 执行时间是在脚本中花费的时间,而不是在下标中花费的时间。
所以 A 调用 B,B 调用 C。C 需要 1 个滴答,B 需要 4 个但执行时间仅为 3,A 需要 7 个滴答,但执行时间为 3。 F 调用 G,然后调用 H,因此需要 7 个滴答,但执行时间仅为 5。
我正试图围绕我的(“流感缠身”)头脑是一个伪代码算法,用于逐步或递归遍历时间列表,以便为每一行生成时间执行值。
对于此问题(或普通感冒的治疗)的任何帮助,我们将不胜感激。 :-)
最佳答案
如果所有时间点都不同,则脚本执行时间跨度通过有序树相互关联:给定任何一对脚本执行时间跨度,其中一个严格包含另一个,或者它们根本不重叠。如果您想这样做,这可以轻松恢复亲子关系。
但如果您只关心执行时间,我们甚至不需要它! :) 有一个非常简单的算法,它只是对开始和结束时间进行排序,并遍历生成的“事件”数组,维护一个打开的“帧”堆栈:
- 创建一个
(time, scriptID)
的数组对,并将每个脚本的开始时间和结束时间插入其中(即,将每个脚本两对插入同一数组)。 - 按时间对数组进行排序。
- 创建一个整数三元组堆栈,并压入单个
(0, 0, 0)
进入它。 (这只是一个虚拟条目,以简化后面的代码。)同时创建一个数组seen[]
每个脚本 ID 都有一个 bool 标志,所有初始设置为false
. - 遍历
(time, scriptID)
的排序数组对:- 每当您看到
(time, scriptID)
对您以前没有见过的脚本 ID,该脚本正在启动。- 设置
seen[scriptID] = true
. - 推送三元组
(time, scriptID, 0)
到堆栈上。最后一个组件,最初为 0,将用于累积在此脚本的“后代”脚本中花费的总持续时间。
- 设置
- 每当您看到之前看到的脚本 ID 的时间(因为
seen[scriptID] == true
),该脚本就结束了。- 弹出顶部
(time, scriptID, descendantDuration)
堆栈中的三元组(请注意,此三元组中的 scriptID 应与数组当前索引处的对中的 scriptID 匹配;如果不是,则不知何故你有“相交”的脚本时间跨度,无法对应于任何嵌套脚本运行序列). - 此脚本 ID 的持续时间是(如您所知)
time - startTime[scriptID]
. - 它的执行时间是
duration - descendantDuration
. - 通过添加
duration
记录在此脚本及其后代中花费的时间到新的栈顶的descendantDuration
(即第三)场。
- 弹出顶部
- 每当您看到
就是这样!对于 n 个脚本执行,这将花费 O(n log n) 时间,因为排序步骤需要这么长时间(遍历数组并执行堆栈操作只需要 O(n))。空间使用量为 O(n)。
关于algorithm - 伪代码:递归处理列表中的开始/停止时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36689613/