2

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?

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.