Changeset 11799 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs

Timestamp:

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

Author:

gkronber

Message:

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

File:

• branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs (modified) (2 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs

@@ -1 +1 @@
 using System;
+using System.Collections.Concurrent;
 using System.Collections.Generic;
+using System.Collections.Specialized;
 using System.Linq;
 using System.Net;
@@ -72 +74 @@
 
 
+    // most-recently-used caching (with limited capacity) for canonical representations
+    MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
     // right now only + and * is supported
-    //private Dictionary<string, string> cache = new Dictionary<string, string>();
     public string CanonicalRepresentation(string phrase) {
-      string res;
-      //if (!cache.TryGetValue(phrase, out res)) {
-      var terms = phrase.Split('+').Select(t => t.Replace("*", ""));
-      var terminalTerms = terms.Where(t => t.All(ch => grammar.IsTerminal(ch)));
-      var nonTerminalTerms = terms.Where(t => t.Any(ch => grammar.IsNonTerminal(ch)));
+      string canonicalPhrase;
+      if (!canonicalPhraseCache.TryGetValue(phrase, out canonicalPhrase)) {
+        var terms = phrase.Split('+');
+        var canonicalTerms = new SortedSet<string>();
+        // only the last term might contain a NT-symbol. make sure this term is added at the end
+        for (int i = 0; i < terms.Length - 1; i++) {
+          canonicalTerms.Add(CanonicalTerm(terms[i]));
+        }
 
-      res = string.Join("+", terminalTerms.Select(term => CanonicalTerm(term)).OrderBy(term => term).Concat(nonTerminalTerms.Select(term => CanonicalTerm(term))));
-      //cache[phrase] = res;
-      //}
-      return res;
+        var sb = new StringBuilder(phrase.Length);
+        foreach (var t in canonicalTerms)
+          sb.Append(t).Append('+');
+
+        sb.Append(CanonicalTerm(terms[terms.Length - 1]));
+        sb.Append(phrase.Length - sb.Length);
+        canonicalPhrase = sb.ToString();
+        canonicalPhraseCache.Add(phrase, canonicalPhrase);
+      }
+      return canonicalPhrase;
     }
 
+    // cache the canonical form of terms for performance reasons
+    private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
     private string CanonicalTerm(string term) {
-      return string.Join("", term.OrderByDescending(ch => (byte)ch)); // we want to have the up-case characters last
+      string canonicalTerm;
+      if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm)) {
+        // add
+        var chars = term.ToCharArray();
+        Array.Sort(chars);
+        var sb = new StringBuilder(chars.Length);
+        // we want to have the up-case characters last
+        for (int i = chars.Length - 1; i >= 0; i--) {
+          if (chars[i] != '*') sb.Append(chars[i]);
+        }
+        canonicalTerm = sb.ToString();
+        canonicalTermDictionary.Add(term, canonicalTerm);
+      }
+      return canonicalTerm;
     }
   }