Structured Chaos

[AngleWyrm]

Random Sorting Let's say we have a collection of things with a weight property and some other data. Perhaps that collection got loaded according to a mod list, so the sequence starts in unknown state. One method of returning a random weighted element from such a set is to make a speed/space trade-off: create an array that will contain only index references to the original set, and insert multiple references according to weight. So if the first item encountered in the data collection has a weight of ten, then insert ten index entries into the look-up collection that point to that first item.

During execution a look-up is very fast because it doesn't use any scan or looping mechanism:

index = lookupSet[ rng.next(0, lookupSet.Count-1) ]
sampleItem[ index ]

The number of entries in the look-up table is the total of the weights in the original table, and could be an effective speed gain for space cost where that total is measured in dozens to hundreds.

For situations that involve using up entries like drawing cards from a deck, even more optimization can be done by first shuffling the index set and then popping the first entry out of the index set any time one is needed. Then there's only one call to the rng, during the initial shuffle.