Free cookie consent management tool by TermsFeed Policy Generator

Changeset 7812


Ignore:
Timestamp:
05/14/12 17:20:43 (12 years ago)
Author:
abeham
Message:

#1848

  • Added extension methods to trunk
Location:
trunk/sources
Files:
2 added
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Common/3.3/HeuristicLab.Common-3.3.csproj

    r7626 r7812  
    124124    <Compile Include="Content\IStorableContent.cs" />
    125125    <Compile Include="Constants.cs" />
     126    <Compile Include="EnumerableExtensions.cs" />
     127    <Compile Include="MatrixExtensions.cs" />
    126128    <Compile Include="NaturalStringComparer.cs" />
    127129    <Compile Include="ObjectExtensions.cs" />
  • trunk/sources/HeuristicLab.Random/3.3/RandomEnumerable.cs

    r7259 r7812  
    2222using System;
    2323using System.Collections.Generic;
     24using System.Linq;
     25using HeuristicLab.Core;
    2426
    2527namespace HeuristicLab.Random {
    26   public class RandomEnumerable {
     28  public static class RandomEnumerable {
    2729    public static IEnumerable<int> SampleRandomNumbers(int maxElement, int count) {
    2830      return SampleRandomNumbers(Environment.TickCount, 0, maxElement, count);
     
    4850      }
    4951    }
     52
     53    /// <summary>
     54    /// Chooses one elements from a sequence giving each element an equal chance.
     55    /// </summary>
     56    /// <remarks>
     57    /// Runtime complexity is O(1) for sequences that are of type <see cref="IList{T}"/> and
     58    /// O(N) for all other.
     59    /// </remarks>
     60    /// <exception cref="ArgumentException">If the sequence is empty.</exception>
     61    /// <typeparam name="T">The type of the items to be selected.</typeparam>
     62    /// <param name="source">The sequence of elements.</param>
     63    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
     64    /// <param name="count">The number of items to be selected.</param>
     65    /// <returns>An element that has been chosen randomly from the sequence.</returns>
     66    public static T SampleRandom<T>(this IEnumerable<T> source, IRandom random) {
     67      if (!source.Any()) throw new ArgumentException("sequence is empty.", "source");
     68      return source.SampleRandom(random, 1).First();
     69    }
     70
     71    /// <summary>
     72    /// Chooses <paramref name="count"/> elements from a sequence with repetition with equal chances for each element.
     73    /// </summary>
     74    /// <remarks>
     75    /// Runtime complexity is O(count) for sequences that are <see cref="IList{T}"/> and
     76    /// O(N * count) for all other. No exception is thrown if the sequence is empty.
     77    ///
     78    /// The method is online.
     79    /// </remarks>
     80    /// <typeparam name="T">The type of the items to be selected.</typeparam>
     81    /// <param name="source">The sequence of elements.</param>
     82    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
     83    /// <param name="count">The number of items to be selected.</param>
     84    /// <returns>A sequence of elements that have been chosen randomly.</returns>
     85    public static IEnumerable<T> SampleRandom<T>(this IEnumerable<T> source, IRandom random, int count) {
     86      var listSource = source as IList<T>;
     87      if (listSource != null) {
     88        while (count > 0) {
     89          yield return listSource[random.Next(listSource.Count)];
     90          count--;
     91        }
     92      } else {
     93        while (count > 0) {
     94          var enumerator = source.GetEnumerator();
     95          enumerator.MoveNext();
     96          T selectedItem = enumerator.Current;
     97          int counter = 1;
     98          while (enumerator.MoveNext()) {
     99            counter++;
     100            if (counter * random.NextDouble() < 1.0)
     101              selectedItem = enumerator.Current;
     102          }
     103          yield return selectedItem;
     104          count--;
     105        }
     106      }
     107    }
     108
     109    /// <summary>
     110    /// Chooses <paramref name="count"/> elements from a sequence without repetition with equal chances for each element.
     111    /// The items are returned in the same order as they appear in the sequence.
     112    /// </summary>
     113    /// <remarks>
     114    /// Runtime complexity is O(N) for all sequences.
     115    /// No exception is thrown if the sequence contains less items than there are to be selected.
     116    ///
     117    /// The method is online.
     118    /// </remarks>
     119    /// <typeparam name="T">The type of the items to be selected.</typeparam>
     120    /// <param name="source">The sequence of elements.</param>
     121    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
     122    /// <param name="count">The number of items to be selected.</param>
     123    /// <returns>A sequence of elements that have been chosen randomly.</returns>
     124    public static IEnumerable<T> SampleRandomWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count) {
     125      int remaining = source.Count();
     126      foreach (var item in source) {
     127        if (random.NextDouble() * remaining < count) {
     128          count--;
     129          yield return item;
     130          if (count <= 0) break;
     131        }
     132        remaining--;
     133      }
     134    }
     135
     136    /// <summary>
     137    /// Chooses elements out of a sequence with repetition. The chance that an item is selected is proportional or inverse-proportional
     138    /// to the <paramref name="weights"/>.
     139    /// </summary>
     140    /// <remarks>
     141    /// In case both <paramref name="inverseProportional"/> and <paramref name="windowing"/> are false values must be &gt; 0,
     142    /// otherwise an InvalidOperationException is thrown.
     143    ///
     144    /// The method internally holds two arrays: One that is the sequence itself and another one for the values.
     145    /// </remarks>
     146    /// <typeparam name="T">The type of the items to be selected.</typeparam>
     147    /// <param name="source">The sequence of elements.</param>
     148    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
     149    /// <param name="count">The number of items to be selected.</param>
     150    /// <param name="weights">The weight values for the items.</param>
     151    /// <param name="windowing">Whether to scale the proportional values or not.</param>
     152    /// <param name="inverseProportional">Determines whether to choose proportionally (false) or inverse-proportionally (true).</param>
     153    /// <returns>A sequence of selected items. The sequence might contain the same item more than once.</returns>
     154    public static IEnumerable<T> SampleProportional<T>(this IEnumerable<T> source, IRandom random, int count, IEnumerable<double> weights, bool windowing = true, bool inverseProportional = false) {
     155      return source.SampleProportional(random, weights, windowing, inverseProportional).Take(count);
     156    }
     157
     158    /// <summary>
     159    /// Same as <seealso cref="SampleProportional<T>"/>, but chooses an item exactly once.
     160    /// </summary>
     161    /// <remarks>
     162    /// In case both <paramref name="inverseProportional"/> and <paramref name="windowing"/> are false values must be &gt; 0,
     163    /// otherwise an InvalidOperationException is thrown.
     164    ///
     165    /// The method internally holds two arrays: One that is the sequence itself and another one for the values.
     166    /// </remarks>
     167    /// <typeparam name="T">The type of the items to be selected.</typeparam>
     168    /// <param name="source">The sequence of elements.</param>
     169    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
     170    /// <param name="count">The number of items to be selected.</param>
     171    /// <param name="weights">The weight values for the items.</param>
     172    /// <param name="windowing">Whether to scale the proportional values or not.</param>
     173    /// <param name="maximization">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
     174    /// <returns>A sequence of selected items.</returns>
     175    public static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count, IEnumerable<double> weights, bool windowing = true, bool inverseProportional = false) {
     176      return source.SampleProportionalWithoutRepetition(random, weights, windowing, inverseProportional).Take(count);
     177    }
     178    #region Proportional Helpers
     179    private static IEnumerable<T> SampleProportional<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
     180      var sourceArray = source.ToArray();
     181      var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);
     182      double total = valueArray.Sum();
     183
     184      while (true) {
     185        int index = 0;
     186        double ball = valueArray[index], sum = random.NextDouble() * total;
     187        while (ball < sum)
     188          ball += valueArray[++index];
     189        yield return sourceArray[index];
     190      }
     191    }
     192    private static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
     193      var sourceArray = source.ToArray();
     194      var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);
     195      double total = valueArray.Sum();
     196
     197      HashSet<int> chosenIndices = new HashSet<int>();
     198      while (chosenIndices.Count < sourceArray.Length) {
     199        int index = 0;
     200        double ball = valueArray[index], sum = random.NextDouble() * total;
     201        while (ball < sum) {
     202          index++;
     203          if (!chosenIndices.Contains(index))
     204            ball += valueArray[++index];
     205        }
     206        yield return sourceArray[index];
     207        chosenIndices.Add(index);
     208        total -= valueArray[index];
     209      }
     210    }
     211    private static double[] PrepareProportional<T>(IList<T> sourceArray, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
     212      double maxValue = double.MinValue, minValue = double.MaxValue;
     213      double[] valueArray = new double[sourceArray.Count];
     214
     215      var weightsEnum = weights.GetEnumerator();
     216      for (int i = 0; i < sourceArray.Count && weightsEnum.MoveNext(); i++) {
     217        valueArray[i] = weightsEnum.Current;
     218        if (valueArray[i] > maxValue) maxValue = valueArray[i];
     219        if (valueArray[i] < minValue) minValue = valueArray[i];
     220      }
     221      if (minValue == maxValue) {  // all values are equal
     222        for (int i = 0; i < sourceArray.Count; i++) {
     223          valueArray[i] = 1.0;
     224        }
     225      } else {
     226        if (windowing) {
     227          if (inverseProportional) InverseProportionalScale(valueArray, minValue);
     228          else ProportionalScale(valueArray, maxValue);
     229        } else {
     230          if (minValue < 0.0) throw new InvalidOperationException("Proportional selection without windowing does not work with values < 0.");
     231          if (inverseProportional) InverseProportionalScale(valueArray, 2 * maxValue);
     232        }
     233      }
     234      return valueArray;
     235    }
     236    private static void ProportionalScale(double[] values, double minValue) {
     237      for (int i = 0; i < values.Length; i++) {
     238        values[i] = values[i] - minValue;
     239      }
     240    }
     241    private static void InverseProportionalScale(double[] values, double maxValue) {
     242      for (int i = 0; i < values.Length; i++) {
     243        values[i] = maxValue - values[i];
     244      }
     245    }
     246    #endregion
     247
     248    /// <summary>
     249    /// Shuffles an enumerable and returns a new enumerable according to the Fisher-Yates shuffle.
     250    /// </summary>
     251    /// <remarks>
     252    /// Note that the source enumerable is transformed into an array.
     253    ///
     254    /// The implementation is described in http://stackoverflow.com/questions/1287567/c-is-using-random-and-orderby-a-good-shuffle-algorithm.
     255    /// </remarks>
     256    /// <typeparam name="T">The type of the items that are to be shuffled.</typeparam>
     257    /// <param name="source">The enumerable that contains the items.</param>
     258    /// <param name="random">The random number generator, its Next(n) method must deliver uniformly distributed random numbers in the range [0;n).</param>
     259    /// <returns>An enumerable with the elements shuffled.</returns>
     260    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, IRandom random) {
     261      T[] elements = source.ToArray();
     262      for (int i = elements.Length - 1; i > 0; i--) {
     263        // Swap element "i" with a random earlier element (including itself)
     264        int swapIndex = random.Next(i + 1);
     265        yield return elements[swapIndex];
     266        elements[swapIndex] = elements[i];
     267        // we don't actually perform the swap, we can forget about the
     268        // swapped element because we already returned it.
     269      }
     270      yield return elements[0];
     271    }
    50272  }
    51273}
Note: See TracChangeset for help on using the changeset viewer.