데이터 구조

Question

가능한 중복 :
Is it there any LRU implementation of IDictionary?

내가 사전 비슷하지만 키의 설정 번호를 포함 할 수있는 데이터 구조를 찾고 있어요 값 쌍. 키 값 쌍이 이미 가득 차있는 사전에 추가되면 최근에 액세스되지 않은 키 값 쌍이 제거됩니다.

C#의 경우 이와 비슷한 항목이 이미 있습니까?

운영체제 클래스에 이와 같은 것을 구현 한 것을 기억하고 데이터 구조를 사용하여 RAM의 어느 부분을 디스크로 페이징해야하는지 결정했습니다. 이는 쌍을 액세스 할 때 참으로 설정된 각 키 값 쌍과 참조 비트를 연관시킴으로써 수행되었습니다. 쌍을 제거해야 할 때 키 값 쌍은 참조 비트가 거짓으로 설정된 상태에서 키 값 쌍이 발견 될 때까지 반복됩니다. 반복되는 각 쌍의 참조 비트는 거짓으로 설정되고 마지막 쌍은 제거됩니다.

이 데이터 구조가 C#에 아직없는 경우에는 설명 된 알고리즘을 구현하는 것이 좋을까요? 아직 여기에 닷넷 프레임 워크에서이 아닌 모든 구현이있는 것처럼

Answer 1

내가

using System.Collections.Generic; 
using System.Linq; 

namespace MyProject.Util 
{ 
public class LruCache<Key, Value> 
{ 
    public delegate Value ValueCreator(); 

    Dictionary<Key, ValueWithReference> cache; 

    //The maximum number of elements that can fit in the cache. 
    int maxCacheSize; 

    IEnumerator<Value> valueRemover; 

    public LruCache(int maxCacheSize) { 
     this.cache = new Dictionary<Key, ValueWithReference>(); 
     this.maxCacheSize = maxCacheSize; 
     this.valueRemover = GetKeyValuePairRemover().GetEnumerator(); 
    } 

    /// <summary> 
    /// Gets the value associated with the specified key. If it doesn't exist in the cache 
    /// then it will be created with createValue() and added to the cache. 
    /// </summary> 
    public Value GetAndAddValue(Key key, ValueCreator createValue) { 
     if (this.cache.ContainsKey(key) == false) 
     { 
      while (this.cache.Count >= this.maxCacheSize) { 
       this.valueRemover.MoveNext(); 
      } 

      this.cache[key] = new ValueWithReference(createValue()); 
     } 

     this.cache[key].recentlyUsed = true; 
     return this.cache[key].value; 

    } 

    protected IEnumerable<Value> GetKeyValuePairRemover() { 
     while (true) { 
      List<Key> keyList = this.cache.Keys.ToList(); 

      foreach(Key key in keyList) { 
       if (this.cache[key].recentlyUsed) 
       { 
        this.cache[key].recentlyUsed = false; 
       } 
       else { 
        Value removedValue = this.cache[key].value; 
        this.cache.Remove(key); 
        yield return removedValue; 
       } 
      } 

     } 
    } 

    protected class ValueWithReference 
    { 
     public Value value; 
     public bool recentlyUsed; 

     public ValueWithReference(Value value) 
     { 
      this.value = value; 
      this.recentlyUsed = true; 
     } 
    } 
} 
} 

를 사용하여 결국 무엇인가 본다