Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
05/14/12 17:22:56 (12 years ago)
Author:
abeham
Message:

#1614

  • moved extension methods to trunk and added reference to HeuristicLab.Random
File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common/3.3/ExtensionMethods.cs

    r7807 r7813  
    2020#endregion
    2121
    22 using System;
    2322using System.Collections.Generic;
    2423using System.Linq;
    … …  
    2726namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common {
    2827  public static class ExtensionMethods {
    29 
    30     #region Choosing from a sequence
    31     /// <summary>
    32     /// Chooses one elements from a sequence giving each element an equal chance.
    33     /// </summary>
    34     /// <remarks>
    35     /// Runtime complexity is O(1) for sequences that are of type <see cref="IList{T}"/> and
    36     /// O(N) for all other.
    37     /// </remarks>
    38     /// <exception cref="ArgumentException">If the sequence is empty.</exception>
    39     /// <typeparam name="T">The type of the items to be selected.</typeparam>
    40     /// <param name="source">The sequence of elements.</param>
    41     /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
    42     /// <param name="count">The number of items to be selected.</param>
    43     /// <returns>An element that has been chosen randomly from the sequence.</returns>
    44     public static T SampleRandom<T>(this IEnumerable<T> source, IRandom random) {
    45       if (!source.Any()) throw new ArgumentException("sequence is empty.", "source");
    46       return source.SampleRandom(random, 1).First();
    47     }
    48     /// <summary>
    49     /// Chooses <paramref name="count"/> elements from a sequence with repetition with equal chances for each element.
    50     /// </summary>
    51     /// <remarks>
    52     /// Runtime complexity is O(count) for sequences that are <see cref="IList{T}"/> and
    53     /// O(N * count) for all other. No exception is thrown if the sequence is empty.
    54     ///
    55     /// The method is online.
    56     /// </remarks>
    57     /// <typeparam name="T">The type of the items to be selected.</typeparam>
    58     /// <param name="source">The sequence of elements.</param>
    59     /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
    60     /// <param name="count">The number of items to be selected.</param>
    61     /// <returns>A sequence of elements that have been chosen randomly.</returns>
    62     public static IEnumerable<T> SampleRandom<T>(this IEnumerable<T> source, IRandom random, int count) {
    63       var listSource = source as IList<T>;
    64       if (listSource != null) {
    65         while (count > 0) {
    66           yield return listSource[random.Next(listSource.Count)];
    67           count--;
    68         }
    69       } else {
    70         while (count > 0) {
    71           var enumerator = source.GetEnumerator();
    72           enumerator.MoveNext();
    73           T selectedItem = enumerator.Current;
    74           int counter = 1;
    75           while (enumerator.MoveNext()) {
    76             counter++;
    77             if (counter * random.NextDouble() < 1.0)
    78               selectedItem = enumerator.Current;
    79           }
    80           yield return selectedItem;
    81           count--;
    82         }
    83       }
    84     }
    85     /// <summary>
    86     /// Chooses <paramref name="count"/> elements from a sequence without repetition with equal chances for each element.
    87     /// The items are returned in the same order as they appear in the sequence.
    88     /// </summary>
    89     /// <remarks>
    90     /// Runtime complexity is O(N) for all sequences.
    91     /// No exception is thrown if the sequence contains less items than there are to be selected.
    92     ///
    93     /// The method is online.
    94     /// </remarks>
    95     /// <typeparam name="T">The type of the items to be selected.</typeparam>
    96     /// <param name="source">The sequence of elements.</param>
    97     /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
    98     /// <param name="count">The number of items to be selected.</param>
    99     /// <returns>A sequence of elements that have been chosen randomly.</returns>
    100     public static IEnumerable<T> SampleRandomWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count) {
    101       int remaining = source.Count();
    102       foreach (var item in source) {
    103         if (random.NextDouble() * remaining < count) {
    104           count--;
    105           yield return item;
    106           if (count <= 0) break;
    107         }
    108         remaining--;
    109       }
    110     }
    111 
    112     /// <summary>
    113     /// Chooses elements out of a sequence with repetition. The chance that an item is selected is proportional or inverse-proportional
    114     /// to the <paramref name="weights"/>.
    115     /// </summary>
    116     /// <remarks>
    117     /// In case both <paramref name="inverseProportional"/> and <paramref name="windowing"/> are false values must be &gt; 0,
    118     /// otherwise an InvalidOperationException is thrown.
    119     ///
    120     /// The method internally holds two arrays: One that is the sequence itself and another one for the values.
    121     /// </remarks>
    122     /// <typeparam name="T">The type of the items to be selected.</typeparam>
    123     /// <param name="source">The sequence of elements.</param>
    124     /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
    125     /// <param name="count">The number of items to be selected.</param>
    126     /// <param name="weights">The weight values for the items.</param>
    127     /// <param name="windowing">Whether to scale the proportional values or not.</param>
    128     /// <param name="inverseProportional">Determines whether to choose proportionally (false) or inverse-proportionally (true).</param>
    129     /// <returns>A sequence of selected items. The sequence might contain the same item more than once.</returns>
    130     public static IEnumerable<T> SampleProportional<T>(this IEnumerable<T> source, IRandom random, int count, IEnumerable<double> weights, bool windowing = true, bool inverseProportional = false) {
    131       return source.SampleProportional(random, weights, windowing, inverseProportional).Take(count);
    132     }
    133     /// <summary>
    134     /// Same as <seealso cref="SampleProportional<T>"/>, but chooses an item exactly once.
    135     /// </summary>
    136     /// <remarks>
    137     /// In case both <paramref name="inverseProportional"/> and <paramref name="windowing"/> are false values must be &gt; 0,
    138     /// otherwise an InvalidOperationException is thrown.
    139     ///
    140     /// The method internally holds two arrays: One that is the sequence itself and another one for the values.
    141     /// </remarks>
    142     /// <typeparam name="T">The type of the items to be selected.</typeparam>
    143     /// <param name="source">The sequence of elements.</param>
    144     /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
    145     /// <param name="count">The number of items to be selected.</param>
    146     /// <param name="weights">The weight values for the items.</param>
    147     /// <param name="windowing">Whether to scale the proportional values or not.</param>
    148     /// <param name="maximization">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
    149     /// <returns>A sequence of selected items.</returns>
    150     public static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count, IEnumerable<double> weights, bool windowing = true, bool inverseProportional = false) {
    151       return source.SampleProportionalWithoutRepetition(random, weights, windowing, inverseProportional).Take(count);
    152     }
    153     #region Proportional Helpers
    154     private static IEnumerable<T> SampleProportional<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
    155       var sourceArray = source.ToArray();
    156       var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);
    157       double total = valueArray.Sum();
    158 
    159       while (true) {
    160         int index = 0;
    161         double ball = valueArray[index], sum = random.NextDouble() * total;
    162         while (ball < sum)
    163           ball += valueArray[++index];
    164         yield return sourceArray[index];
    165       }
    166     }
    167     private static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
    168       var sourceArray = source.ToArray();
    169       var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);
    170       double total = valueArray.Sum();
    171 
    172       HashSet<int> chosenIndices = new HashSet<int>();
    173       while (chosenIndices.Count < sourceArray.Length) {
    174         int index = 0;
    175         double ball = valueArray[index], sum = random.NextDouble() * total;
    176         while (ball < sum) {
    177           index++;
    178           if (!chosenIndices.Contains(index))
    179             ball += valueArray[++index];
    180         }
    181         yield return sourceArray[index];
    182         chosenIndices.Add(index);
    183         total -= valueArray[index];
    184       }
    185     }
    186     private static double[] PrepareProportional<T>(IList<T> sourceArray, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
    187       double maxValue = double.MinValue, minValue = double.MaxValue;
    188       double[] valueArray = new double[sourceArray.Count];
    189 
    190       var weightsEnum = weights.GetEnumerator();
    191       for (int i = 0; i < sourceArray.Count && weightsEnum.MoveNext(); i++) {
    192         valueArray[i] = weightsEnum.Current;
    193         if (valueArray[i] > maxValue) maxValue = valueArray[i];
    194         if (valueArray[i] < minValue) minValue = valueArray[i];
    195       }
    196       if (minValue == maxValue) {  // all values are equal
    197         for (int i = 0; i < sourceArray.Count; i++) {
    198           valueArray[i] = 1.0;
    199         }
    200       } else {
    201         if (windowing) {
    202           if (inverseProportional) InverseProportionalScale(valueArray, minValue);
    203           else ProportionalScale(valueArray, maxValue);
    204         } else {
    205           if (minValue < 0.0) throw new InvalidOperationException("Proportional selection without windowing does not work with values < 0.");
    206           if (inverseProportional) InverseProportionalScale(valueArray, 2 * maxValue);
    207         }
    208       }
    209       return valueArray;
    210     }
    211     private static void ProportionalScale(double[] values, double minValue) {
    212       for (int i = 0; i < values.Length; i++) {
    213         values[i] = values[i] - minValue;
    214       }
    215     }
    216     private static void InverseProportionalScale(double[] values, double maxValue) {
    217       for (int i = 0; i < values.Length; i++) {
    218         values[i] = maxValue - values[i];
    219       }
    220     }
    221     #endregion
    222 
    223     /// <summary>
    224     /// Selects all elements in the sequence that are maximal with respect to the given value.
    225     /// </summary>
    226     /// <remarks>
    227     /// Runtime complexity of the operation is O(N).
    228     /// </remarks>
    229     /// <typeparam name="T">The type of the elements.</typeparam>
    230     /// <param name="source">The enumeration in which the items with a maximal value should be found.</param>
    231     /// <param name="valueSelector">The function that selects the value to compare.</param>
    232     /// <returns>All elements in the enumeration where the selected value is the maximum.</returns>
    233     public static IEnumerable<T> MaxItems<T>(this IEnumerable<T> source, Func<T, IComparable> valueSelector) {
    234       IEnumerator<T> enumerator = source.GetEnumerator();
    235       if (!enumerator.MoveNext()) return Enumerable.Empty<T>();
    236       IComparable max = valueSelector(enumerator.Current);
    237       var result = new List<T>();
    238       result.Add(enumerator.Current);
    239 
    240       while (enumerator.MoveNext()) {
    241         T item = enumerator.Current;
    242         IComparable comparison = valueSelector(item);
    243         if (comparison.CompareTo(max) > 0) {
    244           result.Clear();
    245           result.Add(item);
    246           max = comparison;
    247         } else if (comparison.CompareTo(max) == 0) {
    248           result.Add(item);
    249         }
    250       }
    251       return result;
    252     }
    253 
    254     /// <summary>
    255     /// Selects all elements in the sequence that are minimal with respect to the given value.
    256     /// </summary>
    257     /// <remarks>
    258     /// Runtime complexity of the operation is O(N).
    259     /// </remarks>
    260     /// <typeparam name="T">The type of the elements.</typeparam>
    261     /// <param name="source">The enumeration in which items with a minimal value should be found.</param>
    262     /// <param name="valueSelector">The function that selects the value.</param>
    263     /// <returns>All elements in the enumeration where the selected value is the minimum.</returns>
    264     public static IEnumerable<T> MinItems<T>(this IEnumerable<T> source, Func<T, IComparable> valueSelector) {
    265       IEnumerator<T> enumerator = source.GetEnumerator();
    266       if (!enumerator.MoveNext()) return Enumerable.Empty<T>();
    267       IComparable min = valueSelector(enumerator.Current);
    268       var result = new List<T>();
    269       result.Add(enumerator.Current);
    270 
    271       while (enumerator.MoveNext()) {
    272         T item = enumerator.Current;
    273         IComparable comparison = valueSelector(item);
    274         if (comparison.CompareTo(min) < 0) {
    275           result.Clear();
    276           result.Add(item);
    277           min = comparison;
    278         } else if (comparison.CompareTo(min) == 0) {
    279           result.Add(item);
    280         }
    281       }
    282       return result;
    283     }
    284     #endregion
    285 
    286     #region Shuffling
    287     /// <summary>
    288     /// Shuffles an enumerable and returns a new enumerable according to the Fisher-Yates shuffle.
    289     /// </summary>
    290     /// <remarks>
    291     /// Note that the source enumerable is transformed into an array.
    292     ///
    293     /// The implementation is described in http://stackoverflow.com/questions/1287567/c-is-using-random-and-orderby-a-good-shuffle-algorithm.
    294     /// </remarks>
    295     /// <typeparam name="T">The type of the items that are to be shuffled.</typeparam>
    296     /// <param name="source">The enumerable that contains the items.</param>
    297     /// <param name="random">The random number generator, its Next(n) method must deliver uniformly distributed random numbers in the range [0;n).</param>
    298     /// <returns>An enumerable with the elements shuffled.</returns>
    299     public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, IRandom random) {
    300       T[] elements = source.ToArray();
    301       for (int i = elements.Length - 1; i > 0; i--) {
    302         // Swap element "i" with a random earlier element (including itself)
    303         int swapIndex = random.Next(i + 1);
    304         yield return elements[swapIndex];
    305         elements[swapIndex] = elements[i];
    306         // we don't actually perform the swap, we can forget about the
    307         // swapped element because we already returned it.
    308       }
    309       yield return elements[0];
    310     }
    311     #endregion
    312 
    31328    #region Graph walk
    31429    /// <summary>
    … …  
    33954    }
    34055    #endregion
    341 
    342     #region Matrix operations
    343     /// <summary>
    344     /// Returns a transposed matrix of the given <paramref name="matrix"/>.
    345     /// </summary>
    346     /// <typeparam name="T">The type of the matrix</typeparam>
    347     /// <param name="matrix">The matrix that should be transposed.</param>
    348     /// <returns>The transposed matrix.</returns>
    349     public static T[,] Transpose<T>(this T[,] matrix) {
    350       var result = new T[matrix.GetLength(1), matrix.GetLength(0)];
    351       for (int i = 0; i < matrix.GetLength(0); i++)
    352         for (int j = 0; j < matrix.GetLength(1); j++)
    353           result[j, i] = matrix[i, j];
    354       return result;
    355     }
    356     #endregion
    35756  }
    35857}
Note: See TracChangeset for help on using the changeset viewer.