Quantity allocation algorithm performance

Question

I have a scenario for which I'll take an analogous example to help understand better.

There are N buckets of known varying capacities. We have 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 where Bi and Ci is the current number of balls in the bucket and capacity of ith bucket 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?

Answer 1

You can optimize by only recalculating when you put a ball in a bucket. That means instead of M*N you have M+N calculations.

Of course this means you need memory to store the calculations. One for each bucket.

You could also optimize finding the lowest effect bucket by keeping them in a priority queue.