Changeset 11674 for branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageTree.cs

Timestamp:

12/09/14 17:00:53 (9 years ago)

Author:

mkommend

Message:

#2282: Performance improvements in PPP (reduced memory allocations and more efficient implementation).

File:

• branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageTree.cs (modified) (10 diffs)

branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageTree.cs

@@ -27 +27 @@
 
 namespace HeuristicLab.Algorithms.ParameterlessPopulationPyramid {
-  
+
   public class LinkageTree {
 
@@ -66 +66 @@
         for (int j = 0; j < i; j++) {
           // Updates the entry of the 4 long array based on the two bits
-          var pattern = (Convert.ToInt32(solution[j]) << 1) + Convert.ToInt32(solution[i]);
+
+          var pattern = (Convert.ToByte(solution[j]) << 1) + Convert.ToByte(solution[i]);
           occurances[i][j][pattern]++;
         }
@@ -78 +79 @@
     private static double NegativeEntropy(int[] counts, double total) {
       double sum = 0;
-      foreach (var value in counts) {
-        if (value == 0) continue;
-        var p = value / total;
-        sum += (p * Math.Log(p));
+      for (int i = 0; i < counts.Length; i++) {
+        if (counts[i] != 0) {
+          sum += ((counts[i] / total) * Math.Log(counts[i] / total));
+        }
       }
       return sum;
@@ -88 +89 @@
     // Uses the frequency table to calcuate the entropy distance between two indices.
     // In the GECCO paper, calculates Equation 1
+    private int[] bits = new int[4];
     private double EntropyDistance(int i, int j) {
       // This ensures you are using the lower triangular part of "occurances"
@@ -96 +98 @@
       }
       var entry = occurances[i][j];
-      int[] bits = new int[4];
       // extracts the occurrences of the individual bits
       bits[0] = entry[0] + entry[2];  // i zero
@@ -114 +115 @@
     }
 
+
+
     // Performs O(N^2) clustering based on the method described in:
     // "Optimal implementations of UPGMA and other common clustering algorithms"
     // by I. Gronau and S. Moran
     // In the GECCO paper, Figure 2 is a simplified version of this algorithm.
+    private double[][] distances;
     private void Rebuild() {
+      if (distances == null) {
+        distances = new double[clusters.Length * 2 - 1][];
+        for (int i = 0; i < distances.Length; i++)
+          distances[i] = new double[clusters.Length * 2 - 1];
+      }
+
+
       // Keep track of which clusters have not been merged
-      var topLevel = Enumerable.Range(0, length).ToList();
-      bool[] useful = Enumerable.Repeat(true, clusters.Length).ToArray();
+      var topLevel = new List<int>(length);
+      for (int i = 0; i < length; i++)
+        topLevel.Add(i);
+
+      bool[] useful = new bool[clusters.Length];
+      for (int i = 0; i < useful.Length; i++)
+        useful[i] = true;
 
       // Store the distances between all clusters
-      double[,] distances = new double[clusters.Length, clusters.Length];
       for (int i = 1; i < length; i++) {
         for (int j = 0; j < i; j++) {
-          distances[i, j] = EntropyDistance(clusters[i][0], clusters[j][0]);
+          distances[i][j] = EntropyDistance(clusters[i][0], clusters[j][0]);
           // make it symmetric
-          distances[j, i] = distances[i, j];
+          distances[j][i] = distances[i][j];
         }
       }
@@ -139 +154 @@
       for (int index = length; index < clusters.Length; index++) {
         // Shuffle everything not yet in the path
-        topLevel.ShuffleInPlace(rand, end_of_path, topLevel.Count-1);
+        topLevel.ShuffleInPlace(rand, end_of_path, topLevel.Count - 1);
 
         // if nothing in the path, just add a random usable node
@@ -151 +166 @@
           // best_index stores the location of the best thing in the top level
           int best_index = end_of_path;
-          double min_dist = distances[final, topLevel[best_index]];
+          double min_dist = distances[final][topLevel[best_index]];
           // check all options which might be closer to "final" than "topLevel[best_index]"
           for (int option = end_of_path + 1; option < topLevel.Count; option++) {
-            if (distances[final, topLevel[option]] < min_dist) {
-              min_dist = distances[final, topLevel[option]];
+            if (distances[final][topLevel[option]] < min_dist) {
+              min_dist = distances[final][topLevel[option]];
               best_index = option;
             }
           }
           // If the current last two in the path are minimally distant
-          if (end_of_path > 1 && min_dist >= distances[final, topLevel[end_of_path - 2]]) {
+          if (end_of_path > 1 && min_dist >= distances[final][topLevel[end_of_path - 2]]) {
             break;
           }
@@ -173 +188 @@
 
         // Only keep a cluster if the distance between the joining clusters is > zero
-        bool keep = !distances[first, second].IsAlmost(0.0);
+        bool keep = !distances[first][second].IsAlmost(0.0);
         useful[first] = keep;
         useful[second] = keep;
@@ -191 +206 @@
           }
           // Use the previous distances to calculate the joined distance
-          double first_distance = distances[first, x];
+          double first_distance = distances[first][x];
           first_distance *= clusters[first].Count;
-          double second_distance = distances[second, x];
+          double second_distance = distances[second][x];
           second_distance *= clusters[second].Count;
-          distances[x, index] = ((first_distance + second_distance)
+          distances[x][index] = ((first_distance + second_distance)
               / (clusters[first].Count + clusters[second].Count));
           // make it symmetric
-          distances[index, x] = distances[x, index];
+          distances[index][x] = distances[x][index];
           i++;
         }