3

C# または Java で容量制限のある汎用 MruList をどのように実装しますか?

最近使用したキャッシュまたはリスト (= MruList) を表すクラスが必要です。これは一般的であり、インスタンス化時に指定された容量 (カウント) に制限されている必要があります。インターフェイスを次のようにしたいと思います。

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
}

各 Store() は、アイテムをリストの一番上 (先頭?) に配置する必要があります。GetList() は、最新のstoreで並べ替えられた順序付きリスト内のすべてのアイテムを返す必要があります。Store() を 20 回呼び出し、リストの長さが 10 項目である場合、最近保存された 10 項目のみを保持したいと考えています。GetList と StoreRange は、アプリの起動時とシャットダウン時に MruList の取得と保存をサポートすることを目的としています。

これは、GUI アプリをサポートするためのものです。保存されたアイテムのタイムスタンプも知りたいと思うかもしれません。多分。わからない。

内部的には、それをどのように実装しますか?またその理由は?

（いいえ、これはコースの割り当てではありません）

4

7 に答える 7

3

これは、アクセスされた時点でオブジェクトを格納する Cache クラスです。最近のアイテムがリストの最後にバブルします。キャッシュは、オブジェクト キーを取得するインデクサー プロパティを操作します。内部ディクショナリをリストに簡単に置き換えて、インデクサーからリストを参照できます。

ところで、クラスの名前もMRUに変更する必要があります:)

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();
            }
        }
    }
于 2009-05-11T19:14:33.740 に答える
3

あなたのアプローチに関するいくつかのコメント

  • Store が T を返すのはなぜですか? 追加したものはわかっています。明示的にメソッドチェーンが必要でない限り、戻す必要はありません。
  • GetNext() を新しいクラスにリファクタリングします。これは、異なる機能のセット (ストレージとカーソル トラバーサル) を表し、別のインターフェイスで表す必要があります。また、同じスタックでアクティブな 2 つの異なるメソッドが構造をトラバースしたい場合に何が起こるかというユーザビリティの問題もあります。
  • GetList() はおそらく を返すはずIEnumerable<T>です。戻るList<T>と、明示的なコピーが前もって強制されるか、基になる実装へのポインターが返されます。どちらも素晴らしい選択ではありません。

インターフェイスをバックアップするのに最適な構造は何ですか。実装するのに最適なように思われるのは、一方の端に追加し、もう一方の端から削除するのに効率的なデータ構造を持つことです。双方向リンク リストはこれに適しています。

于 2009-05-11T19:02:57.147 に答える
1

誰もが独自のコンテナー クラスを展開することを楽しんでいます。

しかし、.NET BCL には という小さな宝石がありますSortedList<T>。これを使用して、MRU リストまたはその他の優先キュー タイプ リストを実装できます。効率的な追加のために効率的なツリー構造を使用します。

MSDN の SortedListから:

SortedList オブジェクトの要素は、SortedList の作成時に指定された特定の IComparer 実装に従って、またはキー自体によって提供される IComparable 実装に従って、キーによって並べ替えられます。いずれの場合も、SortedList は重複キーを許可しません。

索引順序はソート順序に基づいています。要素が追加されると、正しい並べ替え順序で SortedList に挿入され、それに応じてインデックスが調整されます。要素が削除されると、それに応じてインデックスも調整されます。したがって、特定のキーと値のペアのインデックスは、SortedList オブジェクトに対して要素が追加または削除されると、変更される可能性があります。

SortedList オブジェクトの操作は、ソートのために Hashtable オブジェクトの操作よりも遅くなる傾向があります。ただし、SortedList は、関連付けられたキーまたはインデックスを介して値にアクセスできるようにすることで、より柔軟性を提供します。

このコレクションの要素には、整数インデックスを使用してアクセスできます。このコレクションのインデックスはゼロ ベースです。

于 2009-05-11T21:34:34.403 に答える
0

Java 6 では、Double-ended Queue の Deque... という名前の新しい Collection タイプが追加されました。

特に、制限された容量を指定できるものがあります: 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);
        }
    }

}
于 2009-05-11T21:25:41.547 に答える
0

Java では、LinkedHashMapこのようなことのために構築された を使用します。

public class MRUList<E> implements Iterable<E> {
    private final LinkedHashMap<E, Void> backing;

    public MRUList() {
        this(10);
    }

    public MRUList(final int maxSize) {
        this.backing = new LinkedHashMap<E,Void>(maxSize, maxSize, true){
           private final int MAX_SIZE = maxSize;
           @Override
           protected boolean removeEldestEntry(Map.Entry<E,Void> eldest){
               return size() > MAX_SIZE;
           }
        };
    }

    public void store(E item) {
        backing.put(item, null);
    }

    public void clear() {
        backing.clear();
    }

    public void storeRange(E[] range) {
        for (E e : range) {
            backing.put(e, null);
        }
    }

    public List<E> getList() {
        return new ArrayList<E>(backing.keySet());
    }

    public Iterator<E> iterator() {
        return backing.keySet().iterator();
    }
}

ただし、これはまったく逆の順序で繰り返されます (つまり、LRU が最初、MRU が最後)。MRU ファーストにするには、基本的に再実装する必要がありますLinkedHashMapが、バッキング リストの末尾ではなく先頭に新しい要素を挿入する必要があります。

于 2009-05-11T20:23:37.653 に答える