Guest User

Comparison of various shuffle algorithms

a guest
Mar 15th, 2015
523
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace Example
  6. {
  7.     class Program
  8.     {
  9.         public static void Main(string[] args)
  10.         {
  11.             const int length = 3;
  12.             const int cycles = 1000000;
  13.  
  14.             Random r = new Random();
  15.  
  16.             List<int[]> permutations = new List<int[]>();
  17.  
  18.             // Build all the permutations
  19.             {
  20.                 var numbers = new int[length];
  21.                 Reset(numbers);
  22.  
  23.                 // We calculate all the possible permutations. We will use them
  24.                 // later, to see if each one happens the same number of times
  25.                 permutations.Add((int[])numbers.Clone());
  26.  
  27.                 while (!NextPermutation(numbers))
  28.                 {
  29.                     permutations.Add((int[])numbers.Clone());
  30.                 }
  31.             }
  32.  
  33.             Calculate("Fisher-Yates backward", length, cycles, permutations.AsReadOnly(), nums => Shuffle1(nums, r));
  34.             Calculate("Fisher-Yates forward", length, cycles, permutations.AsReadOnly(), nums => Shuffle2(nums, r));
  35.             Calculate("Naive", length, cycles, permutations.AsReadOnly(), nums => NaiveShuffle(nums, r));
  36.             Calculate("r.Next()", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next()));
  37.             Calculate("r.Next(int.MaxValue)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(int.MaxValue)));
  38.             Calculate("r.Next(1)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(1)));
  39.             Calculate("r.Next(2)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(2)));
  40.             Calculate("r.Next(4)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(4)));
  41.             Calculate("r.Next(8)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(8)));
  42.             Calculate("r.Next(16)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(16)));
  43.             Calculate("r.Next(32)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(32)));
  44.             Calculate("r.Next(64)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(64)));
  45.             Calculate("r.Next(128)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(128)));
  46.             Calculate("r.Next(256)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(256)));
  47.             Calculate("r.Next(512)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(512)));
  48.             Calculate("r.Next(1024)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(1024)));
  49.         }
  50.  
  51.         #region Algorithms
  52.  
  53.         // http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
  54.         public static void Shuffle1<T>(T[] array, Random r)
  55.         {
  56.             // Shuffles in place! Compatible with arrays (but a little
  57.             // slower, because it is using the IList<T> interface instead of
  58.             // using direct array accessors)
  59.             // Using the backward algorithm of the Wiki.
  60.             // With C# I could have used the forward algorithm.
  61.             for (int i = array.Length - 1; i > 0; i--)
  62.             {
  63.                 int j = r.Next(i + 1);
  64.  
  65.                 T temp = array[i];
  66.                 array[i] = array[j];
  67.                 array[j] = temp;
  68.             }
  69.         }
  70.  
  71.         // http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
  72.         public static void Shuffle2<T>(T[] array, Random r)
  73.         {
  74.             // Shuffles in place! Compatible with arrays (but a little
  75.             // slower, because it is using the IList<T> interface instead of
  76.             // using direct array accessors)
  77.             // Using the forward algorithm of the Wiki.
  78.             for (int i = 0; i < array.Length; i++)
  79.             {
  80.                 int j = r.Next(i, array.Length);
  81.  
  82.                 T temp = array[i];
  83.                 array[i] = array[j];
  84.                 array[j] = temp;
  85.             }
  86.         }
  87.  
  88.         // Taken from http://blog.codinghorror.com/the-danger-of-naivete/
  89.         public static void NaiveShuffle<T>(T[] array, Random r)
  90.         {
  91.             for (int i = 0; i < array.Length; i++)
  92.             {
  93.                 int j = r.Next(array.Length);
  94.  
  95.                 T temp = array[i];
  96.                 array[i] = array[j];
  97.                 array[j] = temp;
  98.             }
  99.         }
  100.  
  101.         // OrderBy shuffler, receives a function orderer that should be
  102.         // something like () => r.Next()
  103.         public static void WithOrderBy<T>(T[] array, Func<int> orderer)
  104.         {
  105.             var enu = array.OrderBy(x => orderer());
  106.  
  107.             // OrderBy creates a new "collection". We have to overwrite the
  108.             // old one
  109.             int i = 0;
  110.  
  111.             foreach (T el in enu)
  112.             {
  113.                 array[i] = el;
  114.                 i++;
  115.             }
  116.         }
  117.  
  118.         #endregion
  119.  
  120.         // Taken from http://stackoverflow.com/questions/11208446/generating-permutations-of-a-set-most-efficiently
  121.         public static bool NextPermutation<T>(T[] elements) where T : IComparable<T>
  122.         {
  123.             // More efficient to have a variable instead of accessing a property
  124.             var count = elements.Length;
  125.  
  126.             // Indicates whether this is the last lexicographic permutation
  127.             var done = true;
  128.  
  129.             // Go through the array from last to first
  130.             for (var i = count - 1; i > 0; i--)
  131.             {
  132.                 var curr = elements[i];
  133.  
  134.                 // Check if the current element is less than the one before it
  135.                 if (curr.CompareTo(elements[i - 1]) < 0)
  136.                 {
  137.                     continue;
  138.                 }
  139.  
  140.                 // An element bigger than the one before it has been found,
  141.                 // so this isn't the last lexicographic permutation.
  142.                 done = false;
  143.  
  144.                 // Save the previous (bigger) element in a variable for more efficiency.
  145.                 var prev = elements[i - 1];
  146.  
  147.                 // Have a variable to hold the index of the element to swap
  148.                 // with the previous element (the to-swap element would be
  149.                 // the smallest element that comes after the previous element
  150.                 // and is bigger than the previous element), initializing it
  151.                 // as the current index of the current item (curr).
  152.                 var currIndex = i;
  153.  
  154.                 // Go through the array from the element after the current one to last
  155.                 for (var j = i + 1; j < count; j++)
  156.                 {
  157.                     // Save into variable for more efficiency
  158.                     var tmp = elements[j];
  159.  
  160.                     // Check if tmp suits the "next swap" conditions:
  161.                     // Smallest, but bigger than the "prev" element
  162.                     if (tmp.CompareTo(curr) < 0 && tmp.CompareTo(prev) > 0)
  163.                     {
  164.                         curr = tmp;
  165.                         currIndex = j;
  166.                     }
  167.                 }
  168.  
  169.                 // Swap the "prev" with the new "curr" (the swap-with element)
  170.                 elements[currIndex] = prev;
  171.                 elements[i - 1] = curr;
  172.  
  173.                 // Reverse the order of the tail, in order to reset it's lexicographic order
  174.                 for (var j = count - 1; j > i; j--, i++)
  175.                 {
  176.                     var tmp = elements[j];
  177.                     elements[j] = elements[i];
  178.                     elements[i] = tmp;
  179.                 }
  180.  
  181.                 // Break since we have got the next permutation
  182.                 // The reason to have all the logic inside the loop is
  183.                 // to prevent the need of an extra variable indicating "i" when
  184.                 // the next needed swap is found (moving "i" outside the loop is a
  185.                 // bad practice, and isn't very readable, so I preferred not doing
  186.                 // that as well).
  187.                 break;
  188.             }
  189.  
  190.             // Return whether this has been the last lexicographic permutation.
  191.             return done;
  192.         }
  193.  
  194.         // Reset an array to a sequence 0... array.Length - 1
  195.         public static void Reset(int[] array)
  196.         {
  197.             for (int i = 0; i < array.Length; i++)
  198.             {
  199.                 array[i] = i;
  200.             }
  201.         }
  202.  
  203.         // Simple array IEqualityComparer
  204.         public class ArrayComparer : IEqualityComparer<int[]>, IComparer<int[]>
  205.         {
  206.             public static readonly ArrayComparer Instance = new ArrayComparer();
  207.  
  208.             protected ArrayComparer()
  209.             {
  210.             }
  211.  
  212.             public bool Equals(int[] x, int[] y)
  213.             {
  214.                 return Compare(x, y) == 0;
  215.             }
  216.  
  217.             public int GetHashCode(int[] obj)
  218.             {
  219.                 unchecked
  220.                 {
  221.                     int hash = 17;
  222.  
  223.                     if (obj != null)
  224.                     {
  225.                         for (int i = 0; i < obj.Length; i++)
  226.                         {
  227.                             hash = hash * 23 + obj[i].GetHashCode();
  228.                         }
  229.                     }
  230.  
  231.                     return hash;
  232.                 }
  233.             }
  234.  
  235.             public int Compare(int[] x, int[] y)
  236.             {
  237.                 if (x == null)
  238.                 {
  239.                     if (y == null)
  240.                     {
  241.                         return 0;
  242.                     }
  243.  
  244.                     return -1;
  245.                 }
  246.  
  247.                 if (y == null)
  248.                 {
  249.                     return 1;
  250.                 }
  251.  
  252.                 int min = Math.Min(x.Length, y.Length);
  253.  
  254.                 for (int i = 0; i < min; i++)
  255.                 {
  256.                     int cmp = x[i].CompareTo(y[i]);
  257.  
  258.                     if (cmp != 0)
  259.                     {
  260.                         return cmp;
  261.                     }
  262.                 }
  263.  
  264.                 return x.Length.CompareTo(y.Length);
  265.             }
  266.         }
  267.  
  268.         // Executes cycles shuffles on a int[length] array, using shuffler.
  269.         // Shows the number of times each of the permutations happened, with
  270.         // a comparison to the first of the permutations
  271.         public static void Calculate(string title, int length, int cycles, IReadOnlyList<int[]> permutations, Action<int[]> shuffler)
  272.         {
  273.             var numbers = new int[length];
  274.             Reset(numbers);
  275.  
  276.             var dict = permutations.ToDictionary(x => x, x => 0, ArrayComparer.Instance);
  277.  
  278.             for (int i = 0; i < cycles; i++)
  279.             {
  280.                 Reset(numbers);
  281.  
  282.                 shuffler(numbers);
  283.  
  284.                 dict[numbers]++;
  285.             }
  286.  
  287.             Console.WriteLine(title);
  288.  
  289.             var dict2 = dict.OrderBy(x => x.Key, ArrayComparer.Instance).ToArray();
  290.  
  291.             // All the % are based on the first element
  292.             foreach (var kv in dict2)
  293.             {
  294.                 Console.WriteLine("[{0}]: {1} ({2:P2})", string.Join(",", kv.Key), kv.Value, ((double)kv.Value) / dict2[0].Value - 1);
  295.             }
  296.  
  297.             Console.WriteLine();
  298.         }
  299.     }
  300. }
RAW Paste Data