0

我正在创建一个公共时间范围的报告，其中所有给定的进程同时执行，我一直在做的是绘制图表并手动计算出来。现在我有更多的数据，绘制图表不会是最佳解决方案，作为计算机工程师，我想以编程方式解决这个问题，使用最佳和高效的算法。

所以问题基本上是，

每个N进程都有一个它已执行的时间范围列表，找到所有给定进程中所有公共时间间隔的最佳方法是什么。

例子：

假设有三个进程P1, P2, P3, 下表给出了每个进程的执行时间信息：

-|---------|--------------------|-
 | PROCESS |  TIME OF EXECUTION |
-|---------|--------------------|-
 |    P1   |   (0,4) , (5,10)   | **(updated from (0,1) , (5,10))
-|---------|--------------------|-
 |    P2   |   (0,6) , (1,8)    |
-|---------|--------------------|-
 |    P3   |   (3,10)           |
-|---------|--------------------|-

Y-axis如果我使用时间范围内的每个过程绘制图表，X-axis我可以得到如下所示的内容，并且公共范围以蓝色边框颜色突出显示。

表示过程与时间范围的图表 注意：P1 值为 (0, 4) 和 (5,10)

从图中，很明显输出/结果是[ (3, 4), (5, 8) ].

我正在寻找一种解决方案/算法来从给定的输入中推断出这些结果。我将不胜感激能够解决以下问题的答案：

  • 针对每个流程的大量流程和时间范围的通用理论解决方案。
  • 是动态规划问题吗？
  • 在这种情况下我可以使用任何算法吗？
  • 它类似于直方图中的最大矩形问题吗？
4

2 回答 2

2

这可以通过维护前缀和并检查其计数来解决。

但在此之前，您需要进行一些基本的预处理。

对于流程的每次执行，您需要合并重叠的间隔。

这是一个非常常见的算法，你可以查一下。

所以，在这一步之后，你的输入变成了，

-|---------|--------------------|-
 | PROCESS |  TIME OF EXECUTION |
-|---------|--------------------|-
 |    P1   |   (0,4) , (5,10)   |
-|---------|--------------------|-
 |    P2   |   (0,8)            |
-|---------|--------------------|-
 |    P3   |   (3,10)           |
-|---------|--------------------|-

因为P2我们在这里所做的是合并 (0,6) 和 (1,8) 并使其成为 (0,8)。

现在，下一步是计算前缀和的实际算法。

它以下列方式工作。

1. initialize a map
2. for each start_time,end_time.
      map[start_time++] and map[[(end_time+1)]--]

原因(end_time+1)是因为进程运行到 end_time。在此之后end_time，我们可以从我们的列表中删除它的计数。

所以，现在我们有了我们的价值观。

0 2
3 1
5 0
9 -1
11 -2

现在，我们可以开始计算前缀和。

为此，我们初始化一个计数器sum=0。并按排序顺序排列地图的键。

num_processes=3也被初始化了！`

at 0, val = 2 , sum =2 (!=3) .(start=-1 and end =-1)
at 3, val = 1,  sum =3 // intersection start (start=3, end=-1)
at 5, val = 0,  sum =3 (remains same) // intersection end and start new one (add (3,4) and (start=5,end=-1) 
at 9 , val = -1, sum = 2 // intersection end (add 5,8) (start=-1 and end =-1)
at 11, val = -2, sum = 0 // (start=-1 and end =-1)

添加(3,4),(5,8)到最终结果。

于 2021-04-28T04:12:07.547 回答
1

如果您有离散时间步长，您可以使用 2 遍方法生成一个包含 N 个时间步长的数组，其中 N 是您正在观看的时间长度除以时间步长（即，对于 1ms 周期，离散时间步长为 10us 将有 N=101) 然后遍历所有执行开始/停止对。每当进程启动时，将数组的该时间步加 1，每当进程停止时，从时间步减去 1。有些是负数，有些是正数，所有元素的总和应该为零。

接下来，创建一个整数，我们将其命名为 process_count。它从 0 开始。您遍历数组，每次都将值添加到 process_count。每当 process_count 等于将要运行的进程总数时，您就找到了您的矩形。

伪代码：

//Create empty array to store value
array = zeroes(N)

//Assign each timestep the net change in number of running processes
for(tuple in process_runtimes):
    array[tuple[0]] += 1
    array[tuple[1]] -= 1

//Create array to store periods of all programs being on, tuple for individual periods and flag for state machine processing
all_on_periods = []
current_tuple = (0, 0)
on_flag = 0
process_count = 0

//Iterate over array to calculate for each timestep the number of processes running.
for i in range(len(array)):
    process_count += val[i]
    
    //If all processes are running, create a tuple that tracks the beginning of the block where they are all running
    if(process_count == total_processes and on_flag == 0):
        on_flag = 1
        current_tuple[0] = i

    //Else, if all processes were running but aren't running any longer, enter the last timestamp they were all running on.
    elseif(process_count == total_processes and on_flag == 0):
        on_flag = 0
        current_tuple[1] = i - 1
        all_on_periods.append(current_tuple)

我不认为这是动态编程，但我不是这方面的权威。

虽然类似于最大直方图问题，但这也是相当不同的。这是关于二进制检查的并发性，而直方图问题是关于搜索矩形和比较大小。

于 2021-04-28T04:17:47.887 回答