Carey Brown wrote:It seems that your cumulative weights, to work properly, would need the initial Map of weights in increasing weight order. Correct? Otherwise it would seem like your "cumulativeWeight" would have large jumps and gaps.
Carey Brown wrote:I see "cumulativeWeight" as "a" way of distributing keys on a floating point scale. I could see using some function f(w) that might compute a weight key based on some formula, e.g. squared(w).
Carey Brown wrote:The scenarios I've imagined, e.g. playlist, should have unique keys but the value, the weight, is probably not unique for a number of different scenarios. In which case it seems like you wouldn't want to accumulate duplicate weights and for the current cumulativeWeight key the value would need to be a List<T>.
Carey Brown wrote:Thanks for your effort it gave me a new way to view the problem.
Mike Simmons wrote:
Carey Brown wrote:The scenarios I've imagined, e.g. playlist, should have unique keys but the value, the weight, is probably not unique for a number of different scenarios. In which case it seems like you wouldn't want to accumulate duplicate weights and for the current cumulativeWeight key the value would need to be a List<T>.
No, the cumulative weight, always increasing, will be unique as long as the individual weights are positive.
There are three kinds of actuaries: those who can count, and those who can't.
Carey Brown wrote:Here's a possible reason for keeping a List<T> for each unique weight (assuming duplicate weights would appear often otherwise).
Here the while loop will repeat until the set has been completely filled. For a very large amount of data waiting for random numbers to hit all the slots may take a while. Whereas with fewer slots and each slot manages a List<T> it's not a big deal.
Mike Simmons wrote:The new version periodically recalculates the map in order to get rid of all the entries for elements that have already been chosen. It's a tradeoff, but I think it's worth it.
In this example B & C would be in a list under weight '1'. So retrieving the next element involves two random numbers, the first selects a random weight from the TreeMap as you already have laid out. This gets you to a list of one or more elements all of the same weight where you use a second random number to get to a specific element in the list while also removing it from the list.Mike Simmons wrote:On the other hand... this comment makes me wonder if I've misunderstood your requirements. If you have a list of elements with the same priority, once you chose that list, do you need to keep everything in the list together in the shuffle? So if you have
A -> 10
B -> 1
C -> 1