Changeset 10466


Ignore:
Timestamp:
02/19/14 11:30:23 (6 years ago)
Author:
gkronber
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Random/3.3/RandomEnumerable.cs

    r10407 r10466  
    3636
    3737    //algorithm taken from progamming pearls page 127
    38     //IMPORTANT because IEnumerables with yield are used the seed must best be specified to return always
     38    //IMPORTANT because IEnumerables with yield are used the seed must be specified to return always
    3939    //the same sequence of numbers without caching the values.
    4040    public static IEnumerable<int> SampleRandomNumbers(int seed, int start, int end, int count) {
     
    166166    ///
    167167    /// The method internally holds two arrays: One that is the sequence itself and another one for the values.
     168    ///
     169    /// The method does not check if the number of elements in source and weights are the same.
    168170    /// </remarks>
    169171    /// <typeparam name="T">The type of the items to be selected.</typeparam>
     
    173175    /// <param name="weights">The weight values for the items.</param>
    174176    /// <param name="windowing">Whether to scale the proportional values or not.</param>
    175     /// <param name="maximization">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
    176     /// <returns>A sequence of selected items.</returns>
     177    /// <param name="inverseProportional">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
     178    /// <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>
    177179    public static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count, IEnumerable<double> weights, bool windowing = true, bool inverseProportional = false) {
    178180      return source.SampleProportionalWithoutRepetition(random, weights, windowing, inverseProportional).Take(count);
     
    181183    private static IEnumerable<T> SampleProportional<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
    182184      var sourceArray = source.ToArray();
    183       var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);
     185      var valueArray = PrepareProportional(sourceArray, weights, windowing, inverseProportional);
    184186      double total = valueArray.Sum();
    185187
     
    193195    }
    194196    private static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
    195       var sourceArray = source.ToArray();
    196       var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);
     197      var valueArray = PrepareProportional(source.ToArray(), weights, windowing, inverseProportional);
     198      var list = new LinkedList<Tuple<T, double>>(source.Zip(valueArray, Tuple.Create));
    197199      double total = valueArray.Sum();
    198200
    199       HashSet<int> chosenIndices = new HashSet<int>();
    200       while (chosenIndices.Count < sourceArray.Length) {
    201         int index = -1;
    202         double ball = 0, sum = random.NextDouble() * total;
     201      while (list.Count > 0) {       
     202        var cur = list.First;       
     203        double ball = cur.Value.Item2, sum = random.NextDouble() * total; // assert: sum < total. When there is only one item remaining: sum < ball
    203204        while (ball < sum) {
    204           index++;
    205           if (!chosenIndices.Contains(index))
    206             ball += valueArray[index];
    207         }
    208         index = index >= 0 ? index : Enumerable.Range(0, sourceArray.Length).First(x => !chosenIndices.Contains(x));
    209         yield return sourceArray[index];
    210         chosenIndices.Add(index);
    211         total -= valueArray[index];
    212       }
    213     }
     205          cur = cur.Next;
     206          ball += cur.Value.Item2;
     207        }
     208        yield return cur.Value.Item1;
     209        list.Remove(cur);
     210        total -= cur.Value.Item2;
     211      }
     212    }
     213
    214214    private static double[] PrepareProportional<T>(IList<T> sourceArray, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
    215215      double maxValue = double.MinValue, minValue = double.MaxValue;
     
    275275  }
    276276}
     277
Note: See TracChangeset for help on using the changeset viewer.