Randomness Algorithms: Fisher–Yates Shuffle, Reservoir Sampling, Weighted Random and Random.Shared, Shuffle, GetItems in .NET

Version note: The code in this post was built with .NET 10, C# 14 and System.IO.Hashing 10.0.15 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8.

Guess First

Bookstore, the online bookstore used as the shared example across this site's series, shows the "recommended books" list on the home page in shuffled order. There are two proposals in code review. The first swaps every position with a random position of the array:

for (int i = 0; i < items.Length; i++)
{
    int j = random.Next(items.Length);
    (items[i], items[j]) = (items[j], items[i]);
}

The second is one line: Array.Sort(items, (_, _) => random.Next(-1, 2)). If we shuffle A, B and C 600,000 times, each of the six orders should come out at about 16.7 percent. Which one achieves that: both, one, or neither?

Fisher–Yates and Why It Is Correct

// Fisher-Yates (Durstenfeld): walk from the end, swap i with a random index in [0, i]
public static void FisherYates<T>(Span<T> items, Random random)
{
    for (int i = items.Length - 1; i > 0; i--)
    {
        int j = random.Next(i + 1);
        (items[i], items[j]) = (items[j], items[i]);
    }
}

Fisher and Yates described this method in 1938 for statistical tables, done with pencil and paper; Richard Durstenfeld published the O(n) version for computers in 1964. The idea: one of the remaining n elements is chosen with equal probability for the last position, then the same is repeated for the remaining n−1 elements. There are n·(n−1)·…·1 = n! equally likely paths in total, and exactly one path leads to each permutation. I measured it together with the two proposals from the opening:

Fisher-Yates     ABC=16.7% ACB=16.6% BAC=16.8% BCA=16.6% CAB=16.6% CBA=16.6%
naive swap       ABC=14.8% ACB=18.5% BAC=18.5% BCA=18.6% CAB=14.8% CBA=14.9%
OrderBy(Guid)    ABC=16.5% ACB=16.8% BAC=16.6% BCA=16.7% CAB=16.7% CBA=16.7%
random comparer  ABC=29.6% ACB=14.8% BAC=14.9% BCA=7.4% CAB=14.8% CBA=18.5%
Random.Shuffle   ABC=16.7% ACB=16.6% BAC=16.7% BCA=16.7% CAB=16.7% CBA=16.7%

The answer: neither. The only difference in the first proposal is that j is chosen from the whole array, and the reason for the bias is arithmetic: 3 choices at each of 3 steps, 27 equally likely paths in total; 27 does not divide evenly among 6 permutations, so some orders come from 4 paths and some from 5 (4/27 = 14.8 percent, 5/27 = 18.5 percent). The comparer that answers at random is even worse: ABC 29.6 percent, BCA 7.4 percent. A sorting algorithm assumes comparisons are consistent; as we saw in the ninth post of this series, an inconsistent comparer produces wrong results without an error. Here the "wrong result" is the bias itself.

OrderBy(_ => Guid.NewGuid()) is evenly distributed in this measurement; giving every element a random key and sorting is a correct method. It still has two problems: it costs O(n log n) and allocates a key for every element; and the documentation of Guid.NewGuid promises uniqueness, not a statistical distribution. According to the runtime source, Random.Shuffle, which came with .NET 8, is the front-to-back version of Fisher–Yates: for every i it picks an index from [i, n).

The cost of shuffling 100,000 ints; absolute times depend on the machine, look at the ratios:

| Method          | N      | Mean        | Ratio | Allocated |
|---------------- |------- |------------:|------:|----------:|
| FisherYatesOurs | 100000 |    475.0 us |  1.00 |         - |
| RandomShuffle   | 100000 |    482.2 us |  1.02 |         - |
| OrderByGuid     | 100000 | 25,942.6 us | 54.63 | 2803943 B |

Our own Fisher–Yates and Random.Shuffle are the same; both work in place and allocate nothing. OrderBy(Guid) is 55 times slower and allocates 2.8 MB. In production, Random.Shared.Shuffle is enough.

GetItems and Sampling from a Stream

Alongside Random.Shuffle, .NET 8 also brought Random.GetItems: it picks a requested number of elements from a list. According to the runtime source, GetItems picks every position independently, so the same element can come more than once (with replacement). For "pick 3 different books out of 10", GetItems is not the right tool; shuffle a copy and take the first 3, or run Fisher–Yates for only 3 steps.

What if the source is a stream rather than an array? You want 5 sample lines from a 5-million-line log file, you can read the file once, and you do not know the number of lines in advance. Reservoir sampling solves this; the version below appears as Algorithm R in Vitter's 1985 paper:

// Algorithm R: keep the first k; the i-th item (0-based) replaces a random slot with probability k / (i + 1)
public static T[] Sample<T>(IEnumerable<T> source, int k, Random random)
{
    ArgumentOutOfRangeException.ThrowIfLessThan(k, 1);
    T[] reservoir = new T[k];
    long seen = 0;
    foreach (T item in source)
    {
        if (seen < k)
        {
            reservoir[seen] = item;
        }
        else
        {
            long j = random.NextInt64(seen + 1);
            if (j < k) reservoir[j] = item;
        }

        seen++;
    }

    return seen >= k ? reservoir : reservoir[..(int)seen];
}

sample: line 33162 | line 1452813 | line 2891061 | line 582690 | line 3648131

Memory is O(k), time is O(n), and every line has a k/n probability of being in the sample; that is shown by induction, and the test takes 3 samples from a 10-element stream 30,000 times and verifies that each element is chosen about 9,000 times. How IEnumerable<T> and yield return keep the stream from ever being loaded into memory is the subject of the C# Collections series post "C# Collection Interfaces: IEnumerable, ICollection, IList and yield return".

Weighted Selection: The Book of the Day

The "book of the day" on the home page should be chosen by campaign priority, not with equal probability: Dune 50 percent, Emma 30 percent, Middlemarch 15 percent, The Hobbit 5 percent. The first way is to keep the cumulative sum of the weights and use binary search to find which slice a random number in [0, total) falls into:

public T Pick(Random random)
{
    double r = random.NextDouble() * _cumulative[^1];
    int index = Array.BinarySearch(_cumulative, r);
    index = index < 0 ? ~index : index + 1; // first cumulative value greater than r
    return _items[Math.Min(index, _items.Length - 1)];
}

This combines the prefix sum from the seventh post of this series with the upper bound from the tenth: building is O(n), picking is O(log n). The ~index that Array.BinarySearch returns when it does not find the value is exactly the position we want. If there are very many picks, Walker's alias method, with Vose's 1991 construction, brings each pick down to O(1): it builds a table of n columns and splits each column between at most two elements; a pick is one column and one coin flip.

Dune         weight 50%  cumulative  50.1%  alias  50.0%
Emma         weight 30%  cumulative  29.9%  alias  30.0%
Middlemarch  weight 15%  cumulative  15.1%  alias  15.0%
The Hobbit   weight  5%  cumulative   5.0%  alias   5.0%

Over 100,000 days both methods follow the weights. The alias table has to be rebuilt whenever the weights change; for a few dozen campaigns the cumulative array is enough and easier to read.

Deterministic Randomness: A 10 Percent Rollout

The new checkout page will be enabled for 10 percent of users. Saying Random.Shared.Next(100) < 10 on every request is wrong: the same user sees the new page on one request and the old one on the next. The assignment must be fixed per user and independent of the server and the process. We need something that looks random but is deterministic: a hash.

// Deterministic bucketing: the same flag and user always land in the same bucket, on every server and every run
public static int Bucket(string flag, string userId)
{
    ulong hash = XxHash3.HashToUInt64(Encoding.UTF8.GetBytes($"{flag}:{userId}"));
    return (int)(hash % 100);
}

public static bool IsEnabled(string flag, string userId, int percentage) => Bucket(flag, userId) < percentage;

I ran the demo twice, as two separate processes. Both printed:

user-42 new-checkout bucket: 50
user-42 dark-mode bucket:    95
new-checkout at 10%: 10,048 of 100,000 users; also in dark-mode at 10%: 1,049

The only difference was on the last line: "user-42".GetHashCode() was −1040352849 in the first run and 1759377789 in the second. Because of the randomized string hashing we saw in the sixth post of this series, GetHashCode cannot be used for bucketing; the user would land in a different group on every deploy. Three more details matter. Including the flag name in the hash makes flags independent of each other: 10 percent of the 10,048 people in new-checkout (1,049) are also in dark-mode; without the flag name, the same 10 percent would be in every experiment. Raising the percentage from 10 to 20 keeps the first 10 percent, because everyone with bucket < 10 also has bucket < 20. And since 2⁶⁴ is not divisible by 100, the modulo has a bias, but on the order of 10⁻¹⁷. The code side of feature flags is in the Solution Patterns series post "Designing Feature Flags in Code: Toggle Types, Microsoft.FeatureManagement and Flag Debt", and the statistics of A/B tests in the Product Management series post "Deciding with Experiments: A/B Tests, Feature Flags and Statistical Pitfalls".

Seeds, Threads and Security

1,000 x new Random() in a loop: 1000 distinct first values
seeded Random shared by threads: 85 of 10,000,000 calls returned 0; afterwards 0 of 1,000
Random.Shared from threads: 0 zeros
Random(12345) token: 632b808fafc222ca, again: 632b808fafc222ca
RandomNumberGenerator token length: 32 hex chars

The first line shows the current state of an old warning. According to the Random documentation, on .NET Framework the parameterless constructor took its seed from the system clock, and objects created back to back in a loop could produce the same sequence; on .NET 10 the first values of 1,000 objects are all different. Creating objects in a loop is still a needless allocation; a single object or Random.Shared is enough.

The second line is the real danger. I called a single seeded Random from Parallel.For; 85 of 10 million calls returned 0. When I repeated the same experiment in a separate small program with 50 million calls, most of the calls returned 0, and afterwards the object kept producing only 0 even when called from a single thread: its internal state was permanently corrupted. The documentation says it plainly: Random is not thread-safe. For sharing across threads there is Random.Shared.

The last two lines are about security. Two Random objects created with the same seed produce the same "token"; someone who knows the seed or a few outputs can compute the next ones. For password reset links, API keys and session tokens use System.Security.Cryptography.RandomNumberGenerator (GetHexString, GetInt32, Fill); the details are in the Cryptography for Developers series. The legitimate use of a seed is tests: new Random(27) makes the tests in this post repeatable. But according to the documentation the same seed can produce a different sequence on different .NET versions; do not store a seeded sequence in data or tie it to a result that must stay fixed across versions. That is one reason the rollout uses a hash, not Random.

In Production

Pin the hash and the format. The rollout bucket is the XxHash3 of the "{flag}:{userId}" string; changing that format or updating the hash algorithm redistributes all users. Document it like a contract and pin it down with a test.

Make randomness testable. Pass Random to the method as a parameter or inject it through the constructor; a seeded object in tests, Random.Shared in production. Test a distribution not with a single output but with counts over thousands of trials.

Know what your sample represents. Reservoir sampling gives every line in the stream an equal chance; if you specifically want to see error lines, you need weighted or stratified sampling.

Common Pitfalls

Choosing j from the whole array. The loop that looks like Fisher–Yates but produces n^n paths is biased; use Random.Shuffle instead of writing it by hand.

Sorting with a random comparer. Sorting expects consistent comparisons; the result is biased at best.

Sharing a Random object across threads. As in the measurement, its internal state gets corrupted and the object starts producing 0. Use Random.Shared.

Using Random for a security token. It is predictable; use RandomNumberGenerator.

Assigning feature flags at random on every request, or with GetHashCode. The user flips between groups; use a deterministic hash that does not depend on the process.

Series Wrap-Up: Structures You Often Write in Practice

The decision table in the twenty-second post of this series covered the classic curriculum. The last five posts added five signals you run into when building product features:

What these structures have in common is that each is a combination of basic structures from earlier posts: LRU combines a hash table with a linked list, Aho-Corasick combines a trie with KMP, the alias method combines a prefix sum with binary search. Knowing the basics means being able to take a new structure apart the first time you see it.

A Small Experiment

★☆☆ Change FisherYates to run only the first k steps and write a "pick k different books out of n" method. Pick 3 out of 10 books 100,000 times and verify that each book is picked about 30 percent of the time.

★★☆ Add a sticky A/B assignment to Rollout: Variant(flag, userId, ["control", "a", "b"], [50, 25, 25]). Keep the weights in a cumulative array and use the bucket in the 0–99 range. When you change the share of one variant, how many users change group?

★★★ Write weighted reservoir sampling: every line has a weight (say 10 for error lines, 1 for the rest). In Efraimidis and Spirakis' method a key u^(1/w) is computed for every item, and the k largest keys are kept in a k-element min-heap as in the thirteenth post of this series. Measure the share of error lines in the sample.

With this post the "Algorithms and Data Structures" series is complete. From arrays to hash tables, from sorting to trees, from graphs to dynamic programming, and from there to LRU caches, string search, intervals, probabilistic structures and randomness, we wrote every structure ourselves, measured it against its BCL counterpart and applied it to the Bookstore's real problems. The next step is your project: at the next slow endpoint, or the next "how should we store this" question, look for which row of these two decision tables you are facing.