Changeset 15974

Timestamp:

06/28/18 11:35:13 (6 years ago)

Author:

bburlacu

Message:

#2886: implement LRU cache for storing search nodes, introduce SortedSet for handling priorities, fix serialization and cloning

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• ExpressionClustering/ExpressionClustering.csproj (modified) (1 diff)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/RSquaredEvaluator.cs (modified) (5 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (8 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (17 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/LruCache.cs (added)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs (modified) (14 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Sentence.cs (modified) (1 diff)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs (modified) (1 diff)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj (modified) (1 diff)
• Test/HeuristicLab.snk (added)
• Test/Test.csproj (modified) (2 diffs)

branches/2886_SymRegGrammarEnumeration/ExpressionClustering/ExpressionClustering.csproj

@@ -15 +15 @@
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
-    <PlatformTarget>x64</PlatformTarget>
+    <PlatformTarget>AnyCPU</PlatformTarget>
     <DebugSymbols>true</DebugSymbols>
     <DebugType>full</DebugType>

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/RSquaredEvaluator.cs

@@ -16 +16 @@
   public class RSquaredEvaluator : Item, IGrammarEnumerationAnalyzer {
     public static readonly string BestTrainingQualityResultName = "Best R² (Training)";
+    public static readonly string BestTestQualityResultName = "Best R² (Test)";
     public static readonly string BestTrainingModelResultName = "Best model (Training)";
     public static readonly string BestTrainingSolutionResultName = "Best solution (Training)";
+    public static readonly string BestComplexityResultName = "Best solution complexity";
 
     private static readonly ISymbolicDataAnalysisExpressionTreeInterpreter expressionTreeLinearInterpreter = new SymbolicDataAnalysisExpressionTreeLinearInterpreter();
@@ -42 +44 @@
       algorithm.Started -= OnStarted;
       algorithm.Stopped -= OnStopped;
-
       algorithm.DistinctSentenceGenerated -= AlgorithmOnDistinctSentenceGenerated;
     }
@@ -57 +58 @@
     }
 
-    private void OnStopped(object sender, EventArgs eventArgs) {
-      GrammarEnumerationAlgorithm algorithm = (GrammarEnumerationAlgorithm)sender;
-      if (algorithm.Results.ContainsKey(BestTrainingModelResultName)) {
-        SymbolicRegressionModel model = (SymbolicRegressionModel)algorithm.Results[BestTrainingModelResultName].Value;
-        IRegressionSolution bestTrainingSolution = new RegressionSolution(model, algorithm.Problem.ProblemData);
+    private void OnStopped(object sender, EventArgs eventArgs) { }
 
-        algorithm.Results.AddOrUpdateResult(BestTrainingSolutionResultName, bestTrainingSolution);
-      }
+    private T GetValue<T>(IItem value) where T : struct {
+      var v = value as ValueTypeValue<T>;
+      if (v == null)
+        throw new ArgumentException(string.Format("Item is not of type {0}", typeof(ValueTypeValue<T>)));
+      return v.Value;
     }
 
     private void EvaluateSentence(GrammarEnumerationAlgorithm algorithm, SymbolString symbolString) {
+      var results = algorithm.Results;
+      var grammar = algorithm.Grammar;
       var problemData = algorithm.Problem.ProblemData;
 
@@ -74 +76 @@
 
       double r2 = Evaluate(problemData, tree, OptimizeConstants);
+      double bestR2 = results.ContainsKey(BestTrainingQualityResultName) ? GetValue<double>(results[BestTrainingQualityResultName].Value) : 0.0;
+      if (r2 < bestR2)
+        return;
 
-      double bestR2 = 0.0;
-      if (algorithm.Results.ContainsKey(BestTrainingQualityResultName))
-        bestR2 = ((DoubleValue)algorithm.Results[BestTrainingQualityResultName].Value).Value;
-      bool better = r2 > bestR2;
-      bool equallyGood = r2.IsAlmost(bestR2);
-      bool shorter = false;
+      var bestComplexity = int.MaxValue;
+      if (results.ContainsKey(BestComplexityResultName)) {
+        bestComplexity = GetValue<int>(results[BestComplexityResultName].Value);
+      } else if (algorithm.BestTrainingSentence != null) {
+        bestComplexity = grammar.GetComplexity(algorithm.BestTrainingSentence);
+        results.AddOrUpdateResult(BestComplexityResultName, new IntValue(bestComplexity));
+      }
+      var complexity = grammar.GetComplexity(symbolString);
 
-      if (!better && equallyGood) {
-        shorter = algorithm.BestTrainingSentence != null &&
-          algorithm.Grammar.GetComplexity(algorithm.BestTrainingSentence) > algorithm.Grammar.GetComplexity(symbolString);
-      }
-      if (better || (equallyGood && shorter)) {
-        algorithm.Results.AddOrUpdateResult(BestTrainingQualityResultName, new DoubleValue(r2));
-
-        SymbolicRegressionModel model = new SymbolicRegressionModel(
-          problemData.TargetVariable,
-          tree,
-          expressionTreeLinearInterpreter);
-
-        algorithm.Results.AddOrUpdateResult(BestTrainingModelResultName, model);
-
+      if (r2 > bestR2 || (r2.IsAlmost(bestR2) && complexity < bestComplexity)) {
+        results.AddOrUpdateResult(BestTrainingQualityResultName, new DoubleValue(r2));
+        results.AddOrUpdateResult(BestComplexityResultName, new IntValue(complexity));
         algorithm.BestTrainingSentence = symbolString;
       }
@@ -121 +117 @@
           }
         }
-
-        r2 = double.IsNaN(r2) ? 0.0 : r2;
-
       } else {
-        var target = problemData.TargetVariableTrainingValues;
-
-        SymbolicRegressionModel model = new SymbolicRegressionModel(
-          problemData.TargetVariable,
+        r2 = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(expressionTreeLinearInterpreter,
           tree,
-          expressionTreeLinearInterpreter);
-
-        var estVals = model.GetEstimatedValues(problemData.Dataset, problemData.TrainingIndices);
-        OnlineCalculatorError error;
-        r2 = OnlinePearsonsRCalculator.Calculate(target, estVals, out error);
-        if (error != OnlineCalculatorError.None) r2 = 0.0;
+          double.MinValue,
+          double.MaxValue,
+          problemData,
+          problemData.TrainingIndices,
+          applyLinearScaling: true);
       }
-
-      return r2;
+      return double.IsNaN(r2) ? 0.0 : r2;
     }
   }

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs

@@ -22 +22 @@
   [StorableClass(StorableClassType.AllFieldsAndAllProperties)]
   public class Grammar : DeepCloneable {
-
-    public Symbol StartSymbol { get; }
+    public Symbol StartSymbol { get; private set; }
 
     public Hasher<int> Hasher { get; }
@@ -29 +28 @@
     #region Symbols
 
-    public IReadOnlyDictionary<Symbol, IReadOnlyList<Production>> Productions { get; }
+    public IReadOnlyDictionary<Symbol, IReadOnlyList<Production>> Productions { get; private set; }
 
     public NonterminalSymbol Var;
@@ -79 +78 @@
 
     protected Grammar(Grammar original, Cloner cloner) : base(original, cloner) {
-      VarTerminals = original.VarTerminals.Select(cloner.Clone).ToArray();
-      StartSymbol = cloner.Clone(original.StartSymbol);
-      Hasher = cloner.Clone(original.Hasher); // how to handle circular reference grammar <-> hasher? (the cloner *should* handle it)
+      infixExpressionFormatter = cloner.Clone(original.infixExpressionFormatter);
+
       Productions = original.Productions.ToDictionary(x => cloner.Clone(x.Key), x => (IReadOnlyList<Production>)x.Value.Select(cloner.Clone).ToList());
+      VarTerminals = original.VarTerminals.Select(cloner.Clone).ToList();
+
       Var = cloner.Clone(original.Var);
-      VarTerminals = original.VarTerminals.Select(cloner.Clone).ToList();
       Expr = cloner.Clone(original.Expr);
       Term = cloner.Clone(original.Term);
@@ -95 +94 @@
       InvExpr = cloner.Clone(original.InvExpr);
       InvTerm = cloner.Clone(original.InvTerm);
+
       Addition = cloner.Clone(original.Addition);
       Multiplication = cloner.Clone(original.Multiplication);
@@ -100 +100 @@
       Exp = cloner.Clone(original.Exp);
       Sin = cloner.Clone(original.Sin);
-      Sin = cloner.Clone(original.Sin);
       Inv = cloner.Clone(original.Inv);
       Const = cloner.Clone(original.Const);
 
-
-      constSy = cloner.Clone(original.constSy);
-      varSy = cloner.Clone(original.varSy);
-      addSy = cloner.Clone(original.addSy);
-      mulSy = cloner.Clone(original.mulSy);
-      logSy = cloner.Clone(original.logSy);
-      expSy = cloner.Clone(original.expSy);
-      divSy = cloner.Clone(original.divSy);
-      sinSy = cloner.Clone(original.sinSy);
-
-      rootSy = cloner.Clone(original.rootSy);
-      startSy = cloner.Clone(original.startSy);
-
-      infixExpressionFormatter = cloner.Clone(original.infixExpressionFormatter);
-    }
-
-    public Grammar(string[] variables, IEnumerable<GrammarRule> includedRules) {
+      StartSymbol = Expr;
+      Hasher = cloner.Clone(original.Hasher);
+
+      InitTreeParser(); // easier this way (and less typing)
+    }
+
+    private void InitProductions(string[] variables, IEnumerable<GrammarRule> includedRules) {
       #region Define Symbols
       Var = new NonterminalSymbol("Var");
@@ -210 +199 @@
       Productions = productions;
       #endregion
-
+    }
+
+    private void InitTreeParser() {
       #region Parsing to SymbolicExpressionTree
       var symbolicExpressionGrammar = new TypeCoherentExpressionGrammar();
@@ -229 +220 @@
       infixExpressionFormatter = new InfixExpressionFormatter();
       #endregion
+    }
+
+    public Grammar(string[] variables, IEnumerable<GrammarRule> includedRules) {
+      InitProductions(variables, includedRules);
+      InitTreeParser();
 
       Hasher = new IntHasher(this);
@@ -244 +240 @@
     public double EvaluatePhrase(SymbolString s, IRegressionProblemData problemData, bool optimizeConstants) {
       SymbolicExpressionTree tree = ParseSymbolicExpressionTree(s);
-
-      double r2 = RSquaredEvaluator.Evaluate(problemData, tree, optimizeConstants);
-
-      return r2;
+      return RSquaredEvaluator.Evaluate(problemData, tree, optimizeConstants);
     }
 

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs

@@ -12 +12 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.DataAnalysis;
+using HeuristicLab.Problems.DataAnalysis.Symbolic;
+using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
 
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
@@ -36 +38 @@
     private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";
     private readonly string GrammarSymbolsParameterName = "Grammar Symbols";
+    private readonly string SearchCacheSizeParameterName = "Search Cache Size";
+    private readonly string SearchDataStructureSizeParameterName = "Search Data Structure Size";
+
+    // result names
+    public static readonly string BestTrainingModelResultName = "Best model (Training)";
+    public static readonly string BestTrainingSolutionResultName = "Best solution (Training)";
+    public static readonly string BestComplexityResultName = "Best solution complexity";
 
     public override bool SupportsPause { get { return true; } }
 
-    protected IValueParameter<DoubleValue> VariableImportanceWeightParameter {
-      get { return (IValueParameter<DoubleValue>)Parameters[VariableImportanceWeightName]; }
+    protected IFixedValueParameter<DoubleValue> VariableImportanceWeightParameter {
+      get { return (IFixedValueParameter<DoubleValue>)Parameters[VariableImportanceWeightName]; }
     }
 
@@ -47 +56 @@
     }
 
-    protected IValueParameter<BoolValue> OptimizeConstantsParameter {
-      get { return (IValueParameter<BoolValue>)Parameters[OptimizeConstantsParameterName]; }
+    protected IFixedValueParameter<BoolValue> OptimizeConstantsParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[OptimizeConstantsParameterName]; }
     }
 
@@ -56 +65 @@
     }
 
-    protected IValueParameter<IntValue> MaxComplexityParameter {
-      get { return (IValueParameter<IntValue>)Parameters[MaxComplexityParameterName]; }
-    }
+    protected IFixedValueParameter<IntValue> MaxComplexityParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[MaxComplexityParameterName]; }
+    }
+
     public int MaxComplexity {
       get { return MaxComplexityParameter.Value.Value; }
@@ -64 +74 @@
     }
 
-    protected IValueParameter<DoubleValue> ErrorWeightParameter {
-      get { return (IValueParameter<DoubleValue>)Parameters[ErrorWeightParameterName]; }
-    }
+    protected IFixedValueParameter<DoubleValue> ErrorWeightParameter {
+      get { return (IFixedValueParameter<DoubleValue>)Parameters[ErrorWeightParameterName]; }
+    }
+
     public double ErrorWeight {
       get { return ErrorWeightParameter.Value.Value; }
@@ -72 +83 @@
     }
 
-    protected IValueParameter<IntValue> GuiUpdateIntervalParameter {
-      get { return (IValueParameter<IntValue>)Parameters[GuiUpdateIntervalParameterName]; }
-    }
+    protected IFixedValueParameter<IntValue> GuiUpdateIntervalParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[GuiUpdateIntervalParameterName]; }
+    }
+
     public int GuiUpdateInterval {
       get { return GuiUpdateIntervalParameter.Value.Value; }
@@ -80 +92 @@
     }
 
-    protected IValueParameter<EnumValue<StorageType>> SearchDataStructureParameter {
-      get { return (IValueParameter<EnumValue<StorageType>>)Parameters[SearchDataStructureParameterName]; }
-    }
+    protected IFixedValueParameter<EnumValue<StorageType>> SearchDataStructureParameter {
+      get { return (IFixedValueParameter<EnumValue<StorageType>>)Parameters[SearchDataStructureParameterName]; }
+    }
+
+    public IFixedValueParameter<IntValue> SearchDataStructureSizeParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[SearchDataStructureSizeParameterName]; }
+    }
+
+    public int SearchDataStructureSize {
+      get { return SearchDataStructureSizeParameter.Value.Value; }
+    }
+
+    public IFixedValueParameter<IntValue> SearchCacheSizeParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[SearchCacheSizeParameterName]; }
+    }
+
+    public int SearchCacheSize {
+      get { return SearchCacheSizeParameter.Value.Value; }
+    }
+
     public StorageType SearchDataStructure {
       get { return SearchDataStructureParameter.Value.Value; }
@@ -116 +145 @@
     internal SearchDataStore OpenPhrases { get; private set; }           // Stack/Queue/etc. for fetching the next node in the search tree.  
 
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      variableImportance = CalculateVariableImportances();
+    }
+
     #region execution stats
+    [Storable]
     public int AllGeneratedSentencesCount { get; private set; }
 
+    [Storable]
     public int OverwrittenSentencesCount { get; private set; } // It is not guaranteed that shorter solutions are found first. 
                                                                // When longer solutions are overwritten with shorter ones, 
                                                                // this counter is increased.
+    [Storable]
     public int PhraseExpansionCount { get; private set; }      // Number, how many times a nonterminal symbol is replaced with a production rule.
     #endregion
@@ -133 +170 @@
 
     public GrammarEnumerationAlgorithm() {
-      Parameters.Add(new ValueParameter<DoubleValue>(VariableImportanceWeightName, "Variable Weight.", new DoubleValue(1.0)));
-      Parameters.Add(new ValueParameter<BoolValue>(OptimizeConstantsParameterName, "Run constant optimization in sentence evaluation.", new BoolValue(false)));
-      Parameters.Add(new ValueParameter<DoubleValue>(ErrorWeightParameterName, "Defines, how much weight is put on a phrase's r² value when priorizing phrases during search.", new DoubleValue(0.8)));
-      Parameters.Add(new ValueParameter<IntValue>(MaxComplexityParameterName, "The maximum number of variable symbols in a sentence.", new IntValue(12)));
-      Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(5000)));
-      Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.PriorityQueue)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>(VariableImportanceWeightName, "Variable Weight.", new DoubleValue(1.0)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(OptimizeConstantsParameterName, "Run constant optimization in sentence evaluation.", new BoolValue(false)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>(ErrorWeightParameterName, "Defines, how much weight is put on a phrase's r² value when priorizing phrases during search.", new DoubleValue(0.8)));
+      Parameters.Add(new FixedValueParameter<IntValue>(MaxComplexityParameterName, "The maximum number of variable symbols in a sentence.", new IntValue(12)));
+      Parameters.Add(new FixedValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(5000)));
+      Parameters.Add(new FixedValueParameter<IntValue>(SearchCacheSizeParameterName, "The size of the search node cache.", new IntValue((int)1e5)));
+      Parameters.Add(new FixedValueParameter<IntValue>(SearchDataStructureSizeParameterName, "The size of the search data structure.", new IntValue((int)1e5)));
+      Parameters.Add(new FixedValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.PriorityQueue)));
+
+      SearchDataStructureParameter.Value.ValueChanged += (o, e) => Prepare();
+      SearchDataStructureSizeParameter.Value.ValueChanged += (o, e) => Prepare();
+      SearchCacheSizeParameter.Value.ValueChanged += (o, e) => Prepare();
 
       var availableAnalyzers = new IGrammarEnumerationAnalyzer[] {
@@ -145 +188 @@
         new RSquaredEvaluator()
       };
+
       Parameters.Add(new FixedValueParameter<ReadOnlyCheckedItemCollection<IGrammarEnumerationAnalyzer>>(
         AnalyzersParameterName,
@@ -170 +214 @@
       // set a default problem
       Problem = new RegressionProblem() {
-        ProblemData = new HeuristicLab.Problems.Instances.DataAnalysis.PolyTen(seed: 1234).GenerateRegressionData()
+        ProblemData = new Problems.Instances.DataAnalysis.PolyTen(seed: 1234).GenerateRegressionData()
       };
     }
@@ -182 +226 @@
       ArchivedPhrases = new HashSet<int>(original.ArchivedPhrases);
       OpenPhrases = cloner.Clone(original.OpenPhrases);
+      Grammar = cloner.Clone(original.Grammar);
 
       AllGeneratedSentencesCount = original.AllGeneratedSentencesCount;
       OverwrittenSentencesCount = original.OverwrittenSentencesCount;
       PhraseExpansionCount = original.PhraseExpansionCount;
-      Grammar = cloner.Clone(original.Grammar);
 
       if (original.variableImportance != null)
@@ -204 +248 @@
       Analyzers.OfType<RSquaredEvaluator>().First().OptimizeConstants = OptimizeConstants;
       Grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray(), GrammarSymbols.CheckedItems.Select(v => v.Value));
-      OpenPhrases = new SearchDataStore(SearchDataStructure); // Select search strategy
+      OpenPhrases = new SearchDataStore(SearchDataStructure, SearchDataStructureSize, SearchCacheSize); // Select search strategy
 
       base.Prepare(); // this actually clears the results which will get reinitialized on Run()
@@ -237 +281 @@
         var phrase0 = new SymbolString(new[] { Grammar.StartSymbol });
         var phrase0Hash = Grammar.Hasher.CalcHashCode(phrase0);
+
         OpenPhrases.Store(new SearchNode(phrase0Hash, 0.0, 0.0, phrase0));
       }
@@ -249 +294 @@
 
         SearchNode fetchedSearchNode = OpenPhrases.GetNext();
+
+        if (fetchedSearchNode == null)
+          continue;
+
         SymbolString currPhrase = fetchedSearchNode.SymbolString;
 
@@ -380 +429 @@
     protected override void OnStopped() {
       previousExecutionState = this.ExecutionState;
+
+      if (BestTrainingSentence == null) {
+        base.OnStopped();
+        return;
+      }
+
+      var tree = Grammar.ParseSymbolicExpressionTree(BestTrainingSentence);
+      var model = new SymbolicRegressionModel(Problem.ProblemData.TargetVariable, tree, new SymbolicDataAnalysisExpressionTreeLinearInterpreter());
+      model.Scale(Problem.ProblemData);
+      var bestTrainingSolution = new SymbolicRegressionSolution(model, Problem.ProblemData);
+      Results.AddOrUpdateResult(BestTrainingModelResultName, model);
+      Results.AddOrUpdateResult(BestTrainingSolutionResultName, bestTrainingSolution);
+      Results.AddOrUpdateResult(BestComplexityResultName, new IntValue(Grammar.GetComplexity(BestTrainingSentence)));
       base.OnStopped();
     }
@@ -409 +471 @@
         ((IntValue)Results[DistinctSentencesName].Value).Value = DistinctSentencesComplexity.Count;
         ((IntValue)Results[PhraseExpansionsName].Value).Value = PhraseExpansionCount;
-        ((DoubleValue)Results[AverageSentenceComplexityName].Value).Value = DistinctSentencesComplexity.Select(pair => pair.Value).Average();
+        ((DoubleValue)Results[AverageSentenceComplexityName].Value).Value = DistinctSentencesComplexity.Count > 0
+          ? DistinctSentencesComplexity.Select(pair => pair.Value).Average()
+          : 0;
         ((IntValue)Results[OverwrittenSentencesName].Value).Value = OverwrittenSentencesCount;
         ((IntValue)Results[ExpansionsPerSecondName].Value).Value = (int)((PhraseExpansionCount /

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs

@@ -11 +11 @@
     [Storable]
     public readonly int Hash;
+
     [Storable]
     public readonly SymbolString SymbolString;
+
     [Storable]
     public readonly double Priority;
+
     [Storable]
     public readonly double R2;
@@ -43 +46 @@
 
   public enum StorageType {
-    PriorityQueue, Stack, Queue, RandomList
+    PriorityQueue, Stack, Queue, RandomList, SortedSet
   }
 
@@ -49 +52 @@
   class SearchDataStore : DeepCloneable, IEnumerable<SearchNode> {
     [Storable]
-    private Dictionary<int, SearchNode> storedValues; // Store hash-references and associated, actual values 
+    private LruCache<int, SearchNode> storedValues;
+    //private Dictionary<int, SearchNode> storedValues; // Store hash-references and associated, actual values 
+
     [Storable]
     private StorageType storageType;
 
-    // private storage
     [Storable]
     private Queue<int> queue;
@@ -62 +66 @@
     [Storable]
     private List<int> list;
+
+    [Storable]
+    private SortedSet<Tuple<double, int>> sortedSet;
+
+    [Storable]
+    private int searchDataStructureSize; // storage size for search nodes 
+
+    [Storable]
+    private int cacheSize; // cache for already explored search nodes 
 
     [ExcludeFromObjectGraphTraversal]
@@ -74 +87 @@
     protected SearchDataStore(bool deserializing) : this() { }
 
-    public SearchDataStore(StorageType storageType) {
+    public SearchDataStore(StorageType storageType, int searchDataStructureSize = (int)1e5, int cacheSize = (int)1e5) {
       this.storageType = storageType;
-      storedValues = new Dictionary<int, SearchNode>();
+
+      this.searchDataStructureSize = searchDataStructureSize;
+      this.cacheSize = cacheSize;
+
+      storedValues = new LruCache<int, SearchNode>(this.cacheSize);
       InitStorage();
     }
@@ -94 +111 @@
           InitRandomList();
           break;
+        case StorageType.SortedSet:
+          InitSortedSet();
+          break;
       }
     }
@@ -102 +122 @@
 
     protected SearchDataStore(SearchDataStore original, Cloner cloner) : base(original, cloner) {
-      storedValues = original.storedValues.ToDictionary(x => x.Key, x => cloner.Clone(x.Value));
+      storedValues = cloner.Clone(original.storedValues);
       storageType = original.storageType;
+      cacheSize = original.cacheSize;
+      searchDataStructureSize = original.searchDataStructureSize;
+
       InitStorage();
       switch (storageType) {
@@ -122 +145 @@
         case StorageType.RandomList:
           list.AddRange(original.list);
+          break;
+        case StorageType.SortedSet:
+          sortedSet = new SortedSet<Tuple<double, int>>(original.sortedSet);
           break;
       }
@@ -153 +179 @@
           };
           break;
+        case StorageType.SortedSet:
+          storeInternal = (hash, prio) => {
+            if (sortedSet.Count >= searchDataStructureSize) {
+              var max = sortedSet.Max;
+              sortedSet.Remove(max);
+              storedValues.Remove(max.Item2);
+            }
+            sortedSet.Add(Tuple.Create(prio, hash));
+          };
+          fetchInternal = () => {
+            var elem = sortedSet.FirstOrDefault();
+            if (elem == null)
+              return 0;
+            sortedSet.Remove(elem);
+            return elem.Item2;
+          };
+          break;
       }
     }
@@ -158 +201 @@
 
     private void InitPriorityQueue() {
-      int capacity = 10000000;
+      int capacity = searchDataStructureSize;
       priorityQueue = new PriorityQueue<double, int>(double.MaxValue, double.MinValue, capacity);
-      storeInternal = (hash, prio) => priorityQueue.Insert(prio, hash);
+      storeInternal = (hash, prio) => {
+        // size is the 0-based index of the last used element
+        if (priorityQueue.Size == capacity - 1) {
+          // if the queue is at capacity we have to replace 
+          return;
+        }
+        priorityQueue.Insert(prio, hash);
+      };
       fetchInternal = () => {
         int ret = priorityQueue.PeekMinValue();
-        priorityQueue.RemoveMin();
+        if (priorityQueue.Size > 0) {
+          priorityQueue.RemoveMin();
+        }
         return ret;
       };
@@ -195 +247 @@
     }
 
+    private void InitSortedSet() {
+      sortedSet = new SortedSet<Tuple<double, int>>();
+      storeInternal = (hash, prio) => {
+        if (sortedSet.Count >= searchDataStructureSize) {
+          var max = sortedSet.Max;
+          sortedSet.Remove(max);
+          storedValues.Remove(max.Item2);
+        }
+        sortedSet.Add(Tuple.Create(prio, hash));
+      };
+      fetchInternal = () => {
+        var elem = sortedSet.FirstOrDefault();
+        if (elem == null)
+          return default(int);
+        sortedSet.Remove(elem);
+        return elem.Item2;
+      };
+    }
+
     #endregion
 
@@ -201 +272 @@
     public SearchNode GetNext() {
       int hash = fetchInternal.Invoke();
-      SearchNode result = storedValues[hash];
-      storedValues.Remove(hash);
+      SearchNode result = null;
+      if (storedValues.TryGetValue(hash, out result)) {
+        storedValues.Remove(hash);
+      }
       return result;
     }
@@ -212 +285 @@
 
     public bool Contains(int hash) {
-      return storedValues.ContainsKey(hash);
+      SearchNode result;
+      return storedValues.TryGetValue(hash, out result);
     }
 
@@ -220 +294 @@
 
     public int Count {
-      get { return storedValues.Count; }
+      get {
+        switch (storageType) {
+          case StorageType.PriorityQueue:
+            return priorityQueue.Size;
+          case StorageType.Queue:
+            return queue.Count;
+          case StorageType.RandomList:
+            return list.Count;
+          case StorageType.Stack:
+            return stack.Count;
+          case StorageType.SortedSet:
+            return sortedSet.Count;
+          default:
+            throw new InvalidOperationException("");
+        }
+      }
     }
 
     public IEnumerator<SearchNode> GetEnumerator() {
-      return storedValues.Values.GetEnumerator();
+      return storedValues.Select(x => x.Value).GetEnumerator();
     }
 

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Sentence.cs

@@ -29 +29 @@
 
     protected SymbolString(SymbolString original, Cloner cloner) : base(original, cloner) {
-      symbols = original.symbols.ToArray();
+      symbols = original.symbols.Select(cloner.Clone).ToArray();
     }
 

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs

@@ -10 +10 @@
     private readonly int stringRepresentationHash;
 
-    [Storable(AllowOneWay = true)]
-    public string StringRepresentation { get; }
+    [Storable]
+    public string StringRepresentation { get; private set; }
 
     protected Symbol(string representation) {

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj

@@ -122 +122 @@
     <Compile Include="GrammarEnumeration\Grammar.cs" />
     <Compile Include="GrammarEnumeration\GrammarEnumerationAlgorithm.cs" />
+    <Compile Include="GrammarEnumeration\LruCache.cs" />
     <Compile Include="Hashing\Hasher.cs" />
     <Compile Include="GrammarEnumeration\SearchDataStructure.cs" />

branches/2886_SymRegGrammarEnumeration/Test/Test.csproj

@@ -34 +34 @@
     <ErrorReport>prompt</ErrorReport>
     <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <PropertyGroup>
+    <SignAssembly>true</SignAssembly>
+  </PropertyGroup>
+  <PropertyGroup>
+    <AssemblyOriginatorKeyFile>HeuristicLab.snk</AssemblyOriginatorKeyFile>
   </PropertyGroup>
   <ItemGroup>
@@ -120 +126 @@
     </ProjectReference>
   </ItemGroup>
+  <ItemGroup>
+    <None Include="HeuristicLab.snk" />
+  </ItemGroup>
   <Choose>
     <When Condition="'$(VisualStudioVersion)' == '10.0' And '$(IsCodedUITest)' == 'True'">