Changeset 15974 for branches/2886_SymRegGrammarEnumeration
- Timestamp:
- 06/28/18 11:35:13 (6 years ago)
- Location:
- branches/2886_SymRegGrammarEnumeration
- Files:
-
- 2 added
- 9 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/2886_SymRegGrammarEnumeration/ExpressionClustering/ExpressionClustering.csproj
r15929 r15974 15 15 </PropertyGroup> 16 16 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' "> 17 <PlatformTarget> x64</PlatformTarget>17 <PlatformTarget>AnyCPU</PlatformTarget> 18 18 <DebugSymbols>true</DebugSymbols> 19 19 <DebugType>full</DebugType> -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/RSquaredEvaluator.cs
r15949 r15974 16 16 public class RSquaredEvaluator : Item, IGrammarEnumerationAnalyzer { 17 17 public static readonly string BestTrainingQualityResultName = "Best R² (Training)"; 18 public static readonly string BestTestQualityResultName = "Best R² (Test)"; 18 19 public static readonly string BestTrainingModelResultName = "Best model (Training)"; 19 20 public static readonly string BestTrainingSolutionResultName = "Best solution (Training)"; 21 public static readonly string BestComplexityResultName = "Best solution complexity"; 20 22 21 23 private static readonly ISymbolicDataAnalysisExpressionTreeInterpreter expressionTreeLinearInterpreter = new SymbolicDataAnalysisExpressionTreeLinearInterpreter(); … … 42 44 algorithm.Started -= OnStarted; 43 45 algorithm.Stopped -= OnStopped; 44 45 46 algorithm.DistinctSentenceGenerated -= AlgorithmOnDistinctSentenceGenerated; 46 47 } … … 57 58 } 58 59 59 private void OnStopped(object sender, EventArgs eventArgs) { 60 GrammarEnumerationAlgorithm algorithm = (GrammarEnumerationAlgorithm)sender; 61 if (algorithm.Results.ContainsKey(BestTrainingModelResultName)) { 62 SymbolicRegressionModel model = (SymbolicRegressionModel)algorithm.Results[BestTrainingModelResultName].Value; 63 IRegressionSolution bestTrainingSolution = new RegressionSolution(model, algorithm.Problem.ProblemData); 60 private void OnStopped(object sender, EventArgs eventArgs) { } 64 61 65 algorithm.Results.AddOrUpdateResult(BestTrainingSolutionResultName, bestTrainingSolution); 66 } 62 private T GetValue<T>(IItem value) where T : struct { 63 var v = value as ValueTypeValue<T>; 64 if (v == null) 65 throw new ArgumentException(string.Format("Item is not of type {0}", typeof(ValueTypeValue<T>))); 66 return v.Value; 67 67 } 68 68 69 69 private void EvaluateSentence(GrammarEnumerationAlgorithm algorithm, SymbolString symbolString) { 70 var results = algorithm.Results; 71 var grammar = algorithm.Grammar; 70 72 var problemData = algorithm.Problem.ProblemData; 71 73 … … 74 76 75 77 double r2 = Evaluate(problemData, tree, OptimizeConstants); 78 double bestR2 = results.ContainsKey(BestTrainingQualityResultName) ? GetValue<double>(results[BestTrainingQualityResultName].Value) : 0.0; 79 if (r2 < bestR2) 80 return; 76 81 77 double bestR2 = 0.0; 78 if (algorithm.Results.ContainsKey(BestTrainingQualityResultName)) 79 bestR2 = ((DoubleValue)algorithm.Results[BestTrainingQualityResultName].Value).Value; 80 bool better = r2 > bestR2; 81 bool equallyGood = r2.IsAlmost(bestR2); 82 bool shorter = false; 82 var bestComplexity = int.MaxValue; 83 if (results.ContainsKey(BestComplexityResultName)) { 84 bestComplexity = GetValue<int>(results[BestComplexityResultName].Value); 85 } else if (algorithm.BestTrainingSentence != null) { 86 bestComplexity = grammar.GetComplexity(algorithm.BestTrainingSentence); 87 results.AddOrUpdateResult(BestComplexityResultName, new IntValue(bestComplexity)); 88 } 89 var complexity = grammar.GetComplexity(symbolString); 83 90 84 if (!better && equallyGood) { 85 shorter = algorithm.BestTrainingSentence != null && 86 algorithm.Grammar.GetComplexity(algorithm.BestTrainingSentence) > algorithm.Grammar.GetComplexity(symbolString); 87 } 88 if (better || (equallyGood && shorter)) { 89 algorithm.Results.AddOrUpdateResult(BestTrainingQualityResultName, new DoubleValue(r2)); 90 91 SymbolicRegressionModel model = new SymbolicRegressionModel( 92 problemData.TargetVariable, 93 tree, 94 expressionTreeLinearInterpreter); 95 96 algorithm.Results.AddOrUpdateResult(BestTrainingModelResultName, model); 97 91 if (r2 > bestR2 || (r2.IsAlmost(bestR2) && complexity < bestComplexity)) { 92 results.AddOrUpdateResult(BestTrainingQualityResultName, new DoubleValue(r2)); 93 results.AddOrUpdateResult(BestComplexityResultName, new IntValue(complexity)); 98 94 algorithm.BestTrainingSentence = symbolString; 99 95 } … … 121 117 } 122 118 } 123 124 r2 = double.IsNaN(r2) ? 0.0 : r2;125 126 119 } else { 127 var target = problemData.TargetVariableTrainingValues; 128 129 SymbolicRegressionModel model = new SymbolicRegressionModel( 130 problemData.TargetVariable, 120 r2 = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(expressionTreeLinearInterpreter, 131 121 tree, 132 expressionTreeLinearInterpreter); 133 134 var estVals = model.GetEstimatedValues(problemData.Dataset, problemData.TrainingIndices); 135 OnlineCalculatorError error; 136 r2 = OnlinePearsonsRCalculator.Calculate(target, estVals, out error); 137 if (error != OnlineCalculatorError.None) r2 = 0.0; 122 double.MinValue, 123 double.MaxValue, 124 problemData, 125 problemData.TrainingIndices, 126 applyLinearScaling: true); 138 127 } 139 140 return r2; 128 return double.IsNaN(r2) ? 0.0 : r2; 141 129 } 142 130 } -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs
r15960 r15974 22 22 [StorableClass(StorableClassType.AllFieldsAndAllProperties)] 23 23 public class Grammar : DeepCloneable { 24 25 public Symbol StartSymbol { get; } 24 public Symbol StartSymbol { get; private set; } 26 25 27 26 public Hasher<int> Hasher { get; } … … 29 28 #region Symbols 30 29 31 public IReadOnlyDictionary<Symbol, IReadOnlyList<Production>> Productions { get; }30 public IReadOnlyDictionary<Symbol, IReadOnlyList<Production>> Productions { get; private set; } 32 31 33 32 public NonterminalSymbol Var; … … 79 78 80 79 protected Grammar(Grammar original, Cloner cloner) : base(original, cloner) { 81 VarTerminals = original.VarTerminals.Select(cloner.Clone).ToArray(); 82 StartSymbol = cloner.Clone(original.StartSymbol); 83 Hasher = cloner.Clone(original.Hasher); // how to handle circular reference grammar <-> hasher? (the cloner *should* handle it) 80 infixExpressionFormatter = cloner.Clone(original.infixExpressionFormatter); 81 84 82 Productions = original.Productions.ToDictionary(x => cloner.Clone(x.Key), x => (IReadOnlyList<Production>)x.Value.Select(cloner.Clone).ToList()); 83 VarTerminals = original.VarTerminals.Select(cloner.Clone).ToList(); 84 85 85 Var = cloner.Clone(original.Var); 86 VarTerminals = original.VarTerminals.Select(cloner.Clone).ToList();87 86 Expr = cloner.Clone(original.Expr); 88 87 Term = cloner.Clone(original.Term); … … 95 94 InvExpr = cloner.Clone(original.InvExpr); 96 95 InvTerm = cloner.Clone(original.InvTerm); 96 97 97 Addition = cloner.Clone(original.Addition); 98 98 Multiplication = cloner.Clone(original.Multiplication); … … 100 100 Exp = cloner.Clone(original.Exp); 101 101 Sin = cloner.Clone(original.Sin); 102 Sin = cloner.Clone(original.Sin);103 102 Inv = cloner.Clone(original.Inv); 104 103 Const = cloner.Clone(original.Const); 105 104 106 107 constSy = cloner.Clone(original.constSy); 108 varSy = cloner.Clone(original.varSy); 109 addSy = cloner.Clone(original.addSy); 110 mulSy = cloner.Clone(original.mulSy); 111 logSy = cloner.Clone(original.logSy); 112 expSy = cloner.Clone(original.expSy); 113 divSy = cloner.Clone(original.divSy); 114 sinSy = cloner.Clone(original.sinSy); 115 116 rootSy = cloner.Clone(original.rootSy); 117 startSy = cloner.Clone(original.startSy); 118 119 infixExpressionFormatter = cloner.Clone(original.infixExpressionFormatter); 120 } 121 122 public Grammar(string[] variables, IEnumerable<GrammarRule> includedRules) { 105 StartSymbol = Expr; 106 Hasher = cloner.Clone(original.Hasher); 107 108 InitTreeParser(); // easier this way (and less typing) 109 } 110 111 private void InitProductions(string[] variables, IEnumerable<GrammarRule> includedRules) { 123 112 #region Define Symbols 124 113 Var = new NonterminalSymbol("Var"); … … 210 199 Productions = productions; 211 200 #endregion 212 201 } 202 203 private void InitTreeParser() { 213 204 #region Parsing to SymbolicExpressionTree 214 205 var symbolicExpressionGrammar = new TypeCoherentExpressionGrammar(); … … 229 220 infixExpressionFormatter = new InfixExpressionFormatter(); 230 221 #endregion 222 } 223 224 public Grammar(string[] variables, IEnumerable<GrammarRule> includedRules) { 225 InitProductions(variables, includedRules); 226 InitTreeParser(); 231 227 232 228 Hasher = new IntHasher(this); … … 244 240 public double EvaluatePhrase(SymbolString s, IRegressionProblemData problemData, bool optimizeConstants) { 245 241 SymbolicExpressionTree tree = ParseSymbolicExpressionTree(s); 246 247 double r2 = RSquaredEvaluator.Evaluate(problemData, tree, optimizeConstants); 248 249 return r2; 242 return RSquaredEvaluator.Evaluate(problemData, tree, optimizeConstants); 250 243 } 251 244 -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs
r15960 r15974 12 12 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 13 13 using HeuristicLab.Problems.DataAnalysis; 14 using HeuristicLab.Problems.DataAnalysis.Symbolic; 15 using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression; 14 16 15 17 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration { … … 36 38 private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval"; 37 39 private readonly string GrammarSymbolsParameterName = "Grammar Symbols"; 40 private readonly string SearchCacheSizeParameterName = "Search Cache Size"; 41 private readonly string SearchDataStructureSizeParameterName = "Search Data Structure Size"; 42 43 // result names 44 public static readonly string BestTrainingModelResultName = "Best model (Training)"; 45 public static readonly string BestTrainingSolutionResultName = "Best solution (Training)"; 46 public static readonly string BestComplexityResultName = "Best solution complexity"; 38 47 39 48 public override bool SupportsPause { get { return true; } } 40 49 41 protected I ValueParameter<DoubleValue> VariableImportanceWeightParameter {42 get { return (I ValueParameter<DoubleValue>)Parameters[VariableImportanceWeightName]; }50 protected IFixedValueParameter<DoubleValue> VariableImportanceWeightParameter { 51 get { return (IFixedValueParameter<DoubleValue>)Parameters[VariableImportanceWeightName]; } 43 52 } 44 53 … … 47 56 } 48 57 49 protected I ValueParameter<BoolValue> OptimizeConstantsParameter {50 get { return (I ValueParameter<BoolValue>)Parameters[OptimizeConstantsParameterName]; }58 protected IFixedValueParameter<BoolValue> OptimizeConstantsParameter { 59 get { return (IFixedValueParameter<BoolValue>)Parameters[OptimizeConstantsParameterName]; } 51 60 } 52 61 … … 56 65 } 57 66 58 protected IValueParameter<IntValue> MaxComplexityParameter { 59 get { return (IValueParameter<IntValue>)Parameters[MaxComplexityParameterName]; } 60 } 67 protected IFixedValueParameter<IntValue> MaxComplexityParameter { 68 get { return (IFixedValueParameter<IntValue>)Parameters[MaxComplexityParameterName]; } 69 } 70 61 71 public int MaxComplexity { 62 72 get { return MaxComplexityParameter.Value.Value; } … … 64 74 } 65 75 66 protected IValueParameter<DoubleValue> ErrorWeightParameter { 67 get { return (IValueParameter<DoubleValue>)Parameters[ErrorWeightParameterName]; } 68 } 76 protected IFixedValueParameter<DoubleValue> ErrorWeightParameter { 77 get { return (IFixedValueParameter<DoubleValue>)Parameters[ErrorWeightParameterName]; } 78 } 79 69 80 public double ErrorWeight { 70 81 get { return ErrorWeightParameter.Value.Value; } … … 72 83 } 73 84 74 protected IValueParameter<IntValue> GuiUpdateIntervalParameter { 75 get { return (IValueParameter<IntValue>)Parameters[GuiUpdateIntervalParameterName]; } 76 } 85 protected IFixedValueParameter<IntValue> GuiUpdateIntervalParameter { 86 get { return (IFixedValueParameter<IntValue>)Parameters[GuiUpdateIntervalParameterName]; } 87 } 88 77 89 public int GuiUpdateInterval { 78 90 get { return GuiUpdateIntervalParameter.Value.Value; } … … 80 92 } 81 93 82 protected IValueParameter<EnumValue<StorageType>> SearchDataStructureParameter { 83 get { return (IValueParameter<EnumValue<StorageType>>)Parameters[SearchDataStructureParameterName]; } 84 } 94 protected IFixedValueParameter<EnumValue<StorageType>> SearchDataStructureParameter { 95 get { return (IFixedValueParameter<EnumValue<StorageType>>)Parameters[SearchDataStructureParameterName]; } 96 } 97 98 public IFixedValueParameter<IntValue> SearchDataStructureSizeParameter { 99 get { return (IFixedValueParameter<IntValue>)Parameters[SearchDataStructureSizeParameterName]; } 100 } 101 102 public int SearchDataStructureSize { 103 get { return SearchDataStructureSizeParameter.Value.Value; } 104 } 105 106 public IFixedValueParameter<IntValue> SearchCacheSizeParameter { 107 get { return (IFixedValueParameter<IntValue>)Parameters[SearchCacheSizeParameterName]; } 108 } 109 110 public int SearchCacheSize { 111 get { return SearchCacheSizeParameter.Value.Value; } 112 } 113 85 114 public StorageType SearchDataStructure { 86 115 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. 117 146 147 [StorableHook(HookType.AfterDeserialization)] 148 private void AfterDeserialization() { 149 variableImportance = CalculateVariableImportances(); 150 } 151 118 152 #region execution stats 153 [Storable] 119 154 public int AllGeneratedSentencesCount { get; private set; } 120 155 156 [Storable] 121 157 public int OverwrittenSentencesCount { get; private set; } // It is not guaranteed that shorter solutions are found first. 122 158 // When longer solutions are overwritten with shorter ones, 123 159 // this counter is increased. 160 [Storable] 124 161 public int PhraseExpansionCount { get; private set; } // Number, how many times a nonterminal symbol is replaced with a production rule. 125 162 #endregion … … 133 170 134 171 public GrammarEnumerationAlgorithm() { 135 Parameters.Add(new ValueParameter<DoubleValue>(VariableImportanceWeightName, "Variable Weight.", new DoubleValue(1.0))); 136 Parameters.Add(new ValueParameter<BoolValue>(OptimizeConstantsParameterName, "Run constant optimization in sentence evaluation.", new BoolValue(false))); 137 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))); 138 Parameters.Add(new ValueParameter<IntValue>(MaxComplexityParameterName, "The maximum number of variable symbols in a sentence.", new IntValue(12))); 139 Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(5000))); 140 Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.PriorityQueue))); 172 Parameters.Add(new FixedValueParameter<DoubleValue>(VariableImportanceWeightName, "Variable Weight.", new DoubleValue(1.0))); 173 Parameters.Add(new FixedValueParameter<BoolValue>(OptimizeConstantsParameterName, "Run constant optimization in sentence evaluation.", new BoolValue(false))); 174 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))); 175 Parameters.Add(new FixedValueParameter<IntValue>(MaxComplexityParameterName, "The maximum number of variable symbols in a sentence.", new IntValue(12))); 176 Parameters.Add(new FixedValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(5000))); 177 Parameters.Add(new FixedValueParameter<IntValue>(SearchCacheSizeParameterName, "The size of the search node cache.", new IntValue((int)1e5))); 178 Parameters.Add(new FixedValueParameter<IntValue>(SearchDataStructureSizeParameterName, "The size of the search data structure.", new IntValue((int)1e5))); 179 Parameters.Add(new FixedValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.PriorityQueue))); 180 181 SearchDataStructureParameter.Value.ValueChanged += (o, e) => Prepare(); 182 SearchDataStructureSizeParameter.Value.ValueChanged += (o, e) => Prepare(); 183 SearchCacheSizeParameter.Value.ValueChanged += (o, e) => Prepare(); 141 184 142 185 var availableAnalyzers = new IGrammarEnumerationAnalyzer[] { … … 145 188 new RSquaredEvaluator() 146 189 }; 190 147 191 Parameters.Add(new FixedValueParameter<ReadOnlyCheckedItemCollection<IGrammarEnumerationAnalyzer>>( 148 192 AnalyzersParameterName, … … 170 214 // set a default problem 171 215 Problem = new RegressionProblem() { 172 ProblemData = new HeuristicLab.Problems.Instances.DataAnalysis.PolyTen(seed: 1234).GenerateRegressionData()216 ProblemData = new Problems.Instances.DataAnalysis.PolyTen(seed: 1234).GenerateRegressionData() 173 217 }; 174 218 } … … 182 226 ArchivedPhrases = new HashSet<int>(original.ArchivedPhrases); 183 227 OpenPhrases = cloner.Clone(original.OpenPhrases); 228 Grammar = cloner.Clone(original.Grammar); 184 229 185 230 AllGeneratedSentencesCount = original.AllGeneratedSentencesCount; 186 231 OverwrittenSentencesCount = original.OverwrittenSentencesCount; 187 232 PhraseExpansionCount = original.PhraseExpansionCount; 188 Grammar = cloner.Clone(original.Grammar);189 233 190 234 if (original.variableImportance != null) … … 204 248 Analyzers.OfType<RSquaredEvaluator>().First().OptimizeConstants = OptimizeConstants; 205 249 Grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray(), GrammarSymbols.CheckedItems.Select(v => v.Value)); 206 OpenPhrases = new SearchDataStore(SearchDataStructure ); // Select search strategy250 OpenPhrases = new SearchDataStore(SearchDataStructure, SearchDataStructureSize, SearchCacheSize); // Select search strategy 207 251 208 252 base.Prepare(); // this actually clears the results which will get reinitialized on Run() … … 237 281 var phrase0 = new SymbolString(new[] { Grammar.StartSymbol }); 238 282 var phrase0Hash = Grammar.Hasher.CalcHashCode(phrase0); 283 239 284 OpenPhrases.Store(new SearchNode(phrase0Hash, 0.0, 0.0, phrase0)); 240 285 } … … 249 294 250 295 SearchNode fetchedSearchNode = OpenPhrases.GetNext(); 296 297 if (fetchedSearchNode == null) 298 continue; 299 251 300 SymbolString currPhrase = fetchedSearchNode.SymbolString; 252 301 … … 380 429 protected override void OnStopped() { 381 430 previousExecutionState = this.ExecutionState; 431 432 if (BestTrainingSentence == null) { 433 base.OnStopped(); 434 return; 435 } 436 437 var tree = Grammar.ParseSymbolicExpressionTree(BestTrainingSentence); 438 var model = new SymbolicRegressionModel(Problem.ProblemData.TargetVariable, tree, new SymbolicDataAnalysisExpressionTreeLinearInterpreter()); 439 model.Scale(Problem.ProblemData); 440 var bestTrainingSolution = new SymbolicRegressionSolution(model, Problem.ProblemData); 441 Results.AddOrUpdateResult(BestTrainingModelResultName, model); 442 Results.AddOrUpdateResult(BestTrainingSolutionResultName, bestTrainingSolution); 443 Results.AddOrUpdateResult(BestComplexityResultName, new IntValue(Grammar.GetComplexity(BestTrainingSentence))); 382 444 base.OnStopped(); 383 445 } … … 409 471 ((IntValue)Results[DistinctSentencesName].Value).Value = DistinctSentencesComplexity.Count; 410 472 ((IntValue)Results[PhraseExpansionsName].Value).Value = PhraseExpansionCount; 411 ((DoubleValue)Results[AverageSentenceComplexityName].Value).Value = DistinctSentencesComplexity.Select(pair => pair.Value).Average(); 473 ((DoubleValue)Results[AverageSentenceComplexityName].Value).Value = DistinctSentencesComplexity.Count > 0 474 ? DistinctSentencesComplexity.Select(pair => pair.Value).Average() 475 : 0; 412 476 ((IntValue)Results[OverwrittenSentencesName].Value).Value = OverwrittenSentencesCount; 413 477 ((IntValue)Results[ExpansionsPerSecondName].Value).Value = (int)((PhraseExpansionCount / -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs
r15960 r15974 11 11 [Storable] 12 12 public readonly int Hash; 13 13 14 [Storable] 14 15 public readonly SymbolString SymbolString; 16 15 17 [Storable] 16 18 public readonly double Priority; 19 17 20 [Storable] 18 21 public readonly double R2; … … 43 46 44 47 public enum StorageType { 45 PriorityQueue, Stack, Queue, RandomList 48 PriorityQueue, Stack, Queue, RandomList, SortedSet 46 49 } 47 50 … … 49 52 class SearchDataStore : DeepCloneable, IEnumerable<SearchNode> { 50 53 [Storable] 51 private Dictionary<int, SearchNode> storedValues; // Store hash-references and associated, actual values 54 private LruCache<int, SearchNode> storedValues; 55 //private Dictionary<int, SearchNode> storedValues; // Store hash-references and associated, actual values 56 52 57 [Storable] 53 58 private StorageType storageType; 54 59 55 // private storage56 60 [Storable] 57 61 private Queue<int> queue; … … 62 66 [Storable] 63 67 private List<int> list; 68 69 [Storable] 70 private SortedSet<Tuple<double, int>> sortedSet; 71 72 [Storable] 73 private int searchDataStructureSize; // storage size for search nodes 74 75 [Storable] 76 private int cacheSize; // cache for already explored search nodes 64 77 65 78 [ExcludeFromObjectGraphTraversal] … … 74 87 protected SearchDataStore(bool deserializing) : this() { } 75 88 76 public SearchDataStore(StorageType storageType ) {89 public SearchDataStore(StorageType storageType, int searchDataStructureSize = (int)1e5, int cacheSize = (int)1e5) { 77 90 this.storageType = storageType; 78 storedValues = new Dictionary<int, SearchNode>(); 91 92 this.searchDataStructureSize = searchDataStructureSize; 93 this.cacheSize = cacheSize; 94 95 storedValues = new LruCache<int, SearchNode>(this.cacheSize); 79 96 InitStorage(); 80 97 } … … 94 111 InitRandomList(); 95 112 break; 113 case StorageType.SortedSet: 114 InitSortedSet(); 115 break; 96 116 } 97 117 } … … 102 122 103 123 protected SearchDataStore(SearchDataStore original, Cloner cloner) : base(original, cloner) { 104 storedValues = original.storedValues.ToDictionary(x => x.Key, x => cloner.Clone(x.Value));124 storedValues = cloner.Clone(original.storedValues); 105 125 storageType = original.storageType; 126 cacheSize = original.cacheSize; 127 searchDataStructureSize = original.searchDataStructureSize; 128 106 129 InitStorage(); 107 130 switch (storageType) { … … 122 145 case StorageType.RandomList: 123 146 list.AddRange(original.list); 147 break; 148 case StorageType.SortedSet: 149 sortedSet = new SortedSet<Tuple<double, int>>(original.sortedSet); 124 150 break; 125 151 } … … 153 179 }; 154 180 break; 181 case StorageType.SortedSet: 182 storeInternal = (hash, prio) => { 183 if (sortedSet.Count >= searchDataStructureSize) { 184 var max = sortedSet.Max; 185 sortedSet.Remove(max); 186 storedValues.Remove(max.Item2); 187 } 188 sortedSet.Add(Tuple.Create(prio, hash)); 189 }; 190 fetchInternal = () => { 191 var elem = sortedSet.FirstOrDefault(); 192 if (elem == null) 193 return 0; 194 sortedSet.Remove(elem); 195 return elem.Item2; 196 }; 197 break; 155 198 } 156 199 } … … 158 201 159 202 private void InitPriorityQueue() { 160 int capacity = 10000000;203 int capacity = searchDataStructureSize; 161 204 priorityQueue = new PriorityQueue<double, int>(double.MaxValue, double.MinValue, capacity); 162 storeInternal = (hash, prio) => priorityQueue.Insert(prio, hash); 205 storeInternal = (hash, prio) => { 206 // size is the 0-based index of the last used element 207 if (priorityQueue.Size == capacity - 1) { 208 // if the queue is at capacity we have to replace 209 return; 210 } 211 priorityQueue.Insert(prio, hash); 212 }; 163 213 fetchInternal = () => { 164 214 int ret = priorityQueue.PeekMinValue(); 165 priorityQueue.RemoveMin(); 215 if (priorityQueue.Size > 0) { 216 priorityQueue.RemoveMin(); 217 } 166 218 return ret; 167 219 }; … … 195 247 } 196 248 249 private void InitSortedSet() { 250 sortedSet = new SortedSet<Tuple<double, int>>(); 251 storeInternal = (hash, prio) => { 252 if (sortedSet.Count >= searchDataStructureSize) { 253 var max = sortedSet.Max; 254 sortedSet.Remove(max); 255 storedValues.Remove(max.Item2); 256 } 257 sortedSet.Add(Tuple.Create(prio, hash)); 258 }; 259 fetchInternal = () => { 260 var elem = sortedSet.FirstOrDefault(); 261 if (elem == null) 262 return default(int); 263 sortedSet.Remove(elem); 264 return elem.Item2; 265 }; 266 } 267 197 268 #endregion 198 269 … … 201 272 public SearchNode GetNext() { 202 273 int hash = fetchInternal.Invoke(); 203 SearchNode result = storedValues[hash]; 204 storedValues.Remove(hash); 274 SearchNode result = null; 275 if (storedValues.TryGetValue(hash, out result)) { 276 storedValues.Remove(hash); 277 } 205 278 return result; 206 279 } … … 212 285 213 286 public bool Contains(int hash) { 214 return storedValues.ContainsKey(hash); 287 SearchNode result; 288 return storedValues.TryGetValue(hash, out result); 215 289 } 216 290 … … 220 294 221 295 public int Count { 222 get { return storedValues.Count; } 296 get { 297 switch (storageType) { 298 case StorageType.PriorityQueue: 299 return priorityQueue.Size; 300 case StorageType.Queue: 301 return queue.Count; 302 case StorageType.RandomList: 303 return list.Count; 304 case StorageType.Stack: 305 return stack.Count; 306 case StorageType.SortedSet: 307 return sortedSet.Count; 308 default: 309 throw new InvalidOperationException(""); 310 } 311 } 223 312 } 224 313 225 314 public IEnumerator<SearchNode> GetEnumerator() { 226 return storedValues. Values.GetEnumerator();315 return storedValues.Select(x => x.Value).GetEnumerator(); 227 316 } 228 317 -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Sentence.cs
r15963 r15974 29 29 30 30 protected SymbolString(SymbolString original, Cloner cloner) : base(original, cloner) { 31 symbols = original.symbols. ToArray();31 symbols = original.symbols.Select(cloner.Clone).ToArray(); 32 32 } 33 33 -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs
r15963 r15974 10 10 private readonly int stringRepresentationHash; 11 11 12 [Storable (AllowOneWay = true)]13 public string StringRepresentation { get; }12 [Storable] 13 public string StringRepresentation { get; private set; } 14 14 15 15 protected Symbol(string representation) { -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj
r15960 r15974 122 122 <Compile Include="GrammarEnumeration\Grammar.cs" /> 123 123 <Compile Include="GrammarEnumeration\GrammarEnumerationAlgorithm.cs" /> 124 <Compile Include="GrammarEnumeration\LruCache.cs" /> 124 125 <Compile Include="Hashing\Hasher.cs" /> 125 126 <Compile Include="GrammarEnumeration\SearchDataStructure.cs" /> -
branches/2886_SymRegGrammarEnumeration/Test/Test.csproj
r15714 r15974 34 34 <ErrorReport>prompt</ErrorReport> 35 35 <WarningLevel>4</WarningLevel> 36 </PropertyGroup> 37 <PropertyGroup> 38 <SignAssembly>true</SignAssembly> 39 </PropertyGroup> 40 <PropertyGroup> 41 <AssemblyOriginatorKeyFile>HeuristicLab.snk</AssemblyOriginatorKeyFile> 36 42 </PropertyGroup> 37 43 <ItemGroup> … … 120 126 </ProjectReference> 121 127 </ItemGroup> 128 <ItemGroup> 129 <None Include="HeuristicLab.snk" /> 130 </ItemGroup> 122 131 <Choose> 123 132 <When Condition="'$(VisualStudioVersion)' == '10.0' And '$(IsCodedUITest)' == 'True'">
Note: See TracChangeset
for help on using the changeset viewer.