`

Lru Cache

 
阅读更多

 

题目:https://leetcode.com/problems/lru-cache/

大学课本在讲操作系统的时候提及LRU可基于双向链表以及map来实现: 其中双向链表用于调整优先级,根据LRU规则淘汰对象; map主要用于快速查询。

 

将题目分解:

  • get 操作涉及优先级调整
  • set 操作涉及优先级调整以及淘汰操作

将题目转化为实现head()以及evict()两个函数;

  • evict 淘汰队尾,有两种情况  1)队尾前面无节点,即:又是队首又是队尾 2)前面有节点
  • head 将操作的节点放到队首,如果已经位于队首则无需操作: 1)这个元素之前已经存在于队列中 2)这个元素是新的
解题代码:
package org.bull.leetcode.alg;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by bull on 16/5/5.
 * <p>
 * https://leetcode.com/problems/lru-cache/
 * get时涉及优先级调整
 * set时涉及优先级调整以及淘汰操作
 * 将问题化简为:实现 head以及evict函数
 * <p>
 * evict其实就是淘汰队尾:有两种情况 1)队尾前面无节点,即:又是队首又是队尾 2)前面有节点
 * head 就是将操作的节点放到队首,如果已经位于队首则无需操作: 1)这个元素之前已经存在于队列中 2)这个元素是新的
 */
public class LRUCache {
    private int capacity;
    /**
     * 用来保存队首,优先级调整基本针对队首
     */
    private Entry head;
    /**
     * 淘汰对象基本针对队尾
     */
    private Entry tail;

    private Map<Integer, Entry> container;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        container = new HashMap<>(capacity);
    }

    /**
     * 获取对象,并调整优先级
     *
     * @param key
     * @return
     */
    public int get(int key) {
        Entry entry = container.get(key);
        if (entry == null) {
            return -1;
        }
        head(entry, true);
        return entry.getValue();
    }

    /**
     * 设置对象,如果达到阈值,淘汰队尾对象
     *
     * @param key
     * @param value
     */
    public void set(int key, int value) {
        if (container.get(key) == null) {
            if (container.size() >= capacity) {
                evict();
            }
            Entry entry = new Entry();
            entry.setKey(key);
            entry.setValue(value);
            head(entry, false);
            container.put(key, entry);
        } else {
            Entry entry = container.get(key);
            entry.setValue(value);
            head(entry, true);
        }
    }

    /**
     * 淘汰队尾
     */
    public void evict() {
        Integer tailKey = tail.getKey();
        container.remove(tailKey);
        //调整队尾
        Entry before = tail.before;
        if (before == null) {
            head = null;
            tail = null;
        } else {
            before.next = null;
            tail.before = null;
            tail = before;
        }
    }

    /**
     * 将优先级置顶
     *
     * @param entry
     */
    public void head(Entry entry, boolean in) {
        if (in) {
            if (entry.before != null) {
                entry.before.next = entry.next;
                if (entry.next == null) {//队尾
                    tail = entry.before;
                } else {
                    entry.next.before = entry.before;
                }
                //调整队首
                entry.before = null;
                head.before = entry;
                entry.next = head;
                head = entry;
            }
        } else {
            if (container.size() > 0) {//已经有元素
                entry.next = head;
                head.before = entry;
                head = entry;
            } else { //特点是 head 和 tail 都不存在
                head = entry;
                tail = entry;
            }
        }
    }

    /**
     * 双向链表结构体
     */
    class Entry {
        private int key;
        private int value;
        private Entry next;
        private Entry before;

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Entry getNext() {
            return next;
        }

        public void setNext(Entry next) {
            this.next = next;
        }

        public Entry getBefore() {
            return before;
        }

        public void setBefore(Entry before) {
            this.before = before;
        }

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }
    }
}
  

总结来说,解题首先思路要对,然后要分解问题,分解问题是要全面考虑,然后有耐心一步步的去实现即可。

 

分享到:
评论

相关推荐

    最近最少使用cache,提取leveldb的lru cache部分,增加过期时间,过期失效

    它使用LRU Cache作为其内部的数据缓冲机制,以加速对数据的读取。在原始的LevelDB实现中,LRU Cache主要关注数据的访问频率,而不涉及数据的过期策略。 在这个项目中,开发者将LevelDB的LRU Cache部分提取出来,...

    算法面试通关40讲完整课件 57-58 LRU Cache

    特别是对于希望在科技公司取得职位的求职者来说,掌握关键的数据结构和算法变得尤为重要,其中LRU Cache(最近最少使用缓存)是面试中经常出现的考点之一。 LRU Cache是一种被广泛使用的缓存管理策略,它主要应用于...

    Python中双向链表的实现及LRU Cache应用详解(包含详细的完整的程序和数据)

    本文将详细介绍双向链表这一数据结构的核心概念、结构特点以及在Python语言中的实现方法,并通过最少最近使用缓存(LRU Cache)的实际案例来阐述双向链表的应用价值。 首先,双向链表是一种比单向链表更为灵活的...

    erlang lru cache module

    Erlang LRU Cache 模块是一个用于实现Least Recently Used(最近最少使用)缓存策略的工具。LRU缓存是一种常见的数据结构,它在内存有限的情况下,通过淘汰最近最少使用的数据来保持缓存的容量。在Erlang中,这个...

    LRU Cache的简单C++实现

     LRU Cache是一个Cache的置换算法,含义是“近少使用”,把满足“近少使用”的数据从Cache中剔除出去,并且保证Cache中第一个数据是近刚刚访问的,因为这样的数据更有可能被接下来的程序所访问。  LRU的应用比较...

    Android性能优化一 : 1.The Magic of LRU Cache (100 Days of Google Dev)

    谷歌官方视频

    完全兼容STL的LRU cache类

    就一个h头文件,使用非常方便! 因项目需要,需要使用LRUCache,...get用来从LRU中查找,查到返回true,否则返回false, replace用来更新(新增)LRU队列中的某数据至最新。 本类提供正向iterator,100%与STL算法兼容。

    python-leetcode题解之146-LRU-Cache

    Python中的leetcode题解之146-LRU-Cache是一个编程问题,主要考察编程者对LRU缓存机制的理解及其在Python中的实现技巧。 在进行LRU Cache的题解中,我们需要考虑到以下知识点和概念: 1. **缓存淘汰策略**:LRU ...

    LRU-update-Cache-.zip_LRU cache

    LRU置换算法是选择最近最久未使用的页面予以置换。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来经历的时间T,当须淘汰一个页面时,选择现有页面中T值最大的,即最近最久没有访问的页面。这是...

    Lru Cache java代码

    LruCache的java代码实现,是从android代码中抽取出来的

    lru-cache-2.5.0.zip

    LRU Cache(Least Recently Used 缓存)是一种常见的数据结构,用于存储有限数量的数据,并在内存容量达到上限时,优先淘汰最近最少使用的数据。在IT领域,LRU Cache被广泛应用于缓存系统,如数据库查询缓存、操作...

    js-leetcode题解之146-lru-cache.js

    在JavaScript中实现LRU Cache通常涉及到创建一个双向链表来维护数据项的使用顺序,以及一个哈希表来通过键值快速访问链表中的节点。 在JavaScript中,可以通过构造函数实现一个简单的LRU Cache。首先,创建一个双向...

    LRU Cache-开源

    LRU Cache,全称为Least Recently Used Cache,是一种常见的缓存淘汰策略。在计算机科学和IT领域,缓存被广泛用于提高数据访问速度,通过将常用数据暂存到内存中,来减少对慢速存储(如硬盘)的访问。LRU Cache的...

    ARM高速缓存(Cache)Verilog代码 包含ISE工程

    Cache替换策略: LRU I_Cache的工作就是在cpu需要指令时将指令从主存中搬进I_Cache,再传给CPU,而D_Cache在解决数据读外,还要注意数据写入的问题。本工程可以与arm.v 中的arm 核协同工作,主存使用dram_ctrl_sim。

    lru-cache-js:使用双链表和映射实现 LRU Cache,读写时间复杂度为 O(1)

    LRU缓存使用的数据结构使用双向链表实现的队列。 队列的最大大小将等于...执行 npm i lru-cache-js-map const LRUCache = require('lru-cache-js-map');var cache = new LRUCache(100);for(var i=0; i &lt; 100; i++){

    bmob聊天组件优化

    "bmob聊天组件优化"就是这样一个专注于缓存优化的实践案例,它利用了LRU Cache和Disk LRU Cache来提高聊天功能的响应速度和效率。下面我们将深入探讨这两种缓存机制及其在聊天组件中的应用。 首先,LRU(Least ...

    LRU更新Cache

    LRU(Least Recently Used)缓存更新策略是一种广泛应用于计算机系统中的内存管理技术,尤其是在操作系统、数据库系统和编程语言的缓存实现中。LRU的基本思想是:当内存空间有限时,最近最少使用的数据应该优先被...

    PyPI 官网下载 | backports.functools_lru_cache-1.3.tar.gz

    《PyPI上的backports.functools_lru_cache-1.3.tar.gz:Python高效缓存技术解析》 在Python编程中,高效的代码执行是至关重要的,特别是在处理大量数据或者需要频繁重复计算的场景下。PyPI(Python Package Index)...

    SimpleLRUCache

    **简单最近最少使用缓存(SimpleLRUCache)** 在计算机科学中,缓存是一种用于存储经常访问数据的机制,以提高系统性能。最近最少使用(LRU, Least Recently Used)是缓存替换策略的一种,当缓存空间满时,会优先...

    LRU-Cache:这是 JavaScript 中的 LRU(最近最少使用)缓存实现

    LRU-Cache 这是 JavaScript 中的 LRU(最近最少使用)缓存实现。 它非常高效并且使用两种数据结构来管理元素。 双向链表和地图为我们提供了以下信息: 时间复杂度: O(1) 空间复杂度: O(n) 这是通过在我们必须...

Global site tag (gtag.js) - Google Analytics