Changeset 10466

Timestamp:

02/19/14 11:30:23 (11 years ago)

Author:

gkronber

Message:

#2146: changed implementation of SampleProportionalWithoutRepetition to use a linked list.

File:

• trunk/sources/HeuristicLab.Random/3.3/RandomEnumerable.cs (modified) (6 diffs)

trunk/sources/HeuristicLab.Random/3.3/RandomEnumerable.cs

@@ -36 +36 @@
 
     //algorithm taken from progamming pearls page 127
-    //IMPORTANT because IEnumerables with yield are used the seed must best be specified to return always 
+    //IMPORTANT because IEnumerables with yield are used the seed must be specified to return always 
     //the same sequence of numbers without caching the values.
     public static IEnumerable<int> SampleRandomNumbers(int seed, int start, int end, int count) {
@@ -166 +166 @@
     /// 
     /// The method internally holds two arrays: One that is the sequence itself and another one for the values.
+    /// 
+    /// The method does not check if the number of elements in source and weights are the same.
     /// </remarks>
     /// <typeparam name="T">The type of the items to be selected.</typeparam>
@@ -173 +175 @@
     /// <param name="weights">The weight values for the items.</param>
     /// <param name="windowing">Whether to scale the proportional values or not.</param>
-    /// <param name="maximization">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
-    /// <returns>A sequence of selected items.</returns>
+    /// <param name="inverseProportional">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
+    /// <returns>A sequence of selected items. Might actually be shorter than <paramref name="count"/> elements if source has less than <paramref name="count"/> elements.</returns>
     public static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count, IEnumerable<double> weights, bool windowing = true, bool inverseProportional = false) {
       return source.SampleProportionalWithoutRepetition(random, weights, windowing, inverseProportional).Take(count);
@@ -181 +183 @@
     private static IEnumerable<T> SampleProportional<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
       var sourceArray = source.ToArray();
-      var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);
+      var valueArray = PrepareProportional(sourceArray, weights, windowing, inverseProportional);
       double total = valueArray.Sum();
 
@@ -193 +195 @@
     }
     private static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
-      var sourceArray = source.ToArray();
-      var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);
+      var valueArray = PrepareProportional(source.ToArray(), weights, windowing, inverseProportional);
+      var list = new LinkedList<Tuple<T, double>>(source.Zip(valueArray, Tuple.Create));
       double total = valueArray.Sum();
 
-      HashSet<int> chosenIndices = new HashSet<int>();
-      while (chosenIndices.Count < sourceArray.Length) {
-        int index = -1;
-        double ball = 0, sum = random.NextDouble() * total;
+      while (list.Count > 0) {        
+        var cur = list.First;        
+        double ball = cur.Value.Item2, sum = random.NextDouble() * total; // assert: sum < total. When there is only one item remaining: sum < ball
         while (ball < sum) {
-          index++;
-          if (!chosenIndices.Contains(index))
-            ball += valueArray[index];
-        }
-        index = index >= 0 ? index : Enumerable.Range(0, sourceArray.Length).First(x => !chosenIndices.Contains(x));
-        yield return sourceArray[index];
-        chosenIndices.Add(index);
-        total -= valueArray[index];
-      }
-    }
+          cur = cur.Next;
+          ball += cur.Value.Item2;
+        }
+        yield return cur.Value.Item1;
+        list.Remove(cur);
+        total -= cur.Value.Item2;
+      }
+    }
+
     private static double[] PrepareProportional<T>(IList<T> sourceArray, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
       double maxValue = double.MinValue, minValue = double.MaxValue;
@@ -275 +275 @@
   }
 }
+