Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
05/09/11 16:49:26 (13 years ago)
Author:
epitzer
Message:

Add maximum capacity parameter and a least recently used replacement strategy to the evaluation cache (#1516)

Location:
trunk/sources/HeuristicLab.Problems.ExternalEvaluation/3.3
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Problems.ExternalEvaluation/3.3/CachedExternalEvaluator.cs

    r6140 r6169  
    4343      set { CacheParameter.Value = value; }
    4444    }
    45     public DoubleValue Quality {
     45    protected DoubleValue Quality {
    4646      get { return QualityParameter.ActualValue; }
    4747      set { QualityParameter.ActualValue = value; }
    4848    }
    49     public IEvaluationServiceClient Client {
     49    protected IEvaluationServiceClient Client {
    5050      get { return ClientParameter.ActualValue; }
    5151    }
  • trunk/sources/HeuristicLab.Problems.ExternalEvaluation/3.3/EvaluationCache.cs

    r6140 r6169  
    1717 * You should have received a copy of the GNU General Public License
    1818 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 *
     20 * The LRU cache is based on an idea by Robert Rossney see
     21 * <http://csharp-lru-cache.googlecode.com>.
    1922 */
    2023#endregion
    21 
    2224
    2325using System;
     
    2729using HeuristicLab.Common.Resources;
    2830using HeuristicLab.Core;
     31using HeuristicLab.Data;
     32using HeuristicLab.Parameters;
    2933using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3034namespace HeuristicLab.Problems.ExternalEvaluation {
     
    3236  [Item("EvaluationCache", "Cache for external evaluation values")]
    3337  [StorableClass]
    34   public class EvaluationCache : NamedItem {
     38  public class EvaluationCache : ParameterizedNamedItem {
     39
     40    #region Types
     41    private class CacheEntry {
     42
     43      public string Key { get; private set; }
     44      public double Value { get; set; }
     45
     46      public CacheEntry(string key, double value) {
     47        Key = key;
     48        Value = value;
     49      }
     50
     51      public CacheEntry(string key) : this(key, 0) { }
     52
     53      public override bool Equals(object obj) {
     54        CacheEntry other = obj as CacheEntry;
     55        if (other == null)
     56          return false;
     57        return Key.Equals(other.Key);
     58      }
     59
     60      public override int GetHashCode() {
     61        return Key.GetHashCode();
     62      }
     63
     64      public override string ToString() {
     65        return string.Format("{{{0} : {1}}}", Key, Value);
     66      }
     67    }
    3568
    3669    public delegate double Evaluator(SolutionMessage message);
    37 
     70    #endregion
     71
     72    #region Fields
     73    private LinkedList<CacheEntry> list;
     74    private Dictionary<CacheEntry, LinkedListNode<CacheEntry>> index;
     75    #endregion
     76
     77    #region Properties
    3878    public override System.Drawing.Image ItemImage {
    3979      get { return VSImageLibrary.Database; }
    4080    }
    41 
    42     #region Fields & Properties
     81    public int Size {
     82      get { return index.Count; }
     83    }
    4384    [Storable]
    44     private Dictionary<string, double> cache;
    45 
    46     [Storable]
    47     private int cacheHits;
    48 
    49     public int CacheSize { get { return cache.Count; } }
    50 
    51     public int CacheHits { get { return cacheHits; } }
    52     #endregion
    53 
    54     #region Events
    55     public event EventHandler CacheSizeChanged;
    56     public event EventHandler CacheHitsChanged;
    57 
    58     protected virtual void OnCacheSizeChanged() {
    59       EventHandler handler = CacheSizeChanged;
     85    public int Hits { get; private set; }
     86    #endregion
     87
     88    #region events
     89    public event EventHandler SizeChanged;
     90    public event EventHandler HitsChanged;
     91
     92    protected virtual void OnSizeChanged() {
     93      EventHandler handler = SizeChanged;
    6094      if (handler != null)
    6195        handler(this, EventArgs.Empty);
    6296    }
    63 
    64     protected virtual void OnCacheHitsChanged() {
    65       EventHandler handler = CacheHitsChanged;
     97    protected virtual void OnHitsChanged() {
     98      EventHandler handler = HitsChanged;
    6699      if (handler != null)
    67100        handler(this, EventArgs.Empty);
     
    69102    #endregion
    70103
    71 
     104    #region Parameters
     105    public FixedValueParameter<IntValue> CapacityParameter {
     106      get { return (FixedValueParameter<IntValue>)Parameters["Capacity"]; }
     107    }
     108    #endregion
     109
     110    #region Parameter Values
     111    public int Capacity {
     112      get { return CapacityParameter.Value.Value; }
     113      set { CapacityParameter.Value.Value = value; }
     114    }
     115    #endregion
     116
     117    #region Persistence
     118    [Storable(Name="Cache")]
     119    private IEnumerable<KeyValuePair<string, double>> Cache_Persistence {
     120      get {
     121        return index.ToDictionary(kvp => kvp.Key.Key, kvp => kvp.Key.Value);
     122      }
     123      set {
     124        list = new LinkedList<CacheEntry>();
     125        index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
     126        foreach (var kvp in value) {
     127          var entry = new CacheEntry(kvp.Key);
     128          entry.Value = kvp.Value;
     129          index[entry] = list.AddLast(entry);
     130        }
     131      }
     132    }
     133    [StorableHook(HookType.AfterDeserialization)]
     134    private void AfterDeserialization() {
     135      RegisterEvents();
     136    }
     137    #endregion
    72138
    73139    #region Construction & Cloning
     
    76142    protected EvaluationCache(EvaluationCache original, Cloner cloner)
    77143      : base(original, cloner) {
    78       cache = original.cache.ToDictionary(kvp => kvp.Key, kvp => kvp.Value);
     144      Cache_Persistence = original.Cache_Persistence;
     145      RegisterEvents();
    79146    }
    80147    public EvaluationCache() {
    81       cache = new Dictionary<string, double>();
     148      list = new LinkedList<CacheEntry>();
     149      index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
     150      Parameters.Add(new FixedValueParameter<IntValue>("Capacity", "Maximum number of cache entries.", new IntValue(10000)));
     151      RegisterEvents();
    82152    }
    83153    public override IDeepCloneable Clone(Cloner cloner) {
     
    86156    #endregion
    87157
     158    #region Event Handling
     159    private void RegisterEvents() {
     160      CapacityParameter.Value.ValueChanged += new EventHandler(Value_ValueChanged);
     161    }
     162
     163    void Value_ValueChanged(object sender, EventArgs e) {
     164      if (Capacity < 0)
     165        throw new ArgumentOutOfRangeException("Cache capacity cannot be less than zero");
     166      Trim();
     167    }
     168    #endregion
     169
     170    #region Methods
     171    public void Reset() {
     172      list = new LinkedList<CacheEntry>();
     173      index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
     174      Hits = 0;
     175      OnSizeChanged();
     176      OnHitsChanged();
     177    }
     178
    88179    public double GetValue(SolutionMessage message, Evaluator evaluate) {
    89       string s = message.ToString();
    90       double value;
    91       if (cache.TryGetValue(s, out value)) {
    92         cacheHits++;
    93         OnCacheHitsChanged();
     180      CacheEntry entry = new CacheEntry(message.ToString());
     181      LinkedListNode<CacheEntry> node;
     182      if (index.TryGetValue(entry, out node)) {
     183        list.Remove(node);
     184        list.AddLast(node);
     185        Hits++;
     186        OnHitsChanged();
     187        return node.Value.Value;
    94188      } else {
    95         value = evaluate(message);
    96         cache[s] = value;
    97         OnCacheSizeChanged();
    98       }
    99       return value;
    100     }
    101 
    102     public void Reset() {
    103       cache = new Dictionary<string, double>();
    104       OnCacheSizeChanged();
    105       cacheHits = 0;
    106       OnCacheHitsChanged();
    107     }
     189        entry.Value = evaluate(message);
     190        index[entry] = list.AddLast(entry);
     191        Trim();
     192        return entry.Value;
     193      }
     194    }
     195
     196    private void Trim() {
     197      while (list.Count > Capacity) {
     198        LinkedListNode<CacheEntry> item = list.First;
     199        list.Remove(item);
     200        index.Remove(item.Value);
     201      }
     202      OnSizeChanged();
     203    }
     204    #endregion
     205
    108206  }
    109207}
Note: See TracChangeset for help on using the changeset viewer.