3
\$\begingroup\$

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

That means: You've got some values and each of them has a priority (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 / (double)max calculations in RouletteWheelSelection and if the last x results of that calculation are all lower than 0.000..., then the max will be calculated again.

    /// <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 = new List<ValuePriorityPair<T>>(elements);
        var lastIndex = firstN < elements.Count() ? firstN - 1 : firstN - 2;
        for (int i = 0; i <= lastIndex; i++)
        {
            int randomIndex = RouletteWheelSelection(list, i, max);
            Swap(list, i, randomIndex);
        }

        return list;
    }

    private static void Swap<TEelment>(IList<TEelment> 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)
    {
        while (true)
        {
            var randomDouble = _rng.NextDouble();
            var randomIndex = _rng.NextInt(startIndex, pairs.Count);
            if (randomDouble <= pairs[randomIndex].Priority / (double)max)
                return randomIndex;
        }
    }
\$\endgroup\$
4
\$\begingroup\$

Without a doubt, RouletteWheelSelection could take a very long time, i.e. loop hundreds, thousands, or more times when you the max is very high. For a set like { 1_000_000_000, 1, 1, 1, 1, 1, 1, 1 } you have 7 elements with a Priority of 1, which means that randomDouble must be less than or equal to 0.000000001 for the method to return. So it might loop for a long time. And it would do it 7 times over. I can't help you with how you could improve that.

Other than that, you code is fairly easy to read with decent enough variable naming. There is a typo in Swap in that TElement is spelled wrong. The signature should be:

private static void Swap<TElement>(IList<TElement> elements, int index1, int index2)

In the Shuffle method, it sounds like your input collection may be small but there is some inefficiencies with it if you ever plan to have a large collection. Right off the bat, you make 2 or 3 full collection enumerations based on these lines:

var max = elements.Max(v => v.Priority);
var list = new List<ValuePriorityPair<T>>(elements);
var lastIndex = firstN < elements.Count() ? firstN - 1 : firstN - 2;

If your input is actually an IList<ValuePriorityPair<T>>, then elements.Count() will just provide the IList.Count. If you do not input a list or array, then Count() will enumerate over the full collection. Max() and well as defining a new List also enumerates over the whole collection. Worst case, is 2 times but it could be 3. And then later you loop over the collection up to firstN.

You could skip LINQ for the first 2 lines and loop once to both find max and add items to list. Then lastIndex could become:

var lastIndex = Math.Min(firstN, list.Count) - 1;

Observe this does 2 things differently. (1) It uses list.Count which does not require enumerating over the collection to perform the count, and (2) it clamps the end at list.Count just in case you input a firstN that is greater than list.Count.

VERY Minor things I would do differently regarding naming and types in RouletteWheelSelection. I would want max to accept a double in the signature rather than cast repeatedly in the while loop. And I would change the name pairs to be elements to be consistent with its usage elsewhere.

private int RouletteWheelSelection(IList<ValuePriorityPair<T>> elements, int startIndex, double max)

Again, those are very minor so take it with a grain of salt.

\$\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.