计算 n 个进程下载到可用存储的磁盘已满时间

Question

我正在解决办公室领导给的难题，以找出解决方案。

谜题是：

n number of processes are running on the computer. They run forever, never die, and no new processes get spawned. Each process takes memory at a constant, individual rate - process p_i (with 0 <= i < n) consumes 1 byte after every d(p_i) seconds. The total amount of available disk space is denoted by X.

Calculate the time to fill up available storage in seconds.

我在下面写的基本逻辑似乎不是正确的解决方案；我对磁盘填满的不同速率的进程有点困惑。

number_of_processes = 3
available_storage = 6 # in bytes
write_speed_x = 1 #(byte/ p_i second)
write_speed_y = 3
write_speed_z = 2
timeTaken = 0

pr_i = [write_speed_x, write_speed_y, write_speed_z]

for i in pr_i:
    timeTaken += available_storage/i


print timeTaken

Answer 1

看来你对内存消耗的定义理解有误。每个进程（索引为 i）每 d[i] 秒多吃一个字节，因此它在 k*d[i] 秒后消耗 k 字节。我们可以说内存消耗的速度在很长的时间间隔上是1/d[i] bytes/second，但是内存消耗的增长是离散的。

time     0   di   2di   3di
mem      0    1    2     3

例如三个进程 d = [1,3,2] seconds/byte 内存消耗取决于时间：

 process  p0   p1  p2  overall
 time
 0         0   0   0   0
 1         1   0   0   1 
 2         2   0   1   3 
 3         3   1   1   5
 4         4   1   2   7  
 5         5   1   2   8  
 6         6   2   3   11

每个进程占用的内存都是一步一步上升的，但是这些台阶出现在不同的时刻（想象台阶不平整的楼梯）。

我们可以计算任何时刻 t 的内存消耗 - 只需对所有进程的内存求和

OverallMem(t) = t//d[0] + t//d[1] + t//[d[2]+...

其中 // 是整数除法 (div, floor(t/d[i]))

简单的方法：使用上面的公式为 t=1, t=2, t=3... 计算内存消耗，依此类推，直到它超过 X。适用于小 X 但适用于大 X。Python 3 示例：

def timetodie(lst, x):
    mem = 0
    t = 0
    while (mem < x):
        t += 1
        mem = sum(t//v for v in lst)
              #mem = 0
              #for v in lst:
                   #mem += t // v
    return t

print(timetodie([1,3,2], 6))
print(timetodie([2,5,7], 11))
>>4
>>14

因为内存消耗是非递减的，我们可以应用二分搜索方法来找到当OverallMem(t)大于[=26=时的时刻t ].

起始条件：
二进制搜索的左边界是 0
粗略的右边框是 X * Min(d[i])

@AJNeufeld 提出的更优左边框：X//sum(1/v for v in lst)。
也许是这种形式：math.floor(x / sum(1/v for v in lst))

我希望这个线索足以详细说明解决方案

计算 n 个进程下载到可用存储的磁盘已满时间

Calculating time to disk full for n processes downloading to available storage

python

algorithm

python-2.x