标签: lru

我试图使用LinkedHashMap实现LRU缓存.在LinkedHashMap(http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html)的文档中,它说:

请注意,如果将键重新插入地图,则插入顺序不会受到影响.

但是,当我做以下投入时

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int size;

    public static void main(String[] args) {
        LRUCache<Integer, Integer> cache = LRUCache.newInstance(2);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(1, 1);
        cache.put(3, 3);

        System.out.println(cache);
    }

    private LRUCache(int size) {
        super(size, 0.75f, true);
        this.size = size;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > size;
    }

    public static <K, V> LRUCache<K, V> newInstance(int size) {
        return new LRUCache<K, V>(size);
    }

}

输出是

{1=1, 3=3}

这表明重新插入确实影响了订单.有人知道任何解释吗？

Java有LinkedHashMap,它可以让你99%到LRU缓存.

是否存在LRU缓存的Javascript实现,最好是来自信誉良好的源,即:

1. 可理解
2. 高效(摊销O(1)获取/放置/删除)

？我一直在网上搜索但找不到一个; 我以为我在Ajax设计模式上找到了一个,但它掩盖了该sendToTail()方法并且具有O(n)性能(可能是因为队列和关联数组被分开).

我想我可以写自己的,但我已经学会了重新发明核心算法的轮子会对一个人的健康造成危害的困难:/

当在memcache中可用内存已满时,memcache使用LRU(最近最近使用的)算法来释放内存.我的问题是LRU算法是否会删除在过期的项目中使用了一段时间(最近一次使用)的条目？到期的条目不会在该确切时刻删除,而是在下次有人尝试访问时(AFAIR).那么LRU算法(也)会解释密钥的到期吗？

我正在尝试实现自己的LRU缓存.是的,我知道Java 为此目的提供了LinkedHashMap,但我试图使用基本数据结构来实现它.

通过阅读这个主题,我明白我需要一个HashMap来O(1)查找一个密钥和一个链表来管理"最近最少使用的"驱逐策略.我发现这些引用都使用标准库hashmap但实现了自己的链表:

• " LRU缓存和快速定位对象通常使用哪些数据结构？ "(stackoverflow.com)
• " 实施LRU缓存的最佳方法是什么？ "(quora.com)
• " 用C++实现LRU缓存 "(uml.edu)
• " LRU Cache(Java) "(programcreek.com)

哈希表应该直接存储链接列表节点,如下所示.我的缓存应该存储Integer键和String值.

但是,在Java中,LinkedList集合不公开其内部节点,因此我无法将它们存储在HashMap中.我可以将HashMap存储索引放入LinkedList中,但是到达一个项目需要O(N)时间.所以我试着存储一个ListIterator.

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.LinkedList;
import java.util.ListIterator;

public class LRUCache {

    private static final int DEFAULT_MAX_CAPACITY = 10;

    protected Map<Integer, ListIterator> _map = new HashMap<Integer, ListIterator>();
    protected LinkedList<String> _list = new LinkedList<String>();

    protected int _size = 0;
    protected int _maxCapacity = 0;

    public LRUCache(int maxCapacity) {
        _maxCapacity = maxCapacity;
    }

    // Put the key, value pair into …

新的Android类LruCache线程是否安全？java doc说:

这个类是线程安全的.通过在缓存上同步以原子方式执行多个缓存操作:

   synchronized (cache) {
     if (cache.get(key) == null) {
         cache.put(key, value);

   }}

他们是不是说不是线程安全的？如果类是线程安全的,为什么必须同步？

谢谢!

我正在考虑在Android应用中实现我的第一层缓存.我正在考虑使用SoftReferences来确保避免OOM异常,但由于有很多关于Android如何"太快"释放这些内容的文章,我决定研究android.util.LruCache缓存.

问题:如何为实际设备正确调整大小？一切听起来很不错LRU缓存是真正的解决方案而不是SoftReferences,但是如果你真的很想避免使用OOM异常,那么使用任意数量的数百万个硬引用都会感到非常不安全.如果你问我,这只是不安全.无论如何,这似乎是唯一的选择.我正在研究getMemoryClass以找出实际设备上应用程序的堆大小(+在调整缓存大小之前检查可用堆大小).基线是16 Megs听起来不错,但是我看过设备(例如旧时的G1)抛出OOM异常只有大约5兆字节的堆大小(根据Eclipse MAT).我知道G1很老了,但重点是我的经验与文档提到的16 Megs基线并不完全一致.因此,我完全不确定如果我需要最合理的话,我应该如何扩展LRU缓存.(对于8 Megs会很满意,并且在低规格设备上可以小到1 Meg)

谢谢你的任何提示.

编辑:我指的是Android LRU缓存类:http://developer.android.com/reference/android/util/LruCache.html

我知道Guava有一个很棒的缓存库,但我正在寻找更多Scala /功能友好的东西,我可以做的事情cache.getOrElse(query, { /* expensive operation */}).我也查看了Scalaz的备忘录,但是没有lru到期.

这可能很简单,但我无法理解它.谁能给我一个顺序泛滥的例子？在我正在阅读的教科书和互联网资料中说明了这一点

当缓冲帧的数量小于文件中的页面时,这将导致读取文件的每个页面.这是由LRU和重复扫描引起的恶劣情况

#frames <文件中的#个页面.

使用LRU,每次扫描文件都会导致读取文件的每一页."

但究竟是什么呢？为什么会这样？

我正在寻找 Python 中的磁盘 LRU 缓存包。其中大部分都在内存缓存中。

主要原因是数据库访问速度慢并且内存 LRU 的 RAM 有限。然而，用于 LRU 缓存的大而快速的 SSD。

我正在尝试使用C++实现LRU Cache.我想知道实现它们的最佳设计是什么.我知道LRU应该提供find(),添加一个元素并删除一个元素.删除应删除LRU元素.实现此目的的最佳ADT是什么？例如:如果我使用带有元素的映射作为值和时间计数器作为键我可以在O(logn)时间内搜索,Inserting是O(n),删除是O(logn).