I have a scenario for which I'll take an analogous example to help understand better.
There are N buckets of known varying capacities.
M balls that we need to put in these buckets to fill them fully or partially. The existing algorithm works as below:
For each bucket calculate the fraction
effect = (Bi + 1)/Ci
Ci is the current number of balls in the bucket and capacity of
respectively. Identify the bucket with the lowest effect and put a ball in it taking from M. Repeat the above process until there are no balls left(
M=0) or all buckets are filled to the capacity.
The above algorithm produces the desired output but it has performance issues when there are a large number of buckets and many balls to allocate.
The inner loop must run
M * N to allocate all the balls.
I tried optimizing it by allocating the balls in bulk to each bucket. The new approach is as below:
For each bucket, do this:
calculate the difference(no. of balls short of full capacity)
Di = Ci - Bi.
calculate the no. of balls to put in bucket as
Mi = (Di * M)/S where S is sum of differences(D1+D2....Dn) for all buckets.
Although, its much faster but results are not the same as the previous approach especially in case there are insufficient balls to fill all buckets.(i.e M < S)
Can anyone suggest an algorithm that is almost independent of
M and produces the same output as the original approach that allocates one ball at a time?