I'm writing a Monte Carlo simulation in which I have to maintain a large collection of items. This collection contains a great many duplicates, and it will most likely be best to store some or all of these in the form of a number that records the number of duplicates, rather than storing each one individually. (The items are essentially strings, so they have a non-negligible memory cost.)
On each iteration I remove a random item from the collection, and possibly add one or two new items. Each item has a weight, and when sampling from the container it's important that the probability of drawing a given item is equal to its weight multiplied by the number of items of that type.
The items that get added on each iteration may or may not be duplicates of ones that are already in the container. The items will probably be roughly Pareto distributed, with a few items having loads of duplicates and many having none, but it's hard to tell in advance.
This seems like a fairly common thing to want to do, and it also seems not entirely trivial to do it efficiently. The obvious way is to store the items in some kind of hash table, pairing each with an integer representing its frequency. The problem is that then it's not very efficient to sample from the container, since you'd have to iterate over the items in an essentially random order.
On the other hand, if they were stored in something like a balanced binary tree then sampling would be very efficient. However, since the container's contents are changing on every update, this would involve rebalancing the tree all the time, which (at least if done in a naïve way) would be very inefficient.
It seems to me that I need a data structure has a trade-off between speed of sampling and speed of updating. Perhaps some kind of partially-sorted heap-like thing that can be re-sorted with a low average cost when only a few items have changed. But I don't know of such a structure.
If there is a standard algorithm / data structure for this purpose then what's it called? If there is there a readily available implementation in Python and/or C++ then that would be a huge bonus.
(Note that user thus spake a.k.
gave an elegant answer to the question in the non-weighted case, but I've realised that for my application, the weights are really necessary.)