Issue
I am working out a puzzle given by office leads to work out a solution.
The puzzle is:
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.
The bare logic I have written below doesn't seem to be correct solution; I am little confused by process with different rate at which disk can get full.
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
Solution
Seems you wrongly understand memory consumption definition. Every process (with index i
) eats one byte more every d[i]
seconds, so it consumes k
bytes after k*d[i]
seconds. We can say that speed of memory consumption is 1/d[i] bytes/second
on the long time interval, but memory consumption rise is discrete.
time 0 di 2di 3di
mem 0 1 2 3
For example three processes with d = [1,3,2]
seconds/byte memory consumption depends on time as:
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
Memory occupied by every process rises step-by-step, but these steps arise on different moments of time (imagine stairs with uneven steps).
We can calculate memory consumption for any moment t - just sum memory for all processes
OverallMem(t) = t//d[0] + t//d[1] + t//[d[2]+...
where //
is integer division (div
, floor(t/d[i])
)
Simple way: calculate memory consumption using formula above for t=1, t=2, t=3...
and so on until it exceeds X. Works for small X but slow for large X. Python 3 example:
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
Because memory consumption is non-decreasing, we can apply binary search approach to find moment t
when OverallMem(t)
becomes larger than X
.
Starting conditions:
left border for binary search is 0
rought right border is X * Min(d[i])
More optimal left border proposed by @AJNeufeld: X//sum(1/v for v in lst)
.
Perhaps in this form: math.floor(x / sum(1/v for v in lst))
I hope that this clue is enough to elaborate solution
Answered By - MBo
0 comments:
Post a Comment
Note: Only a member of this blog may post a comment.