Changeset 15341 for branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis.Base/Extensions/StringExtensions.cs

Timestamp:

08/28/17 09:03:34 (7 years ago)

Author:

pkimmesw

Message:

#2665 Testet Problems, Improved Performance

File:

• branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis.Base/Extensions/StringExtensions.cs (modified) (2 diffs)

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis.Base/Extensions/StringExtensions.cs

@@ -5 +5 @@
     public static bool IsNumeric(this string str) {
       int n;
-      return int.TryParse("123", out n);
+      return int.TryParse(str, out n);
+    }
+
+    /// <summary>
+    /// https://github.com/DanHarltey/Fastenshtein
+    /// </summary>
+    public static int LevenshteinDistance(this string source, string target) {
+      if (target.Length == 0) {
+        return source.Length;
+      }
+
+      int[] costs = new int[target.Length];
+
+      // Add indexing for insertion to first row
+      for (int i = 0; i < costs.Length;) {
+        costs[i] = ++i;
+      }
+
+      for (int i = 0; i < source.Length; i++) {
+        // cost of the first index
+        int cost = i;
+        int addationCost = i;
+
+        // cache value for inner loop to avoid index lookup and bonds checking, profiled this is quicker
+        char value1Char = source[i];
+
+        for (int j = 0; j < target.Length; j++) {
+          int insertionCost = cost;
+
+          cost = addationCost;
+
+          // assigning this here reduces the array reads we do, improvement of the old version
+          addationCost = costs[j];
+
+          if (value1Char != target[j]) {
+            if (insertionCost < cost) {
+              cost = insertionCost;
+            }
+
+            if (addationCost < cost) {
+              cost = addationCost;
+            }
+
+            ++cost;
+          }
+
+          costs[j] = cost;
+        }
+      }
+
+      return costs[costs.Length - 1];
     }
 
@@ -11 +61 @@
     /// https://www.dotnetperls.com/levenshtein
     /// </summary>
-    public static int LevenshteinDistance(this string source, string target) {
+    public static int LevenshteinDistance2(this string source, string target) {
       if (source == null && target == null) return 0;
       if (source == null) return target.Length;