LeetCode .146. LRU缓存机制-详解

problem

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果** (key) 存在于缓存中，则获取**的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果**不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得** 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得** 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

AC

ac1 php版本

我的做法是，用两个数组分别保存，key的顺序索引，用于增加和删除Key时候使用，和Key-Value数组。
put 时，需要考虑重复key 、key总数超过 capacity 的情况
get 时，把 key的顺序索引 使用的Key 置于数组首位，这样数组末位就是LRU删除的值。
需要保证每次插入的 KV 对，在 Index 数组中，是在队列首，如果超过 capacity 删除队尾，并且更新实际KV数组中对应的KV对。

# PHP版本
class LRUCache
{
    /**
     * @param Integer $capacity
     */
    function __construct($capacity)
    {
        $this->capacity = $capacity;
        $this->cache = array();
        $this->cacheIndex = array();

    }

    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key)
    {
        if (in_array($key,$this->cacheIndex)){
            unset($this->cacheIndex[array_search($key,$this->cacheIndex)]);
            array_unshift($this->cacheIndex,$key);
            return($this->cache[$key]);
        }else{
            return(-1);
        }
    }

    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value)
    {
        if (count($this->cache) == $this->capacity){
            if (in_array($key,$this->cacheIndex)){
                unset($this->cache[$this->cacheIndex[array_search($key,$this->cacheIndex)]]);
                unset($this->cacheIndex[array_search($key,$this->cacheIndex)]);
                array_unshift($this->cacheIndex,$key);
            }else{
                unset($this->cache[$this->cacheIndex[$this->capacity-1]]);
                unset($this->cacheIndex[$this->capacity-1]);
                array_unshift($this->cacheIndex,$key);
            }
        }else{
            if (in_array($key,$this->cacheIndex)){
                unset($this->cache[$this->cacheIndex[array_search($key,$this->cacheIndex)]]);
                unset($this->cacheIndex[array_search($key,$this->cacheIndex)]);
                array_unshift($this->cacheIndex,$key);
            }else{
                array_unshift($this->cacheIndex,$key);
            }
        }
        $this->cache[$key] = $value;
    }
}

第一个版本很粗糙，20s ，下面改进优化一下

ac2 php改进版本

改进思路： php中的数组实现是hashtable ，散列哈希表，搜索，插入删除都是O(1) 这里耗时的有两个，一个是 array_unshift 一个是 count ，把这两个优化一下，另外ac1 中的 put 方法逻辑上也可以优化，最终改了2，3个版本得到如下代码：

class LRUCache
{
    /**
     * @param Integer $capacity
     */
    function __construct($capacity)
    {
        $this->capacity = $capacity;
        $this->cache = array();
        $this->cacheIndex = array();
    }

    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key)
    {
        if (in_array($key, $this->cacheIndex)) {
            unset($this->cacheIndex[array_search($key, $this->cacheIndex)]);
            $this->cacheIndex[] = $key;
            return ($this->cache[$key]);
        } else {
            return (-1);
        }


    }

    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value)
    {
        if (in_array($key, $this->cacheIndex)) {
            unset($this->cache[$this->cacheIndex[array_search($key, $this->cacheIndex)]]);
            unset($this->cacheIndex[array_search($key, $this->cacheIndex)]);
            $this->cacheIndex[] = $key;
        } else {
            if (!$this->capacity > 0) {
                $popValue = array_shift($this->cacheIndex);
                unset($this->cache[$popValue]);
                $this->cacheIndex[] = $key;
            } else {
                $this->cacheIndex[] = $key;
                $this->capacity -= 1;
            }
        }
        $this->cache[$key] = $value;
    }
}

执行时间 300ms

ac3 python版本

这里用的是 collection 中的 OrdererdDict 数据结构。将最新的保留在tail，当Cache满了 pop head ，思路如下图：

import collections


class LRUCache(object):
    def __init__(self, capacity):
        self.dic = collections.OrderedDict()
        self.remain = capacity

    def get(self, key):
        if key not in self.dic:
            return -1
        v = self.dic.pop(key)
        self.dic[key] = v  # set key as newest
        return v

    def put(self, key, value):
        if key in self.dic:
            self.dic.pop(key)
        else:
            if self.remain > 0:
                self.remain -= 1
            else:  # dict is full
                self.dic.popitem(last=False)  # pop head
        self.dic[key] = value