I'd like a data structure with the following operations:
- create a new instances from an array of floating point weights.
- randomly sample, returning an item with probability proportionate to its weight.
- set the weight of a specific item to 0.
Without the third option this is pretty standard: Just implement an alias method sampler using Vose's algorithm, but the ability to do a dynamic update makes it harder.
The first operation is intrinsically O(n) (or at least it is if you don't make the second operation O(n)), but it would be nice to be able to do the other two in amortized O(1), or at least O(log(n)). Sampling will be significantly the more common operation, so ideally I would like to have it not be much slower (either in complexity or constant factors) than using the alias method.
One option is to just rebuild the sampler every time you do a remove, but that's O(n) which is less than ideal.
The following is currently my best bet, which builds on that to amortise it a bit:
We keep a copy of the set of weights, and build an alias method sampler initially. When we set the weight of an item to zero we update our weights table appropriately. Then when we sample from our alias table, we check the weight. If it's zero then we rebuild the alias table with the updated weights and draw again.
This should work OK for amortising some of the cost, but unfortunately the workload I'm likely to want to put it through is probably pessimal for it: Items that are going to be removed will have been drawn from the sampler, so will tend to be of high weight. This means that it will end up hitting the rebuild case fairly commonly.
So I'm hoping for something better. Any suggestions?