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

墨蓝 2022-03-17 17:40 196阅读 0赞

### 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 ，思路如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4MDE4Mjgz_size_16_color_FFFFFF_t_70]

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4MDE4Mjgz_size_16_color_FFFFFF_t_70]: /images/20220317/d8c5bf23da7043e38a578b68057a92f3.png