Guest User

Untitled

a guest
Sep 5th, 2014
392
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×