3
\$\begingroup\$

I need to select "random" elements from a collection. Random is quoted because I must assign a weight to each element; elements with higher weights have a greater chance of being selected.

To achieve this, I wrote the classes described below. I'd like to have my code reviewed in order to feel more secure that it is working as intended*

Obs: I store the accumulated probabilities as a field, making the class non-static, because I often need to choose multiple items (always with replacement) from a given pair (items, weights); and performing all the checks / computations is costly.

By the way, I just asked this same question a few moments ago, but I was using floats (that ranged from 0 to 1 and had to sum to 1) to model the weights; and someone asked in a comment why not use ints... I scratched my head and rewrote the whole thing using ints; it made such a big difference (the code became far simpler and cleaner) that I decided to re-ask the question, but now using ints.

namespace Minotaur.Random {
    using System;
    using System.Linq;

    public sealed class BiasedOptionChooser<T> {
        private readonly T[] _options;
        private readonly int[] _weights;
        private readonly int _sumOfWeights;

        private BiasedOptionChooser(T[] options, int[] weights, int sumOfWeights) {
            _options = options;
            _weights = weights;
            _sumOfWeights = sumOfWeights;
        }

        public static BiasedOptionChooser<T> Create(T[] options, int[] weights) {
            if (options is null)
                throw new ArgumentNullException(nameof(options));
            if (weights is null)
                throw new ArgumentNullException(nameof(weights));
            if (options.Length != weights.Length)
                throw new ArgumentException(nameof(options) + " and " + nameof(weights) + " must have the same length.");
            if (options.Length == 0)
                throw new ArgumentException(nameof(options) + " can't be empty.");

            for (int i = 0; i < weights.Length; i++) {
                if (weights[i] <= 0)
                    throw new ArgumentException(nameof(weights) + " can't contain non-positive values.");
            }

            var optionsAndProbabilities = new (T option, int weight)[options.Length];
            for (int i = 0; i < optionsAndProbabilities.Length; i++)
                optionsAndProbabilities[i] = (option: options[i], weight: weights[i]);

            return FromWeightedOptions(optionsAndProbabilities);
        }

        private static BiasedOptionChooser<T> FromWeightedOptions((T option, int weight)[] weightedOptions) {
            var sortedWeightedOptions = weightedOptions
                .OrderBy(op => op.weight)
                .ToList();

            var options = new T[sortedWeightedOptions.Count];
            var weights = new int[sortedWeightedOptions.Count];
            var sumOfWeights = 0;

            /* option A, weight 10
             * option B, weight 10
             * option C, weight 30
             * 
             * weights are stored in this way
             * [10, 20, 50]
             * 
             * We then roll a dice between 0 and 50
             * if dice < 10, we choose option a
             * if dice < 20, we choose option b
             * else we chose option c
             */

            for (int i = 0; i < sortedWeightedOptions.Count; i++) {
                var (option, weight) = sortedWeightedOptions[i];

                sumOfWeights += weight;
                options[i] = option;
                weights[i] = sumOfWeights;
            }

            return new BiasedOptionChooser<T>(
                options: options,
                weights: weights,
                sumOfWeights: sumOfWeights);
        }

        public T GetRandomChoice() {
            var probability = ThreadStaticRandom.Int(
                inclusiveMin: 0,
                exclusiveMax: _sumOfWeights);

            // @Improve performance by utilizing BinarySearch
            for (int i = 0; i < _weights.Length - 1; i++) {
                if (probability < _weights[i])
                    return _options[i];
            }

            return _options[_options.Length - 1];
        }
    }
}

The code for the ThreadStaticRandom can be found here (another codereview post).

Usage example:

private CategoricalFeatureTest FromCategorical(CategoricalDimensionInterval cat) {
    var featureIndex = cat.DimensionIndex;

    var possibleValues = cat.SortedValues;
    var weights = new int[possibleValues.Length];

    for (int i = 0; i < weights.Length; i++) {
        var frequency = Dataset.GetFeatureValueFrequency(
            featureIndex: featureIndex,
            featureValue: possibleValues[i]);

        weights[i] = frequency;
    }

    var chooser = BiasedOptionChooser<float>.Create(
        options: possibleValues,
        weights: weights);

    var value = chooser.GetRandomChoice();

    return new CategoricalFeatureTest(
        featureIndex: cat.DimensionIndex,
        value: value);
}

Poorly-written test example

public static int Main(string[] args) {
    var total = 1000 * 1000 * 1000;
    var chooser = BiasedOptionChooser<char>.Create(
        options: new char[] { 'a', 'b', 'c' },
        weights: new int[] { 37, 13, 50 });


    var aCount = 0;
    var bCount = 0;
    var cCount = 0;

    for (int i = 0; i < total; i++) {
        var choosen = chooser.GetRandomChoice();
        if (choosen == 'a')
            aCount += 1;
        else if (choosen == 'b')
            bCount += 1;
        else if (choosen == 'c')
            cCount += 1;
        else
            throw new InvalidOperationException();
    }

    Console.WriteLine($"a ratio: {(double) aCount / total}");
    Console.WriteLine($"b ratio: {(double) bCount / total}");
    Console.WriteLine($"c ratio: {(double) cCount / total}");

    return 0;
}

Test output:

a ratio: 0.369988021
b ratio: 0.129995958
c ratio: 0.500016021

C:\Program Files\dotnet\dotnet.exe (process 8232) exited with code 0.
Press any key to close this window . .

.

*I'm also writing tests, but having others read and discuss the code is quite nice / reassuring.

\$\endgroup\$
  • 1
    \$\begingroup\$ I'm also writing tests, but having others read and discuss the code is quite nice / reassuring Feel free to include the unit tests you have written, that would also make it easier for us to verify your code :) \$\endgroup\$ – dfhwze Aug 28 at 4:47
  • 1
    \$\begingroup\$ Your tests would also help us to understand how you are going to use this and maybe try this out ourselfes. \$\endgroup\$ – t3chb0t Aug 28 at 5:47
  • 1
    \$\begingroup\$ Could you include ThreadStaticRandom? This one is missing. \$\endgroup\$ – t3chb0t Aug 28 at 5:51
  • \$\begingroup\$ @t3chb0t I have edited the question to include a link to ThreadStaticRandom \$\endgroup\$ – Trauer Aug 28 at 12:02
  • 1
    \$\begingroup\$ @dfhwze I added one of the tests I wrote and its outpout to the question. \$\endgroup\$ – Trauer Aug 29 at 13:30
4
\$\begingroup\$

I don't have a whole lot to say. It looks sound and is easy to read.

I'm not sure the big comment explaining how it works is necessarily in the right place, but that doesn't really bother me since the method is compact enough already.

API

It would be nice to provide a method like FromWeightedOptions as part of the public API. Personally I wouldn't use a tuple for the public part, but this would allow you to accept an IEnumerable/IReadOnlyList<WeightedChoice<T>> or something which would reduce the effort of using the type.

The validation in Create looks good, though you might want to provide the argument name to the ArgumentExceptions: it just makes it a little quicker to scan when it's thrown. One more thing worth checking is overflows: if the total weight is too large, then the class will fail in an unhelpful way.

Everything that should be hidden is hidden, and using ThreadStaticRandom it should work fine from multiple threads. I would really expect a class like this to take a Random instance in the constructor, but clearly you don't want this for your purposes, and I think providing both options in the exact same class would be a bad idea.

Inline documentation would of course be nice. The decision to not support zero-weight options seems fine to me (though I probably would if I were writing this for general use), but definitely needs to be documented.

Efficiency

There is no need to sort your options before building the data-structure. In fact, by sorting in ascending order, you are maximising the number of comparisons required to sample from choices with the linear scan, so if anything it is counter productive.

In case you are not aware, Array.BinarySearch is a thing, so it's little effort to make the sampling time complexity logarithmic in the number of choices.

An alternative method that will give you sort-of constant time sampling is the Alias Method. It's a Monte-Carlo method, so you can't know how many random number you will need to sample, but for very large collections it could be important.

Misc

  • You can simplify optionsAndProbabilities to optionsAndProbabilities = options.Zip(weight, (o, w) => (option: options[i], weight: weights[i])).ToArray() (or something like that, I haven't tested it)

  • I'd be inclined to remove _sumOfWeights from the constuctor: it's strictly redundant with the last element of weights, so I would just acquire it from there.

\$\endgroup\$
  • \$\begingroup\$ Removing sorting would change the behaviour because GetRandomChoice is falling back to max or last item when there was no hit. I think without sorting it would require to rework this method too which currently should be called GetRandomOrMax or GetRandomOrLast. \$\endgroup\$ – t3chb0t Aug 28 at 13:43
  • 1
    \$\begingroup\$ It's returning the last options (coincidentally the one with max chance) not because there's is no hit, but because it must me it, since it's not any of the other options. Notice that I'm not iterating over the entire array. \$\endgroup\$ – Trauer Aug 28 at 13:55
  • \$\begingroup\$ @Trauer yeah... I considered mentioning that: I'd probably prefer to remove the last-element special case, and instead throw if I exit the loop. That way if the loop is broken, the code throws instead of pretending it is still working. \$\endgroup\$ – VisualMelon Aug 28 at 14:15
  • \$\begingroup\$ But ._. isn't it guaranteed to work? If I'm generating a number between X and Y; am I not guaranteed that the number is between X and Y? \$\endgroup\$ – Trauer Aug 28 at 15:05
  • \$\begingroup\$ @Trauer if the code works, yes. But if someone comes along and breaks the code so that it no longer does so, the return at the end will quietly return the last entry. If instead you removed the special case and throw, the code will be simpler (so less likely to go wrong) and if the code is broken in such a way that it doesn't always return from within the loop, then it will throw and immediately tell you that it is broken. I don't think this is a very day/night matter, which is why I didn't put it in the answer, but I'd hope if I were writing the code I would go with the throw. \$\endgroup\$ – VisualMelon Aug 28 at 15:11
2
\$\begingroup\$

Addendum

I noticed VisualMelon also suggested this:

Personally I wouldn't use a tuple for the public part, but this would allow you to accept an IEnumerable/IReadOnlyList<WeightedChoice<T>> or something which would reduce the effort of using the type.

I would just like to express why I think this is an important point, both from the view as a consumer, and as a maintenance developer of the API.

Usability

As consumer of your API, I need to create two lists and have to manage that the items across lists are synchronized.

var chooser = BiasedOptionChooser<char>.Create(
    options: new char[] { 'a', 'b', 'c' },
    weights: new int[] { 37, 13, 50 });

In my object-oriented world, I would rather have related data grouped together in a class.

var chooser = BiasedOptionChooser<char>.Create(
    new[] { 
        new Option<char>('a', 37), 
        new Option<char>('b', 13), 
        new Option<char>('c', 50) });

Maintenance

As developer maintaining your code, I like the idea of this class Option. If ever we need to extend the functionality of the algorithm, we'd only have to add a property to the class, without having to change the signature! This makes versioning and handling compatibility issues easier.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.