이 알고리즘 구현은 LRU 또는 MRU입니까?

Question

저는 C#을 사용하여 프로젝트에서 MRU (Most Recently Used) 캐시를 구현하려고합니다.

MRU와 그 반대로, LRU (Least Recently Used)에 대한 몇 가지 개념과 구현을 살펴보면서 C#에서 MRU 모음의 구현을 설명하는이 기사 http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=626을 발견했습니다.

나를 혼란스럽게 생각하는 이유는이 구현이 MRU보다는 LRU라고 생각하기 때문입니다. 이 컬렉션 클래스가 MRU인지 확인하는 데 도움을 줄 수 있습니까?

다음 코드 블록은 전체 MRUCollection 클래스입니다. 감사. 가장 최근에 (MRU) 사용

---

http://en.wikipedia.org/wiki/Cache_algorithms#Most_Recently_Used

class MruDictionary<TKey, TValue> 
{ 
    private LinkedList<MruItem> items; 
    private Dictionary<TKey, LinkedListNode<MruItem>> itemIndex; 
    private int maxCapacity; 
    public MruDictionary(int cap) 
    { 
     maxCapacity = cap; 
     items = new LinkedList<MruItem>(); 
     itemIndex = new Dictionary<TKey, LinkedListNode<MruItem>>(maxCapacity); 
    } 
    public void Add(TKey key, TValue value) 
    { 
     if (itemIndex.ContainsKey(key)) 
     { 
      throw new ArgumentException("An item with the same key already exists."); 
     } 
     if (itemIndex.Count == maxCapacity) 
     { 
      LinkedListNode<MruItem> node = items.Last; 
      items.RemoveLast(); //Why do we move the last than first here? The node accessed recently is moved to the front of list. 
      itemIndex.Remove(node.Value.Key); 
     } 
     LinkedListNode<MruItem> newNode = new LinkedListNode<MruItem>(new MruItem(key, value)); 
     items.AddFirst(newNode); 
     itemIndex.Add(key, newNode); 
    } 
    public bool TryGetValue(TKey key, out TValue value) 
    { 
     LinkedListNode<MruItem> node; 
     if (itemIndex.TryGetValue(key, out node)) 
     { 
      value = node.Value.Value; 
      items.Remove(node); 
      items.AddFirst(node); 
      return true; 
     } 
     value = default(TValue); 
     return false; 
    } 
} 

class MruItem 
{ 
    private TKey _key; 
    private TValue _value; 
    public MruItem(TKey k, TValue v) 
    { 
     _key = key; 
     _value = v; 
    } 
    public TKey Key 
    { 
     get { return _key; } 
    } 
    public TValue Value 
    { 
     get { return _value; } 
    } 
} 

: 폐기, LRU, 먼저 가장 최근에 사용 된 항목과는 대조적이다.

최근에 액세스 한 노드가 목록의 앞쪽으로 이동 했으므로 캐시가 꽉 찬 경우 목록의 첫 번째 노드를 제거해야합니다.

Answer 1

MRU 구현처럼 보입니다. 검색이 연결된 목록의 시작 부분에서 시작하여 뒤로 이동하는 방식에 주목하십시오. 노드가 액세스 될 때마다 목록의 맨 앞으로 이동합니다. Add()에서 AddFirst()를 사용하여 노드를 추가하고 TryGetValue()에서 노드를 제거하고 목록의 맨 앞에 추가합니다. 여기에 설명되어 있습니다 무엇을 기반으로

Answer 2

: http://en.wikipedia.org/wiki/Cache_algorithms#Most_Recently_Used

은 LRU이다. items을 "주문한"목록으로 생각하십시오.

가장 최근에 사용한 항목이 "전면"에 있습니다. 새 항목이 추가되면 items.AddFirst(newNode);이 호출되어 목록 앞에 추가됩니다.

items.Remove(node); 
items.AddFirst(node); 

목록이 가득, 그것을 사용하여 목록에서 "마지막"/ "오래된"항목을 밀어 : 항목이 '터치'하면 , 그들은 이러한 호출을 사용하여 목록의 전면으로 이동 items.RemoveLast();

캐시는 용량이 떨어질 때 "가장 오래 전에 사용하지 않은"항목을 먼저 제거합니다.