LRU算法 :学习笔记

泠音 · · 82 次点击 · · 开始浏览    

LRU算法 :学习笔记

LRU是什么

LRU(Least Recently Used)即最近最少使用,是一种缓存算法(页面置换算法)。我们知道,缓存通常是具有固定大小的,他应该只保存那些常常被用到的数据,而数据如何更新则是通过缓存算法实现,LRU算法就是一种简单,常用的缓存算法。

原理

LRU算法是核心思想是:如果一个数据在最近一段时间都没有被用到,那么它在将来被使用到的可能性也很小。故当缓存空间已满的情况下,我们需要淘汰掉最久没有被访问到的数据。理想的LRU算法读写是时间复杂度应该都为O(1)。

实现

为了达到理想的性能,我们需要一种既可以按访问顺序排序,又可以在常数时间随机访问的数据结构。这里可以采用HashMap和双向链表实现。HashMap可以存储Key,可以在常数时间里读写Key,而Value用来指向双向链表的节点,为了在常数时间里移除一个节点我们还需要Head节点和Tril节点。

  1. put(key,value)
    首先在HashMap中查找Key如果存在,说明数据已在缓存中,我们只需要更新节点的值,并将节点放到链表头部即可。如果不存在说明数据不在缓存中,则需要构造节点,并将其放置在头部。在这个过程中,如果发现缓存已满,则需要淘汰掉链表尾部的数据并在HashMap中移除相应的Key。
  2. get(key)
    通过HashMap查找对应的节点,将其移动至头部并返回。

代码实现如下:

class LruCache<K, V>() {
    private data class Node<K, V>(
            var key: K? = null,
            var value: V? = null,
            var prev: Node<K, V>? = null,
            var next: Node<K, V>? = null
    )

    private val hashMap: HashMap<K, Node<K, V>> = hashMapOf()
    private var count = 0
    private var capacity = 8
    private val head: Node<K, V> = Node()
    private val tail: Node<K, V> = Node()

    init {
        head.next = tail
        tail.prev = head
    }

    constructor(capacity: Int) : this() {
        this.capacity = capacity
    }

    fun get(key: K): V? {
        val node = hashMap[key] ?: return null
        move(node)
        return node.value
    }

    fun put(key: K, value: V) {
        val node = hashMap[key]
        if (node == null) {
            val newNode = Node(key, value)
            add(newNode)
            hashMap[key] = newNode
            ++count
            if (count > capacity) {
                val deleteNode = delete()
                hashMap.remove(deleteNode.key)
                --count
            }
        } else {
            node.value = value
            move(node)
        }
    }

    private fun add(node: Node<K, V>) {
        node.prev = head
        node.next = head.next
        head.next!!.prev = node
        head.next = node
    }

    private fun remove(node: Node<K, V>) {
        val prev = node.prev!!
        val next = node.next!!
        prev.next = next
        next.prev = prev
    }

    private fun move(node: Node<K, V>) {
        remove(node)
        add(node)
    }

    private fun delete(): Node<K, V> {
        val node = tail.prev!!
        remove(node)
        return node
    }
}

而在实际使用中,我们可以使用LinkedHashMap实现,其内部就是使用双向链表,我们只需稍作修改便能使用。
在LinkedHashMap的构造参数(initialCapacity:Int, loadFactor:Float,accessOrder:Boolean)中,initialCapacity是HashMap的初始大小,loadFactor则是装载因子,accessOrder=false表示基于插入顺序,accessOrder=true表示基于访问顺序。
实现LRU的关键方法:

override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?): Boolean {
    return size > capacity
}

以上表示当LinkedHashMap大小超过我们设定的大小时,移除链表首部的节点

class LruChche<K, V>(private val capacity: Int = 8) {
    private var hashMap: LinkedHashMap<K, V> = object : LinkedHashMap<K, V>
    (capacity / 0.75.toInt() + 1, 0.75f, true) {
        override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?): Boolean {
            return size > capacity
        }
    }

    fun get(key: K): V? = hashMap[key]
    fun put(key: K, value: V) {
        hashMap[key] = value
    }

}

结语

第一次听说LRU算法是在现代操作系统这本书中,但引起我深究的是Glide这个库在自定义Model的时候,便有了一探究竟的想法,故整理资料写下这些文字,一面是为了加深自己的影响,另一面也希望我所说的能让大家更简单的去理解LRU,一起学习。

本文来自:Segmentfault

感谢作者:泠音

查看原文:LRU算法 :学习笔记

82 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet