Problem: I need to sample from a discrete distribution built from specific weights, for example. {w1, w2, w3, ...} and, therefore, the probability distribution {p1, p2, p3, ...}, where pi = wi / (w1 + w2 + ...).
some of the wi change very often, but only a very low proportion of all wi. But the distribution itself, therefore, must be renormalized every time this happens, and therefore I believe that the Alias method does not work efficiently, because every time you need to build the entire distribution from scratch.
The method that I am considering now is a binary tree (heap method), where all wi are stored at the lowest level, and then the sum of each of the two at a higher level, etc. The sum of all of them will be at the highest level, which is also a normalization constant. Thus, to update the tree after changing wi, you need to make changes to log (n), as well as the same amount, to get a sample from the distribution.
Question:
Q1. Do you have a better idea on how to achieve this faster? Q2. The most important part: I'm looking for a library that has already done this.
Explanation: I did this myself a few years ago, creating a heap structure in a vector, but since then I have learned a lot of things, including detecting libraries (:)) and containers like a map ... Now I need to rewrite this code with a higher functionality, and I want to do it right this time:
so Q2.1 is a good way to make a C ++ map ordered and search not by index, but by the total amount of its elements (so we read, right? ..). (this is my current theory, how I would like to do it, but it should not be that way ...)
Q2.2 Maybe there is an even more pleasant way to do the same? I would believe that this problem is so frequent that I am very surprised that I could not find any library that would do this for me ...
, , - , , , ...
-z
: , , , , , .
Edit2: , , ...