Changeset 14342


Ignore:
Timestamp:
10/19/16 15:11:28 (3 years ago)
Author:
mkommend
Message:

#2685: Refactored calculation of minimum expression length and depth into an separate class. Removed separate initialization code for the grammar caches in the ctor.

Location:
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/SymbolicExpressionGrammarBase.cs

    r14185 r14342  
    8282    protected SymbolicExpressionGrammarBase(bool deserializing)
    8383      : base(deserializing) {
    84       cachedMinExpressionLength = new Dictionary<string, int>();
    85       cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    86       cachedMinExpressionDepth = new Dictionary<string, int>();
    87       cachedMaxExpressionDepth = new Dictionary<string, int>();
    88 
    89       cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
    90       cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
    9184
    9285      symbols = new Dictionary<string, ISymbol>();
     
    10093    protected SymbolicExpressionGrammarBase(SymbolicExpressionGrammarBase original, Cloner cloner)
    10194      : base(original, cloner) {
    102       cachedMinExpressionLength = new Dictionary<string, int>();
    103       cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    104       cachedMinExpressionDepth = new Dictionary<string, int>();
    105       cachedMaxExpressionDepth = new Dictionary<string, int>();
    106 
    107       cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
    108       cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
    10995
    11096      symbols = original.symbols.ToDictionary(x => x.Key, y => cloner.Clone(y.Value));
     
    124110    protected SymbolicExpressionGrammarBase(string name, string description)
    125111      : base(name, description) {
    126       cachedMinExpressionLength = new Dictionary<string, int>();
    127       cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    128       cachedMinExpressionDepth = new Dictionary<string, int>();
    129       cachedMaxExpressionDepth = new Dictionary<string, int>();
    130 
    131       cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
    132       cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
    133 
    134112      symbols = new Dictionary<string, ISymbol>();
    135113      symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>();
     
    322300    }
    323301
    324     private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol;
     302    private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
    325303    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
    326304      if (allowedChildSymbols.Count == 0) return false;
     
    352330    }
    353331
    354     private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex;
     332    private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
    355333    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
    356334      if (!child.Enabled) return false;
     
    412390    }
    413391
    414     private readonly Dictionary<string, int> cachedMinExpressionLength;
     392    private readonly Dictionary<string, int> cachedMinExpressionLength = new Dictionary<string, int>();
    415393    public int GetMinimumExpressionLength(ISymbol symbol) {
    416394      int res;
     
    423401        if (cachedMinExpressionLength.TryGetValue(symbol.Name, out res)) return res;
    424402
    425         res = GetMinimumExpressionLengthRec(symbol);
    426         foreach (var entry in cachedMinExpressionLength.Where(e => e.Value >= int.MaxValue).ToList()) {
    427           if (entry.Key != symbol.Name) cachedMinExpressionLength.Remove(entry.Key);
    428         }
    429         return res;
    430       }
    431     }
    432 
    433     private int GetMinimumExpressionLengthRec(ISymbol symbol) {
    434       int temp;
    435       if (!cachedMinExpressionLength.TryGetValue(symbol.Name, out temp)) {
    436         cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
    437         long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
    438                                               let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
    439                                                                       where s.InitialFrequency > 0.0
    440                                                                       select GetMinimumExpressionLengthRec(s)).DefaultIfEmpty(0).Min()
    441                                               select minForSlot).DefaultIfEmpty(0).Sum();
    442 
    443         cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
     403        GrammarUtils.CalculateMinimumExpressionLengths(this, cachedMinExpressionLength);
    444404        return cachedMinExpressionLength[symbol.Name];
    445405      }
    446       return temp;
    447     }
    448 
    449     private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength;
     406    }
     407
     408
     409    private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    450410    public int GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
    451411      int temp;
     
    469429    }
    470430
    471     private readonly Dictionary<string, int> cachedMinExpressionDepth;
     431    private readonly Dictionary<string, int> cachedMinExpressionDepth = new Dictionary<string, int>();
    472432    public int GetMinimumExpressionDepth(ISymbol symbol) {
    473433      int res;
     
    480440        if (cachedMinExpressionDepth.TryGetValue(symbol.Name, out res)) return res;
    481441
    482         res = GetMinimumExpressionDepthRec(symbol);
    483         foreach (var entry in cachedMinExpressionDepth.Where(e => e.Value >= int.MaxValue).ToList()) {
    484           if (entry.Key != symbol.Name) cachedMinExpressionDepth.Remove(entry.Key);
    485         }
    486         return res;
    487       }
    488     }
    489     private int GetMinimumExpressionDepthRec(ISymbol symbol) {
    490       int temp;
    491       if (!cachedMinExpressionDepth.TryGetValue(symbol.Name, out temp)) {
    492         cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
    493         long minDepth = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
    494                              let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
    495                                                      where s.InitialFrequency > 0.0
    496                                                      select GetMinimumExpressionDepthRec(s)).DefaultIfEmpty(0).Min()
    497                              select minForSlot).DefaultIfEmpty(0).Max();
    498         cachedMinExpressionDepth[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
     442        GrammarUtils.CalculateMinimumExpressionDepth(this, cachedMinExpressionDepth);
    499443        return cachedMinExpressionDepth[symbol.Name];
    500444      }
    501       return temp;
    502     }
    503 
    504     private readonly Dictionary<string, int> cachedMaxExpressionDepth;
     445    }
     446
     447    private readonly Dictionary<string, int> cachedMaxExpressionDepth = new Dictionary<string, int>();
    505448    public int GetMaximumExpressionDepth(ISymbol symbol) {
    506449      int temp;
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj

    r12897 r14342  
    129129    <Compile Include="ArchitectureManipulators\SubroutineDuplicater.cs" />
    130130    <Compile Include="ArchitectureManipulators\SymbolicExpressionTreeArchitectureManipulator.cs" />
     131    <Compile Include="Grammars\GrammarUtils.cs" />
    131132    <Compile Include="SymbolicExpressionTreeProblem.cs" />
    132133    <Compile Include="Compiler\Instruction.cs" />
Note: See TracChangeset for help on using the changeset viewer.