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() 20 次并且我的列表有 10 个项目长，我只想保留最近存储的 10 个项目。GetList 和 StoreRange 旨在支持在应用程序启动和关闭时检索/保存 MruList。

这是为了支持 GUI 应用程序。我想我可能还想知道存储项目的时间戳。也许。没有把握。

在内部，您将如何实施它，为什么？

（不，这不是课程作业）

4

7 回答 7

3

关于您的方法的一些评论

  • 为什么有商店退货 T？我知道我刚刚添加的内容，除非您明确需要方法链接，否则无需将其返回给我
  • 将 GetNext() 重构为一个新类。它代表一组不同的功能（存储与游标遍历），应由单独的接口表示。它还存在可用性问题，因为当在同一堆栈上活动的两个不同方法想要遍历结构时会发生什么？
  • GetList() 应该可能返回IEnumerable<T>. 返回List<T>要么强制显式复制，要么返回指向底层实现的指针。两者都不是一个很好的选择。

至于支持接口的最佳结构是什么。似乎最好的实现方法是拥有一种数据结构，该结构可以有效地添加到一端并从另一端移除。双向链表很适合这种情况。

于 2009-05-11T19:02:57.147 回答
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 回答
1

如果它的大小超过构造函数中建立的容量，我将有一个内部 ArrayList 并让 Store() 删除最后一个元素。我认为标准术语，奇怪的是，将其称为“LRU”列表，因为最近最少使用的项目会被丢弃。请参阅维基百科的条目。

于 2009-05-11T19:06:04.957 回答
1

您可以使用Collections.Generic.LinkedList<T>. 当您将一个项目推入完整列表时，删除最后一个并将新的插入到最前面。大多数操作应该在 O(1) 中，这比基于数组的实现要好。

于 2009-05-11T19:07:43.690 回答
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 中，我会使用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-first 基本上需要重新实现LinkedHashMap，但在后备列表的前面插入新元素，而不是在末尾。

于 2009-05-11T20:23:37.653 回答
0

Java 6 为双端队列添加了一个名为 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 回答