SHARE
TWEET

Untitled

a guest Sep 5th, 2014 331 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class NonRepeatingListFactory
  2. {
  3.     public static INonRepeatingList GetNonRepeatingList(int min, int max, int count)
  4.     {
  5.         long length = max - min + 1;
  6.         if (length / 8 > count * 2 * sizeof(int))
  7.         {
  8.             //if the amount of bytes occupied by the array is greater then the dictionary
  9.             return new NonRepeatingListWithSet();
  10.         }
  11.         return new NonRepeatingListWithArray(min, max);
  12.     }
  13. }
  14.  
  15. public interface INonRepeatingList : IEnumerable<int>
  16. {
  17.     bool Add(int value);
  18. }
  19.  
  20. internal class NonRepeatingListWithArray : List<int>, INonRepeatingList
  21. {
  22.     private readonly BitArray inList;
  23.     private readonly int min;
  24.     private readonly int max;
  25.  
  26.     public NonRepeatingListWithArray(int min, int max)
  27.     {
  28.         this.inList = new BitArray(max-min+1);
  29.         this.min = min;
  30.         this.max = max;
  31.     }
  32.  
  33.     bool INonRepeatingList.Add(int value)
  34.     {
  35.         if (!this.inList[value - this.min])
  36.         {
  37.             this.Add(value);
  38.             this.inList[value - this.min] = true;
  39.             return true;
  40.         }
  41.         return false;
  42.     }
  43. }
  44.  
  45. internal class NonRepeatingListWithSet : List<int>, INonRepeatingList
  46. {
  47.     private readonly HashSet<int> mapValue = new HashSet<int>();
  48.     private int currentIndex = 0;
  49.  
  50.     bool INonRepeatingList.Add(int value)
  51.     {
  52.         if (mapValue.Add(value))
  53.         {
  54.             base.Add(value);
  55.             return true;
  56.         }
  57.         return false;
  58.     }
  59. }
  60.  
  61. public static class MathUtils
  62. {
  63.     public static double Factorial(this int n)
  64.     {
  65.         if (n < 2)
  66.         {
  67.             return 1;
  68.         }
  69.         return n*Factorial(n - 1);
  70.     }
  71.  
  72.     public static double Factorial(this int n, int min)
  73.     {
  74.         double acc = 1;
  75.         while (n >= min)
  76.         {
  77.             acc *= n;
  78.             --n;
  79.         }
  80.         return acc;
  81.     }
  82. }
  83.  
  84. public static class CollectionUtils
  85. {
  86.     private static readonly Random random = new Random();
  87.  
  88.     public static IList<T> Shuffle<T>(this IEnumerable<T> col)
  89.     {
  90.         var list = col as IList<T> ?? col.ToList();
  91.         for (int i = 0; i < list.Count; ++i)
  92.         {
  93.             //get a chance of staying in same place
  94.             list.Swap(i, random.Next(i, list.Count));
  95.         }
  96.         return list;
  97.     }
  98.  
  99.     public static void Swap<T>(this IEnumerable<T> col, int idxSrc, int idxDest)
  100.     {
  101.         var list = col as IList<T> ?? col.ToList();
  102.         T aux = list[idxSrc];
  103.         list[idxSrc] = list[idxDest];
  104.         list[idxDest] = aux;
  105.     }
  106. }
  107.  
  108. [TestFixture]
  109. public class TestNonRepeatingGenerator
  110. {
  111.     [Test]
  112.     public void TestLastCountElementsAreNotInIndex0()
  113.     {
  114.         for (int i = 0; i < 1000000; ++i)
  115.         {
  116.             var list = Sequence.BobFloydNonRepeatingSequence(0, 15, 4).ToList();
  117.             Assert.IsFalse(new[] { 12, 13, 14, 15 }.Contains(list[0]));
  118.             Assert.AreEqual(4, list.Count);
  119.         }
  120.     }
  121.  
  122.     [Test]
  123.     public void TestBobFloydBecomesLinear()
  124.     {
  125.         var list = Sequence.BobFloydNonRepeatingSequence(0, 15, 16).ToList();
  126.         for (int i = 0; i < list.Count; ++i)
  127.         {
  128.             Assert.AreEqual(i, list[i]);
  129.         }
  130.     }
  131.  
  132.     [Test]
  133.     public void TestBobFloydRandomness()
  134.     {
  135.         TestRandomness(() => Sequence.BobFloydNonRepeatingSequence(0, 15, 4).ToList(), 16, 4);
  136.     }
  137.  
  138.  
  139.     [Test]
  140.     public void TestBobFloydWithShuffleRandomness()
  141.     {
  142.         TestRandomness(() => Sequence.NonRepeatingRandomSequence(0, 31, 4).ToList(), 32, 4);
  143.     }
  144.  
  145.     [Test]
  146.     public void TestShuffleRandomness()
  147.     {
  148.         TestRandomness(() => Enumerable.Range(0, 15).ToList().Shuffle().Take(4).ToList(), 16, 4);    
  149.     }
  150.    
  151.  
  152.     public void TestRandomness(Func<List<int>> getRandomList, int rangeLength, int count)
  153.     {
  154.         long combinations = (long)(rangeLength.Factorial(rangeLength - count + 1) * ((double)(count - 1) / count));
  155.         long iterations = combinations * 100;
  156.         var partitioner = Partitioner.Create(0, iterations, iterations / 4);
  157.         ConcurrentDictionary<long, int> ocurrences = new ConcurrentDictionary<long, int>(Environment.ProcessorCount, (int)combinations);
  158.  
  159.         Parallel.ForEach(partitioner, new ParallelOptions() {MaxDegreeOfParallelism = Environment.ProcessorCount},
  160.             range =>
  161.             {
  162.                 //hopefully having a private dictionary will help concurrency
  163.                 Dictionary<long, int> privateOcurrences = new Dictionary<long, int>();
  164.                 for (long i = range.Item1; i < range.Item2; ++i)
  165.                 {
  166.                     var list = getRandomList();
  167.                     long acc = 0;
  168.                     //this will only work when numbers are between 0 and 88
  169.                     foreach (var value in list)
  170.                     {
  171.                         acc = (value + 11) + acc*100;
  172.                     }
  173.                     privateOcurrences.AddOrUpdate(acc, 1, v => v + 1);
  174.                 }
  175.                 foreach (var privateOcurrence in privateOcurrences)
  176.                 {
  177.                     ocurrences.AddOrUpdate(privateOcurrence.Key,
  178.                         privateOcurrence.Value,
  179.                         (k, v) => v + privateOcurrence.Value);
  180.                 }
  181.             });
  182.  
  183.         double averageOcurrences = iterations / combinations;
  184.         double currentAverage = ocurrences.Values.Average();
  185.         Debug.WriteLine("The average ocurrences of this implementation is {0} comparing to {1} in the 'perfect' scenario", currentAverage, averageOcurrences);
  186.         Assert.Less(currentAverage, averageOcurrences * 1.05);
  187.         Assert.Greater(currentAverage, averageOcurrences * 0.95);
  188.     }
  189. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top