Changeset 11662

Timestamp:

12/05/14 10:40:26 (9 years ago)

Author:

mkommend

Message:

#2282: Refactored LinkageTree and adapted unit tests.

Location:

branches/Parameter-less Population Pyramid

Files:

• HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageTree.cs (modified) (9 diffs)
• ParameterlessPopulationPyramid.Test/LinkageTreeTest.cs (modified) (2 diffs)

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

@@ -23 +23 @@
 using System.Collections.Generic;
 using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
+using HeuristicLab.Common;
 using HeuristicLab.Core;
-using HeuristicLab.Data;
-using HeuristicLab.Parameters;
-using HeuristicLab.Random;
-using HeuristicLab.Common;
 
 namespace HeuristicLab.Algorithms.ParameterlessPopulationPyramid {
@@ -52 +47 @@
       return list;
     }
-    
+
+    public static IEnumerable<T> Shuffle<T>(this IList<T> source, IRandom random) {
+      for (int i = source.Count - 1; i > 0; i--) {
+        // Swap element "i" with a random earlier element (including itself)
+        int swapIndex = random.Next(i + 1);
+        yield return source[swapIndex];
+        source[swapIndex] = source[i];
+        // we don't actually perform the swap, we can forget about the
+        // swapped element because we already returned it.
+      }
+      yield return source[0];
+    }
+
   }
   public class LinkageTree {
 
-    private int[][][] occurances;
-    private List<int>[] clusters;
-    private List<int> cluster_ordering;
-    private readonly int Length;
+    private readonly int[][][] occurances;
+    private readonly List<int>[] clusters;
+    private readonly List<int> clusterOrdering;
+    private readonly int length;
 
     public LinkageTree(int length) {
-      Length = length;
-      occurances = new int[Length][][];
-
-      for (int i = 1; i < Length; i++) {
+      this.length = length;
+      occurances = new int[length][][];
+
+      for (int i = 1; i < length; i++) {
         occurances[i] = new int[i][];
         for (int j = 0; j < i; j++) {
@@ -71 +78 @@
         }
       }
-      clusters = new List<int>[2 * Length - 1];
+      clusters = new List<int>[2 * length - 1];
       for (int i = 0; i < clusters.Length; i++) {
         clusters[i] = new List<int>();
       }
+      clusterOrdering = new List<int>();
 
       // first "length" clusters just contain a single gene
-      for (int i = 0; i < Length; i++) {
+      for (int i = 0; i < length; i++) {
         clusters[i].Add(i);
       }
@@ -83 +91 @@
 
     public void Add(bool[] solution) {
-      if (solution.Length != Length) throw new ArgumentException("The individual has not the correct length.");
+      if (solution.Length != length) throw new ArgumentException("The individual has not the correct length.");
       for (int i = 1; i < solution.Length; i++) {
         for (int j = 0; j < i; j++) {
@@ -97 +105 @@
     private static double NegativeEntropy(int[] counts, double total) {
       double sum = 0;
-      double p;
       foreach (var value in counts) {
-        if (value != 0) {
-          p = value / total;
-          sum += (p * Math.Log(p));
-        }
+        if (value == 0) continue;
+        var p = value / total;
+        sum += (p * Math.Log(p));
+
       }
       return sum;
     }
-    
+
     private double EntropyDistance(int i, int j) {
       if (i < j) {
@@ -126 +133 @@
       double together = NegativeEntropy(entry, total);
       // If together there is 0 entropy, the distance is zero
-      double ratio = 0;
-      if (together != 0) {
-        ratio = 2 - (separate / together);
-      }
-      return ratio;
+      if (together.IsAlmost(0)) {
+        return 0.0;
+      }
+      return 2 - (separate / together);
     }
 
     public void Rebuild(IRandom rand) {
       // Keep track of which clusters have not been merged
-      List<int> 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;
-      }
+      var topLevel = Enumerable.Range(0, length).ToList();
+      bool[] useful = Enumerable.Repeat(true, clusters.Length).ToArray();
+
 
       // Store the distances between all clusters
       double[,] distances = new double[clusters.Length, clusters.Length];
-      for (int i = 1; i < Length; i++) {
+      for (int i = 1; i < length; i++) {
         for (int j = 0; j < i; j++) {
           distances[i, j] = EntropyDistance(clusters[i][0], clusters[j][0]);
@@ -158 +159 @@
 
       // build all clusters of size greater than 1
-      for (int index = Length; index < clusters.Length; index++) {
+      for (int index = length; index < clusters.Length; index++) {
         // Shuffle everything not yet in the path
         topLevel.ShuffleInPlace(rand, end_of_path, topLevel.Count);
@@ -195 +196 @@
 
         // Only keep a cluster if the distance between the joining clusters is > zero
-        bool keep = !distances[first, second].IsAlmost(0d);
+        bool keep = !distances[first, second].IsAlmost(0.0);
         useful[first] = keep;
         useful[second] = keep;
@@ -230 +231 @@
       }
       // Extract the useful clusters
-      cluster_ordering = new List<int>();
+      clusterOrdering.Clear();
       // Add all useful clusters. The last one is never useful.
       for (int i = 0; i < useful.Length - 1; i++) {
-        if (useful[i]) cluster_ordering.Add(i);
+        if (useful[i]) clusterOrdering.Add(i);
       }
       // TODO Shuffle cluster ordering
-      cluster_ordering.ShuffleInPlace(rand);
-      cluster_ordering.Sort((i, j) => clusters[i].Count.CompareTo(clusters[j].Count));
+      clusterOrdering.ShuffleInPlace(rand);
+      clusterOrdering.Sort((i, j) => clusters[i].Count.CompareTo(clusters[j].Count));
     }
 

branches/Parameter-less Population Pyramid/ParameterlessPopulationPyramid.Test/LinkageTreeTest.cs

@@ -1 +1 @@
 using System;
+using System.Collections.Generic;
 using System.Linq;
-using System.Collections;
-using System.Collections.Generic;
 using HeuristicLab.Algorithms.ParameterlessPopulationPyramid;
 using HeuristicLab.Random;
@@ -71 +70 @@
       tree.Rebuild(rand);
       PrivateObject hidden = new PrivateObject(tree);
-      var ordering = (List<int>)hidden.GetField("cluster_ordering");
+      var ordering = (List<int>)hidden.GetField("clusterOrdering");
       var clusters = (List<int>[])hidden.GetField("clusters");
       int[][] comparable = new int[ordering.Count][];
-      for (int i=0; i < ordering.Count; i++) {
+      for (int i = 0; i < ordering.Count; i++) {
         var found = clusters[ordering[i]].ToArray();
         Array.Sort(found);
         Assert.IsTrue(correctClusters[i].SequenceEqual(found));
-      }      
+      }
     }
   }