Suppose that we have this array of users' resources:
Array = [1, 5, 35, 40 ,100 ,80 ]
We map each number to the nearest power 2, we perform this operation
We apply the following function
MultiValueMap.put( 2 POW (log2 ( Array[i])) , Array[i] )
We will have 64 buckets for unsigned integer.
We perform the following operations
Map.put(1,1);
Map.put(4,5);
Map.put(32, 35);
Map.put(32, 40);
Map.put(64, 100);
Map.put(64, 80);
BucketList with a ListFor bucket number 0 => [ 1 ]
For bucket number 1 => []
For bucket number 2 => [ 5 ]
For bucket number 3 => []
For bucket number 4 => []
For bucket number 5 => [35, 40]
For bucket number 6 => [100, 80]
For bucket number 7 => []
For bucket number 8 => []
For bucket number 9 => []
.............................
Operations :
- use_resources(name, quantity) we just keep a hash between user and the object stored in the BucketList with a List
- get_approximate_max()
We have to find the first nonempty bucket and just perform a random on that set.
In this case as we find that bucket number 6 is not empty we could take either the 80 or the 100.
Because the maximum buckets' number is 64 or 32 I do not see the need for a binary search.
I have this idea because in the final round of Algoritmiada I saw a problem where I need to make a compression very fast but not a optimal compression and the solution was using power of 2.