Changeset 11799 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common

Timestamp:

01/19/15 20:09:12 (10 years ago)

Author:

gkronber

Message:

#2283: performance tuning and reactivated random-roll-out policy in sequential search

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common

Files:

• Extensions.cs (modified) (2 diffs)
• HeuristicLab.Common.csproj (modified) (1 diff)
• MostRecentlyUsedCache.cs (added)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/Extensions.cs

@@ -12 +12 @@
 
     public static T SelectRandom<T>(this IEnumerable<T> xs, Random rand) {
-      var xsArr = xs.ToArray();
-      return xsArr[rand.Next(xsArr.Length)];
+      var n = xs.Count();
+      return xs.ElementAt(rand.Next(n));
     }
 
-    public static IEnumerable<T> SampleProportional<T>(this IEnumerable<T> source, Random random, IEnumerable<double> weights) {
-      var sourceArray = source.ToArray();
-      var valueArray = weights.ToArray();
-      double total = valueArray.Sum();
+    public static T SampleProportional<T>(this IEnumerable<T> elements, Random random, IEnumerable<double> weights) {
+      double total = weights.Sum();
 
-      while (true) {
-        int index = 0;
-        double ball = valueArray[index], sum = random.NextDouble() * total;
-        while (ball < sum)
-          ball += valueArray[++index];
-        yield return sourceArray[index];
+      var elemEnumerator = elements.GetEnumerator();
+      elemEnumerator.MoveNext();
+      var weightEnumerator = weights.GetEnumerator();
+      weightEnumerator.MoveNext();
+
+      var r = random.NextDouble() * total;
+      var agg = weightEnumerator.Current;
+
+      while (agg < r) {
+        weightEnumerator.MoveNext();
+        elemEnumerator.MoveNext();
+        agg += weightEnumerator.Current;
       }
+      return elemEnumerator.Current;
     }
 
@@ -44 +49 @@
         var y = yEnum.Current;
         s += (x - meanX) * (y - meanY);
-        ssX += Math.Pow(x - meanX, 2);
-        ssY += Math.Pow(y - meanY, 2);
+        ssX += (x - meanX) * (x - meanX);
+        ssY += (y - meanY) * (y - meanY);
       }
       if (xEnum.MoveNext() | yEnum.MoveNext()) throw new ArgumentException("lengths are not equal");

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/HeuristicLab.Common.csproj

@@ -43 +43 @@
     <Compile Include="ConsoleEx.cs" />
     <Compile Include="Extensions.cs" />
+    <Compile Include="MostRecentlyUsedCache.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="Rand.cs" />