Changeset 10538 for branches/DataPreprocessing/HeuristicLab.Random/3.3

Timestamp:

03/05/14 14:48:13 (11 years ago)

Author:

pfleck

Message:

• merged trunk

Location:

branches/DataPreprocessing

Files:

• . (modified) (1 prop)
• HeuristicLab.Random/3.3/RandomEnumerable.cs (modified) (6 diffs)

branches/DataPreprocessing/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(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(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 = 0;
-        double ball = valueArray[index], 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];
-        }
-        yield return sourceArray[index];
-        chosenIndices.Add(index);
-        total -= valueArray[index];
-      }
-    }
-    private static double[] PrepareProportional<T>(IList<T> sourceArray, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
+          cur = cur.Next;
+          ball += cur.Value.Item2;
+        }
+        yield return cur.Value.Item1;
+        list.Remove(cur);
+        total -= cur.Value.Item2;
+      }
+    }
+
+    private static double[] PrepareProportional(IEnumerable<double> weights, bool windowing, bool inverseProportional) {
       double maxValue = double.MinValue, minValue = double.MaxValue;
-      double[] valueArray = new double[sourceArray.Count];
-
-      var weightsEnum = weights.GetEnumerator();
-      for (int i = 0; i < sourceArray.Count && weightsEnum.MoveNext(); i++) {
-        valueArray[i] = weightsEnum.Current;
+      double[] valueArray = weights.ToArray();
+
+      for (int i = 0; i < valueArray.Length; i++) {
         if (valueArray[i] > maxValue) maxValue = valueArray[i];
         if (valueArray[i] < minValue) minValue = valueArray[i];
       }
       if (minValue == maxValue) {  // all values are equal
-        for (int i = 0; i < sourceArray.Count; i++) {
+        for (int i = 0; i < valueArray.Length; i++) {
           valueArray[i] = 1.0;
         }
@@ -274 +273 @@
   }
 }
+