Effiziente Modellierung einer MruList in C# oder Java

Question

Wie würden Sie eine kapazitätsbeschränkte, generische MruList in C# oder Java implementieren?

Ich möchte eine Klasse haben, die einen zuletzt verwendeten Cache oder Liste (= MruList) darstellt. Es sollte generisch sein und auf eine Kapazität (Anzahl) beschränkt sein, die bei der Instanziierung angegeben wird. Ich würde die Schnittstelle gerne so etwas wie sein: (vorne)

public interface IMruList<T> 
{ 
    public T Store(T item); 
    public void Clear(); 
    public void StoreRange(T[] range); 
    public List<T> GetList(); 
    public T GetNext(); // cursor-based retrieval 
} 

Jeden Speicher() soll das Element an der Spitze setzt auf der Liste. Die GetList() sollte alle Elemente in einer geordneten Liste zurückgeben, geordnet nach dem letzten Store. Wenn ich Store() 20 Mal anrufe und meine Liste 10 Artikel lang ist, möchte ich nur die 10 zuletzt gespeicherten Artikel behalten. Die GetList und StoreRange sollen das Abrufen/Speichern der MruList beim Starten und Beenden der App unterstützen.

Dies ist eine GUI-App zu unterstützen. Ich denke, ich möchte vielleicht auch den Zeitstempel eines gespeicherten Artikels wissen. Könnte sein. Nicht sicher.

Intern, wie würden Sie es implementieren, und warum?

(nein, das ist keine Kurszuordnung)

Answer 1

Paar Kommentare über Ihren Ansatz

• Warum Shop Rückkehr T haben? Ich weiß, was ich gerade hinzugefügt habe, die Rückgabe an mich ist nicht notwendig, es sei denn, Sie möchten explizit die Verkettung der Methode
• Refactator GetNext() in eine neue Klasse. Es stellt eine andere Funktionalität dar (Speicher vs. Cursor-Traversal) und sollte durch eine separate Schnittstelle dargestellt werden. Es hat auch Usability-Bedenken, was passiert, wenn zwei verschiedene Methoden, die auf demselben Stack aktiv sind, die Struktur durchqueren wollen?
• GetList() sollte wahrscheinlich IEnumerable<T> zurückgeben. Die Rückgabe List<T> erzwingt entweder eine explizite Frontkopie oder gibt einen Zeiger auf eine zugrunde liegende Implementierung zurück. Weder ist eine gute Wahl.

Wie für die beste Struktur, um die Schnittstelle zu unterstützen. Es scheint, als ob die beste Implementierung eine Datenstruktur ist, die effizient zu einem Ende hinzugefügt und von dem anderen entfernt wird. Eine doppelt verknüpfte Liste würde dem gut passen.

Answer 2

Ich hätte eine interne ArrayList und Store() löschen das letzte Element, wenn seine Größe die Kapazität im Konstruktor festgelegt übersteigt. Ich denke, die Standardterminologie nennt das merkwürdigerweise eine "LRU" -Liste, weil das am wenigsten zuletzt verwendete Element das ist, was verworfen wird. Siehe hierzu wikipedia's entry.

Answer 3

Sie können dies mit einer Collections.Generic.LinkedList<T> aufbauen. Wenn Sie ein Objekt in eine vollständige Liste schieben, löschen Sie das letzte und fügen Sie das neue Element an der Vorderseite ein. Die meisten Operationen sollten in O (1) sein, was besser ist als eine Array-basierte Implementierung.

Answer 4

Hier ist eine Cache-Klasse, die Objekte bis zum Zeitpunkt des Zugriffs speichert. Neuere Artikel blubbern bis zum Ende der Liste. Der Cache arbeitet mit einer Indexer-Eigenschaft, die einen Objektschlüssel akzeptiert. Sie könnten das interne Wörterbuch leicht durch eine Liste ersetzen und die Liste vom Indexer aus referenzieren.

BTW, sollten Sie die Klasse zu MRU umbenennen auch :)

class Cache 
    { 
     Dictionary<object, object> cache = new Dictionary<object, object>(); 

     /// <summary> 
     /// Keeps up with the most recently read items. 
     /// Items at the end of the list were read last. 
     /// Items at the front of the list have been the most idle. 
     /// Items at the front are removed if the cache capacity is reached. 
     /// </summary> 
     List<object> priority = new List<object>(); 
     public Type Type { get; set; } 
     public Cache(Type type) 
     { 
      this.Type = type; 

      //TODO: register this cache with the manager 

     } 
     public object this[object key] 
     { 
      get 
      { 
       lock (this) 
       { 
        if (!cache.ContainsKey(key)) return null; 
        //move the item to the end of the list      
        priority.Remove(key); 
        priority.Add(key); 
        return cache[key]; 
       } 
      } 
      set 
      { 
       lock (this) 
       { 
        if (Capacity > 0 && cache.Count == Capacity) 
        { 
         cache.Remove(priority[0]); 
         priority.RemoveAt(0); 
        } 
        cache[key] = value; 
        priority.Remove(key); 
        priority.Add(key); 

        if (priority.Count != cache.Count) 
         throw new Exception("Capacity mismatch."); 
       } 
      } 
     } 
     public int Count { get { return cache.Count; } } 
     public int Capacity { get; set; } 

     public void Clear() 
     { 
      lock (this) 
      { 
       priority.Clear(); 
       cache.Clear(); 
      } 
     } 
    } 

Answer 5

In Java würde ich die LinkedHashMap verwenden, die für diese Art der Sache gebaut.

Jedoch iteriert dies in genau umgekehrter Reihenfolge (d. H. LRU zuerst, MRU zuletzt). Wenn Sie MRU-first erstellen, müssen Sie zunächst neu implementieren, aber am Ende der Backing-Liste neue Elemente einfügen, anstatt am Ende.

Answer 6

Java 6 hat einen neuen Collection-Typ namens Deque ... für Double-ended Queue hinzugefügt.

Es gibt eine, die eine begrenzte Kapazität haben kann: LinkedBlockingDeque.

import java.util.ArrayList; 
import java.util.List; 
import java.util.concurrent.LinkedBlockingDeque; 

public class DequeMruList<T> implements IMruList<T> { 

    private LinkedBlockingDeque<T> store; 

    public DequeMruList(int capacity) { 
     store = new LinkedBlockingDeque<T>(capacity); 
    } 

    @Override 
    public void Clear() { 
     store.clear(); 
    } 

    @Override 
    public List<T> GetList() { 
     return new ArrayList<T>(store); 
    } 

    @Override 
    public T GetNext() { 
    // Get the item, but don't remove it 
     return store.peek(); 
    } 

    @Override 
    public T Store(T item) { 
     boolean stored = false; 
     // Keep looping until the item is added 
     while (!stored) { 
      // Add if there's room 
      if (store.offerFirst(item)) { 
       stored = true; 
      } else { 
       // No room, remove the last item 
       store.removeLast(); 
      } 
     } 
     return item; 
    } 

    @Override 
    public void StoreRange(T[] range) { 
     for (T item : range) { 
      Store(item); 
     } 
    } 

} 

Answer 7

Jeder genießt seine eigenen Container Klassen rollen.

Aber in der .NET BCL gibt es ein kleines Juwel namens SortedList<T>. Sie können dies verwenden, um Ihre MRU-Liste oder eine andere Liste von Prioritätswarteschlangentypen zu implementieren. Es verwendet eine effiziente Baumstruktur für effiziente Ergänzungen.

Von SortedList on MSDN:

Die Elemente eines SortedList Objekt werden durch die Schlüssel sortiert entweder gemäß einem spezifischen IComparer Implementierung spezifiziert, wenn der SortedList erstellt oder nach die IComparable Umsetzung bereitgestellt durch die Schlüssel selbst. In beiden Fällen, eine SortedList nicht ermöglichen doppelte Schlüssel.

Die Indexsequenz basiert auf der Sortierreihenfolge . Wenn ein Element hinzugefügt wird, wird es in SortedList in der richtigen Sortierreihenfolge eingefügt, und die Indexierung wird entsprechend angepasst. Wenn ein Element entfernt wird, wird die Indizierung auch entsprechend angepasst. Daher kann sich der Index eines bestimmten Schlüssel/Wert-Paares ändern, wenn Elemente hinzugefügt oder aus dem SortedList-Objekt entfernt werden.

Operationen auf einem SortedList-Objekt neigen langsamer als Operationen auf ein Hashtable Objekt wegen der Sortierung. Die SortedList bietet jedoch mehr Flexibilität, indem sie Zugriff auf die Werte entweder über die zugehörigen Schlüssel oder über die Indizes ermöglicht.

Elemente in dieser Auflistung können unter Verwendung eines ganzzahligen Index auf zugegriffen werden. Indizes in dieser Sammlung sind nullbasiert.