0

I wrote a prioritized/weighted left shuffle algorithm (the code is copied from my open source C# project Fluent Random Picker).

What does that mean? You've got some values and each of them has a priority/weight (a number). The higher the priority is, the higher are the chances of the value being far on the left after the shuffle.

The algorithm pretty much runs in linear time. It works with "stochastic acceptance" (see method RouletteWheelSelection).

But: It can get slower if one or multiple priorities are much higher than others. E.g. (1.000.000.000, 1, 1, 1, 1, 1, 1, 1). Why? Because the max is only calculated once (see first line in Shuffle) and calculating it n time would make the performance worse.


Any ideas for improvements? The best solution would be an always O(n) algorithm that can run in parallel, but especially the "parallel" part is probably not possible.

Idea 1: Using this O(n) algorithm to get the max values of some intervals (e.g. in an array with 1.000 priorities I get the largest value, the 100th largest, the 200th largest, ... and the 900th largest) in the beginning and keep track of them to be able to replace one max priority with the next one as soon as there is no priority higher than the next one remaining.

Idea 2: Keeping track of the pairs[randomIndex].Priority / castedMax calculations in RouletteWheelSelection and if the last n results of that calculation are all lower than 0.000..., then the max will be re-calculated.

Idea 3: If n values need to be picked: Find out the nth highest value (possible in O(n), see idea 1) and the total max value. If max divided through the nth highest value is > some number (e.g. 10.000), use a different implementation (maybe this O(n * log(n)) implementation).

My code so far:

    /// <summary>
    /// Shuffles the first n elements and respects the probabilities in O(n) time.
    /// </summary>
    /// <param name="elements">The elements (value and probability) to shuffle.</param>
    /// <param name="firstN">Limits how many of the first elements to shuffle.</param>
    /// <returns>The shuffled elements.</returns>
    public IEnumerable<ValuePriorityPair<T>> Shuffle(IEnumerable<ValuePriorityPair<T>> elements, int firstN)
    {
        var max = elements.Max(v => v.Priority);

        var list = elements.ToList();
        var lastIndex = Math.Min(firstN, list.Count) - 1;
        for (int i = 0; i <= lastIndex; i++)
        {
            int randomIndex = RouletteWheelSelection(list, i, max);
            Swap(list, i, randomIndex);
        }

        return list;
    }

    private static void Swap<TElement>(IList<TElement> elements, int index1, int index2)
    {
        var tmp = elements[index1];
        elements[index1] = elements[index2];
        elements[index2] = tmp;
    }

    private int RouletteWheelSelection(IList<ValuePriorityPair<T>> pairs, int startIndex, int max)
    {
        var castedMax = (double)max;
        while (true)
        {
            var randomDouble = _rng.NextDouble();
            var randomIndex = _rng.NextInt(startIndex, pairs.Count);
            if (randomDouble <= pairs[randomIndex].Priority / castedMax)
                return randomIndex;
        }
    }
4
  • did you try implementing using a tree with aggregations? look at the following implementation generacodice.com/en/articolo/2544892/…
    – Ron Klein
    Commented Dec 19, 2021 at 12:12
  • I find your algorithm RouletteWheelSelection counter intuitive. If there is 98 items with PRiority 1 and 1 item of priority 2, I would expect the priority 2 item to be picked first in 2% of the cases. Your algorithm picks that item in 50% of the cases. Do you want to keep that property or are you happy with any algorithm that fulfills the requirement "The higher the priority is, the higher are the chances of the value being far on the left after the shuffle."
    – Helena
    Commented Dec 19, 2021 at 12:50
  • 1
    @Helena, no, it does not pick it in 50% of the cases. There are 2 phases during the Roulette wheel selection. Phase 1: Pick one random element. The priorities don't matter in this phase. So the probability to "select" a particular element is 1.010101%. In the second phase, we find out if we REALLY want to accept it. The 'if' returns true in this case because any _rng.NextDouble() is lower than 2/2 = 1. So the chances stay at 1.010101% to pick element nr. 99 in the first iteration and 49.494949% to pick any other (in the first iteration) and 50% to go into the next while iteration.
    – hardfork
    Commented Dec 19, 2021 at 14:12
  • @RonKlein "did you try implementing using a tree with aggregations" I've just done it differently. Also O(n*log(n)), but via sorting and it's only a few lines: github.com/ndsvw/Fluent-Random-Picker/blob/main/…
    – hardfork
    Commented Dec 23, 2021 at 14:25

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.