伪代码:递归处理列表中的开始/停止时间
伪代码:递归处理列表中的开始/停止时间
提问于 2016-04-18 09:03:15
这是一个相当模糊的问题。
我有一个脚本执行的开始/停止时间列表，其中可能包括嵌套的脚本调用。
| 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次。
我试图将我(“流感肆虐”)的头绕在一起的是一种伪代码算法，用于按步骤或递归地遍历时间列表，以便为每一行生成执行时间值。
对此问题的任何帮助(或治疗普通感冒)都很感激。:-)
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-04-18 13:03:05
如果所有的时间点都是不同的，那么脚本执行时间盘是通过一个有序的树相互关联的:给定任何一对脚本执行时间pair，要么其中一个严格包含另一个，要么它们根本不重叠。如果您想这样做，这可以轻松地恢复父子关系。
但是，如果您只关心执行时间，我们甚至不需要这样做！:)有一个非常简单的算法，只对开始和结束时间进行排序，并遍历生成的“事件”数组，维护一堆打开的“框架”：
- 创建一个
(time, scriptID)对数组，并将每个脚本的开始时间和结束时间插入到其中(即在同一个数组中插入每个脚本两对)。 - 按时间对数组进行排序。
- 创建一个整数三元组，并在其上推送一个
(0, 0, 0)条目。(这只是一个简化以后代码的虚拟条目。)还创建一个数组seen[]，每个脚本ID都有一个布尔标志，所有这些都最初设置为false。 - 迭代
(time, scriptID)对的排序数组：- 每当您看到一个您以前没有见过的脚本ID的
(time, scriptID)对时，该脚本就会启动。- 设置
seen[scriptID] = true。 - 将三重
(time, scriptID, 0)推到堆栈上。最后一个组件，最初为0，将用于累积此脚本的“后代”脚本中的总持续时间。
- 设置
- 每当您看到一个您以前没有见过的脚本ID的
- Whenever you see a time for a script ID that you have seen before (because `seen[scriptID] == true`), that script is ending.
- Pop the top `(time, scriptID, descendantDuration)` triple from the stack (note that the scriptID in this triple should match the scriptID in the pair at the current index of the array; if not, then somehow you have "intersecting" script timespans that could not correspond to any sequence of nested script runs).
- The duration for this script ID is (as you already knew) `time - startTime[scriptID]`.
- Its execution time is `duration - descendantDuration`.
- Record the time spent in this script _and its descendants_ by adding its `duration` to the new top-of-stack's `descendantDuration` (i.e., third) field.
就这样!对于n个脚本执行，这将花费O(n log )时间，因为排序步骤需要花费很长时间(迭代数组和执行堆栈操作只需要O( n) )。空间使用是O(n)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/36689613
复制相关文章
相似问题
腾讯云开发者
