I ran across a practical example of algorithm analysis when I wrote a method that generates unique random values inside a provided range. Figured I would share it...
The code in this article was included in my https://github.com/ZacharyPatten/Towel project. Please check it out if you want to see more code like it. :)
Note: all code examples are in C#.
Introduction
When you want to generate unique random numbers, there are two approaches you can take: 1) you can track the remaining possible values of generation or 2) you can track the values that have already been randomly selected. For variables/parameters, let count be the number of values to generate, minValue be the inclusive lower bound of generation, and maxValue be the exclusive upper bound of generation.
Algorithm #1/A
After a bit of googling, option #1 seems to be more common. You often see people throw all the possible values into an array/list and remove a randomly generated index. Here is an implementation of that algorithm:
public static IEnumerable<int> NextUniqueA(this Random random, int count, int minValue, int maxValue) { // Algorithm A: Θ(range + count) int pool = maxValue - minValue; int[] array = new int[pool]; for (int i = 0, j = minValue; j < maxValue; i++, j++) // Θ(range) array[i] = j; for (int i = 0; i < count; i++) // Θ(count) { int rollIndex = random.Next(0, pool); int roll = array[rollIndex]; array[rollIndex] = array[--pool]; yield return roll; } } Algorithm #2/B
Now, here is what option #2 can look like. For this implementation, I use a linked list to store all the values that have already been generated in sorted order:
public static IEnumerable<int> NextUniqueB(this Random random, int count, int minValue, int maxValue) { // Algorithm B: O(.5*count^2), Ω(count), ε(.5*count^2) Node head = null; for (int i = 0; i < count; i++) // Θ(count) { int roll = random.Next(minValue, maxValue - i); Node node = head; Node previous = null; while (!(node is null)) // O(count / 2), Ω(0), ε(count / 2) { if (node.Value > roll) break; roll++; previous = node; node = node.Next; } yield return roll; if (previous is null) head = new Node() { Value = roll, Next = head, }; else previous.Next = new Node() { Value = roll, Next = previous.Next }; } } internal class Node { internal int Value; internal Node Next; } Analyzing Algorithm Complexities
These two implementations have different runtime algorithm complexities. The #1/A option has a runtime complexity of Θ(range + count) while the #2/B option has a runtime complexity of O(.5*count^2), Ω(count), ε(.5*count^2) where O is the worst case, Θ is every case, Ω is the best case, and ε is the expected average between the worst and the best cases. Long story short, when the count is relatively low you want to use algorithm #2/B. When the count is relatively high you want to use algorithm #1/A. So if you want to make a faster all-around general purpose method, you need to combine the two approaches. But how do you do that? You need to find the intersection of the two runtime complexities of each method.
If you treat both algorithm complexities as linear functions and do some simple math to find the intesection, you will find that they intersect at about √(maxValue - minValue) the square root of the range of random generation relative to count. Now that you know the intersection point, you can combine the two algorithms into a single function that is optimized for more use cases:
Combination of #1/A and #2/B
public static IEnumerable<int> NextUnique(this Random random, int count, int minValue, int maxValue) { if (count > Math.Sqrt(maxValue - minValue)) { // Algorithm A } else { // Algorithm B } } Benchmarks
Here are some benchmarks so you can compare theory with practical results. Note that for these benchmarks I used a random generation range of 0..10000. So minValue = 0 and maxValue = 10000. From the theory, I knew that the intersection of the runtime algorithms is roughly √(maxValue - minValue) = √(100000 - 0) = √(100000) = 100. So when count is less than ~100 the #2/B algorithm should be faster, but when count is greater than ~100 algorithm #1/A should be faster.
Benchmarks Source Code
Note: This code uses the BenchmarkDotNet nuget package. It also uses the Plots exporter to generate the graphs, which requires R be installed.
using BenchmarkDotNet.Attributes; using BenchmarkDotNet.Running; using System; using System.Linq; using System.Collections.Generic; using BenchmarkDotNet.Exporters; using BenchmarkDotNet.Configs; namespace UniqueRandomGeneration { class Program { static void Main(string[] args) => BenchmarkRunner.Run<Benchmarks>(); } [RPlotExporter] [Config(typeof(Config))] public class Benchmarks { public class Config : ManualConfig { public Config() => Add(RPlotExporter.Default); } const int MinValue = 0; const int MaxValue = 10000; [Params(25, 50, 75, 100, 125, 150, 175, 200, 225, 250)] public int Count; readonly Random random = new Random(); [Benchmark] public void RandomUniqueA() => random.NextUniqueA(Count, MinValue, MaxValue).ToArray(); [Benchmark] public void RandomUniqueB() => random.NextUniqueB(Count, MinValue, MaxValue).ToArray(); [Benchmark] public void RandomUnique() => random.NextUnique(Count, MinValue, MaxValue).ToArray(); } public static class Extensions { internal class Node { internal int Value; internal Node Next; } public static IEnumerable<int> NextUnique(this Random random, int count, int minValue, int maxValue) { if (maxValue < minValue) throw new ArgumentOutOfRangeException(nameof(minValue) + " > " + nameof(minValue)); if (count < 0) throw new ArgumentOutOfRangeException(nameof(count) + " < 0"); if (maxValue - minValue < count) throw new ArgumentOutOfRangeException(nameof(count) + " is larger than " + nameof(maxValue) + " - " + nameof(minValue) + "."); if (count > Math.Sqrt(maxValue - minValue)) { // Algorithm A: Θ(range + count) int pool = maxValue - minValue; int[] array = new int[pool]; for (int i = 0, j = minValue; j < maxValue; i++, j++) // Θ(range) array[i] = j; for (int i = 0; i < count; i++) // Θ(count) { int rollIndex = random.Next(0, pool); int roll = array[rollIndex]; array[rollIndex] = array[--pool]; yield return roll; } } else { // Algorithm B: O(.5*count^2), Ω(count), ε(.5*count^2) Node head = null; for (int i = 0; i < count; i++) // Θ(count) { int roll = random.Next(minValue, maxValue - i); Node node = head; Node previous = null; while (!(node is null)) // O(count / 2), Ω(0), ε(count / 2) { if (node.Value > roll) break; roll++; previous = node; node = node.Next; } yield return roll; if (previous is null) head = new Node() { Value = roll, Next = head, }; else previous.Next = new Node() { Value = roll, Next = previous.Next }; } } } public static IEnumerable<int> NextUniqueA(this Random random, int count, int minValue, int maxValue) { if (maxValue < minValue) throw new ArgumentOutOfRangeException(nameof(minValue) + " > " + nameof(minValue)); if (count < 0) throw new ArgumentOutOfRangeException(nameof(count) + " < 0"); if (maxValue - minValue < count) throw new ArgumentOutOfRangeException(nameof(count) + " is larger than " + nameof(maxValue) + " - " + nameof(minValue) + "."); // Algorithm A: Θ(range + count) int pool = maxValue - minValue; int[] array = new int[pool]; for (int i = 0, j = minValue; j < maxValue; i++, j++) // Θ(range) array[i] = j; for (int i = 0; i < count; i++) // Θ(count) { int rollIndex = random.Next(0, pool); int roll = array[rollIndex]; array[rollIndex] = array[--pool]; yield return roll; } } public static IEnumerable<int> NextUniqueB(this Random random, int count, int minValue, int maxValue) { if (maxValue < minValue) throw new ArgumentOutOfRangeException(nameof(minValue) + " > " + nameof(minValue)); if (count < 0) throw new ArgumentOutOfRangeException(nameof(count) + " < 0"); if (maxValue - minValue < count) throw new ArgumentOutOfRangeException(nameof(count) + " is larger than " + nameof(maxValue) + " - " + nameof(minValue) + "."); // Algorithm B: O(.5*count^2), Ω(count), ε(.5*count^2) Node head = null; for (int i = 0; i < count; i++) // Θ(count) { int roll = random.Next(minValue, maxValue - i); Node node = head; Node previous = null; while (!(node is null)) // O(count / 2), Ω(0), ε(count / 2) { if (node.Value > roll) break; roll++; previous = node; node = node.Next; } yield return roll; if (previous is null) head = new Node() { Value = roll, Next = head, }; else previous.Next = new Node() { Value = roll, Next = previous.Next }; } } } } Benchmarks Results Table
BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363 Intel Core i7-4790K CPU 4.00GHz (Haswell), 1 CPU, 8 logical and 4 physical cores .NET Core SDK=3.1.100 [Host] : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT DefaultJob : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT | Method | Count | Mean | Error | StdDev |
|---|---|---|---|---|
| RandomUniqueA | 25 | 7.406 us | 0.1576 us | 0.1876 us |
| RandomUniqueB | 25 | 1.307 us | 0.0256 us | 0.0414 us |
| RandomUnique | 25 | 1.300 us | 0.0046 us | 0.0043 us |
| RandomUniqueA | 50 | 7.761 us | 0.0263 us | 0.0246 us |
| RandomUniqueB | 50 | 2.893 us | 0.0084 us | 0.0079 us |
| RandomUnique | 50 | 3.022 us | 0.0755 us | 0.0707 us |
| RandomUniqueA | 75 | 8.387 us | 0.1317 us | 0.1232 us |
| RandomUniqueB | 75 | 5.180 us | 0.1070 us | 0.1001 us |
| RandomUnique | 75 | 5.298 us | 0.0634 us | 0.0593 us |
| RandomUniqueA | 100 | 9.151 us | 0.1800 us | 0.2340 us |
| RandomUniqueB | 100 | 8.013 us | 0.0994 us | 0.0930 us |
| RandomUnique | 100 | 8.246 us | 0.1205 us | 0.1127 us |
| RandomUniqueA | 125 | 9.335 us | 0.1533 us | 0.1434 us |
| RandomUniqueB | 125 | 11.291 us | 0.1093 us | 0.1023 us |
| RandomUnique | 125 | 9.394 us | 0.1773 us | 0.1658 us |
| RandomUniqueA | 150 | 9.509 us | 0.0323 us | 0.0302 us |
| RandomUniqueB | 150 | 14.486 us | 0.0653 us | 0.0610 us |
| RandomUnique | 150 | 9.355 us | 0.0428 us | 0.0400 us |
| RandomUniqueA | 175 | 9.972 us | 0.0319 us | 0.0298 us |
| RandomUniqueB | 175 | 18.778 us | 0.0792 us | 0.0741 us |
| RandomUnique | 175 | 9.789 us | 0.0593 us | 0.0554 us |
| RandomUniqueA | 200 | 10.270 us | 0.0297 us | 0.0278 us |
| RandomUniqueB | 200 | 23.384 us | 0.0623 us | 0.0520 us |
| RandomUnique | 200 | 10.112 us | 0.0499 us | 0.0466 us |
| RandomUniqueA | 225 | 10.724 us | 0.1754 us | 0.1465 us |
| RandomUniqueB | 225 | 28.748 us | 0.0872 us | 0.0816 us |
| RandomUnique | 225 | 10.612 us | 0.0430 us | 0.0381 us |
| RandomUniqueA | 250 | 11.144 us | 0.0518 us | 0.0484 us |
| RandomUniqueB | 250 | 34.320 us | 0.1249 us | 0.1107 us |
| RandomUnique | 250 | 10.891 us | 0.0826 us | 0.0772 us |
Benchmarks Results Bar Graph
Probability/Validity Testing
Here is some validity testing to hopefully make sure I am not full of shit. In this code, I generate 5 values in the 0..26 range. I do this 1000000 times, and I calculate the mean that each values was randomly selected. All the values should be selected an average of 5 / 26 = 0.1923... times.
Validity Testing Source Code
using System; using System.Linq; using System.Collections.Generic; namespace ValidityTesting { class Program { static void Main() { Console.WriteLine(nameof(Extensions.NextUnique)); PrintPriorities(CalculateProbabilities(Extensions.NextUnique)); Console.WriteLine(); Console.WriteLine(nameof(Extensions.NextUniqueA)); PrintPriorities(CalculateProbabilities(Extensions.NextUniqueA)); Console.WriteLine(); Console.WriteLine(nameof(Extensions.NextUniqueB)); PrintPriorities(CalculateProbabilities(Extensions.NextUniqueB)); Console.WriteLine(); } internal static void PrintPriorities(Dictionary<int, double> results) { foreach (var keyVal in results.OrderBy(x => x.Key)) Console.WriteLine(keyVal.Key + ": " + keyVal.Value); } internal static Dictionary<int, double> CalculateProbabilities(Func<Random, int, int, int, IEnumerable<int>> algorithm) { Random random = new Random(); const int size = 5; const int min = 0; const int max = 26; const int iterations = 1000000; var counts = new Dictionary<int, int>(); for (int i = min; i < max; i++) counts.Add(i, 0); for (int i = 0; i < iterations; i++) foreach (int j in algorithm(random, size, min, max)) counts[j]++; var results = new Dictionary<int, double>(); foreach (var keyVal in counts) results.Add(keyVal.Key, keyVal.Value / (double)iterations); return results; } } public static class Extensions { internal class Node { internal int Value; internal Node Next; } public static IEnumerable<int> NextUnique(this Random random, int count, int minValue, int maxValue) { if (maxValue < minValue) throw new ArgumentOutOfRangeException(nameof(minValue) + " > " + nameof(minValue)); if (count < 0) throw new ArgumentOutOfRangeException(nameof(count) + " < 0"); if (maxValue - minValue < count) throw new ArgumentOutOfRangeException(nameof(count) + " is larger than " + nameof(maxValue) + " - " + nameof(minValue) + "."); if (count > Math.Sqrt(maxValue - minValue)) { // Algorithm A: Θ(range + count) int pool = maxValue - minValue; int[] array = new int[pool]; for (int i = 0, j = minValue; j < maxValue; i++, j++) // Θ(range) array[i] = j; for (int i = 0; i < count; i++) // Θ(count) { int rollIndex = random.Next(0, pool); int roll = array[rollIndex]; array[rollIndex] = array[--pool]; yield return roll; } } else { // Algorithm B: O(.5*count^2), Ω(count), ε(.5*count^2) Node head = null; for (int i = 0; i < count; i++) // Θ(count) { int roll = random.Next(minValue, maxValue - i); Node node = head; Node previous = null; while (!(node is null)) // O(count / 2), Ω(0), ε(count / 2) { if (node.Value > roll) break; roll++; previous = node; node = node.Next; } yield return roll; if (previous is null) head = new Node() { Value = roll, Next = head, }; else previous.Next = new Node() { Value = roll, Next = previous.Next }; } } } public static IEnumerable<int> NextUniqueA(this Random random, int count, int minValue, int maxValue) { if (maxValue < minValue) throw new ArgumentOutOfRangeException(nameof(minValue) + " > " + nameof(minValue)); if (count < 0) throw new ArgumentOutOfRangeException(nameof(count) + " < 0"); if (maxValue - minValue < count) throw new ArgumentOutOfRangeException(nameof(count) + " is larger than " + nameof(maxValue) + " - " + nameof(minValue) + "."); // Algorithm A: Θ(range + count) int pool = maxValue - minValue; int[] array = new int[pool]; for (int i = 0, j = minValue; j < maxValue; i++, j++) // Θ(range) array[i] = j; for (int i = 0; i < count; i++) // Θ(count) { int rollIndex = random.Next(0, pool); int roll = array[rollIndex]; array[rollIndex] = array[--pool]; yield return roll; } } public static IEnumerable<int> NextUniqueB(this Random random, int count, int minValue, int maxValue) { if (maxValue < minValue) throw new ArgumentOutOfRangeException(nameof(minValue) + " > " + nameof(minValue)); if (count < 0) throw new ArgumentOutOfRangeException(nameof(count) + " < 0"); if (maxValue - minValue < count) throw new ArgumentOutOfRangeException(nameof(count) + " is larger than " + nameof(maxValue) + " - " + nameof(minValue) + "."); // Algorithm B: O(.5*count^2), Ω(count), ε(.5*count^2) Node head = null; for (int i = 0; i < count; i++) // Θ(count) { int roll = random.Next(minValue, maxValue - i); Node node = head; Node previous = null; while (!(node is null)) // O(count / 2), Ω(0), ε(count / 2) { if (node.Value > roll) break; roll++; previous = node; node = node.Next; } yield return roll; if (previous is null) head = new Node() { Value = roll, Next = head, }; else previous.Next = new Node() { Value = roll, Next = previous.Next }; } } } } Validity Testing Console Output
NextUnique 0: 0.192031 1: 0.19208 2: 0.192785 3: 0.192287 4: 0.192593 5: 0.192686 6: 0.191937 7: 0.191998 8: 0.19244 9: 0.192112 10: 0.19212 11: 0.192707 12: 0.192877 13: 0.192086 14: 0.192277 15: 0.191907 16: 0.192366 17: 0.192386 18: 0.192423 19: 0.19229 20: 0.192017 21: 0.191901 22: 0.19285 23: 0.19282 24: 0.191902 25: 0.192122 NextUniqueA 0: 0.192705 1: 0.191956 2: 0.192313 3: 0.192613 4: 0.193418 5: 0.191957 6: 0.192116 7: 0.192217 8: 0.192773 9: 0.191862 10: 0.19233 11: 0.192145 12: 0.192044 13: 0.192749 14: 0.192097 15: 0.19224 16: 0.192526 17: 0.19225 18: 0.191653 19: 0.192546 20: 0.192156 21: 0.191686 22: 0.192908 23: 0.19174 24: 0.192605 25: 0.192395 NextUniqueB 0: 0.192408 1: 0.191776 2: 0.191809 3: 0.192623 4: 0.192399 5: 0.192451 6: 0.192135 7: 0.1931 8: 0.192594 9: 0.19232 10: 0.192281 11: 0.191723 12: 0.192358 13: 0.19216 14: 0.192697 15: 0.192975 16: 0.192357 17: 0.192507 18: 0.191768 19: 0.191874 20: 0.192803 21: 0.191934 22: 0.192075 23: 0.192704 24: 0.192155 25: 0.192014 
Top comments (0)