Linux迷+Python粉 - LRU//blog.pythonwood.com/2019-08-22T14:00:00+08:00面试高频题-LRU缓存的python实现2019-08-22T14:00:00+08:002019-08-22T14:00:00+08:00pythonwoodtag:blog.pythonwood.com,2019-08-22:/2019/08/面试高频题-LRU缓存的python实现/<p>过程简略:&nbsp;url去重的方法,数据库四种隔离级别,乐观锁悲观锁,算法题研讨。算法讨论占了很长时间,以下是把这个过程沉淀后的一遍随笔。</p> <h3 id="leetcode146-lru">leetcode算法题:146. <span class="caps">LRU</span>缓存机制<a class="headerlink" href="#leetcode146-lru" title="Permanent link">&para;</a></h3> <p><a href="https://leetcode-cn.com/problems/lru-cache/">https://leetcode-cn.com/problems/lru-cache/</a></p> <blockquote> <p>运用你所掌握的数据结构,设计和实现一个  <span class="caps">LRU</span> (最近最少使用 …</p></blockquote><p>过程简略:&nbsp;url去重的方法,数据库四种隔离级别,乐观锁悲观锁,算法题研讨。算法讨论占了很长时间,以下是把这个过程沉淀后的一遍随笔。</p> <h3 id="leetcode146-lru">leetcode算法题:146. <span class="caps">LRU</span>缓存机制<a class="headerlink" href="#leetcode146-lru" title="Permanent link">&para;</a></h3> <p><a href="https://leetcode-cn.com/problems/lru-cache/">https://leetcode-cn.com/problems/lru-cache/</a></p> <blockquote> <p>运用你所掌握的数据结构,设计和实现一个  <span class="caps">LRU</span> (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put&nbsp;。</p> <p>获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回&nbsp;-1。</p> <p>写入数据 put(key, value) -&nbsp;如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。</p> <p>进阶:</p> <p>你是否可以在 O(1)&nbsp;时间复杂度内完成这两种操作?</p> <p>示例:</p> </blockquote> <div class="highlight"><pre><span></span>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 </pre></div> <h2 id="_1">思考过程简要<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h2> <p>第一次遇到,没有做好题。之后总结思考如下。面试完重新整理好代码,才通过。</p> <p>1、数据结构知识弱,链表随机增删复杂度O(1),&nbsp;数组复杂度O(n)。使用按时间排序的双向链表。头部总是最新访问或插入的,尾巴总是最老的。使用额外maxsize限制大小,nowsize记录目前大小。</p> <p>2、链表元素是key-val的进一步封装的Node类。链表是另一个类,类总head和tail表示头尾两个空的node。一直不删。</p> <p>3、开头想到最小堆,用得不对。二分法等比较查找下限O(lgN),与哈希法的O(1)差距意识不明显。而哈希函数用内置字典即可。</p> <p>4、拆分小函数复用代码。比如get = 出链 + 插入头部, put = 出链 + 插入头部(update) 或者&nbsp;插入头部(非update)</p> <p>5、之后发现python有functools.lru_cache的现成实现,值得学习。</p> <h2 id="leetcode">leetcode通过提交的代码<a class="headerlink" href="#leetcode" title="Permanent link">&para;</a></h2> <div class="highlight"><pre><span></span><span class="kr">class</span> <span class="nx">Node</span>: <span class="kt">def</span> <span class="nx">__init__</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">key</span><span class="o">=</span><span class="nx">None</span><span class="p">,</span> <span class="nx">val</span><span class="o">=</span><span class="nx">None</span><span class="p">)</span><span class="o">:</span> <span class="nx">self</span><span class="p">.</span><span class="nx">key</span> <span class="o">=</span> <span class="nx">key</span> <span class="nx">self</span><span class="p">.</span><span class="nx">val</span> <span class="o">=</span> <span class="nx">val</span> <span class="nx">self</span><span class="p">.</span><span class="nx">prev</span> <span class="o">=</span> <span class="nx">None</span> <span class="nx">self</span><span class="p">.</span><span class="nx">next</span> <span class="o">=</span> <span class="nx">None</span> <span class="kr">class</span> <span class="nx">LRUCache</span><span class="o">:</span> <span class="s1">&#39;&#39;&#39;</span> <span class="s1"> 小函数: 删node,入head</span> <span class="s1"> 注意:head和tail是空的node,不能删除</span> <span class="s1"> &#39;&#39;&#39;</span> <span class="nx">def</span> <span class="nx">__init__</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">maxsize</span><span class="o">=</span><span class="mi">10</span><span class="p">)</span><span class="o">:</span> <span class="nx">self</span><span class="p">.</span><span class="nx">maxsize</span> <span class="o">=</span> <span class="nx">maxsize</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nowsize</span> <span class="o">=</span> <span class="mi">0</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span> <span class="o">=</span> <span class="nx">Node</span><span class="p">()</span> <span class="nx">self</span><span class="p">.</span><span class="nx">tail</span> <span class="o">=</span> <span class="nx">Node</span><span class="p">()</span> <span class="nx">self</span><span class="p">.</span><span class="nx">tail</span><span class="p">.</span><span class="nx">prev</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span><span class="p">.</span><span class="nx">next</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">tail</span> <span class="err">#</span> <span class="nx">key</span> <span class="o">-&gt;</span> <span class="nx">nodes</span><span class="p">.</span><span class="nx">val</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nodes</span> <span class="o">=</span> <span class="p">{}</span> <span class="nx">def</span> <span class="nx">get</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">key</span><span class="p">)</span><span class="o">:</span> <span class="nx">node</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nodes</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="nx">key</span><span class="p">,</span> <span class="nx">None</span><span class="p">)</span> <span class="k">if</span> <span class="nx">node</span> <span class="o">!=</span> <span class="nx">None</span><span class="o">:</span> <span class="err">#</span> <span class="mi">2019</span><span class="o">-</span><span class="mi">08</span><span class="o">-</span><span class="mi">21</span><span class="err">面试时加的要求</span> <span class="nx">self</span><span class="p">.</span><span class="nx">popNode</span><span class="p">(</span><span class="nx">node</span><span class="p">)</span> <span class="nx">self</span><span class="p">.</span><span class="nx">addNode</span><span class="p">(</span><span class="nx">node</span><span class="p">)</span> <span class="k">return</span> <span class="nx">node</span><span class="p">.</span><span class="nx">val</span> <span class="k">else</span><span class="o">:</span> <span class="k">return</span> <span class="o">-</span><span class="mi">1</span> <span class="nx">def</span> <span class="nx">put</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">key</span><span class="p">,</span> <span class="nx">val</span><span class="p">)</span><span class="o">:</span> <span class="nx">self</span><span class="p">.</span><span class="nx">set</span><span class="p">(</span><span class="nx">key</span><span class="p">,</span> <span class="nx">val</span><span class="p">)</span> <span class="nx">def</span> <span class="nx">set</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">key</span><span class="p">,</span> <span class="nx">val</span><span class="p">)</span><span class="o">:</span> <span class="nx">node</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nodes</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="nx">key</span><span class="p">,</span> <span class="nx">None</span><span class="p">)</span> <span class="k">if</span> <span class="nx">node</span> <span class="o">!=</span> <span class="nx">None</span><span class="o">:</span> <span class="err">#</span> <span class="err">在链表中,</span><span class="nx">update</span><span class="err">操作</span> <span class="nx">self</span><span class="p">.</span><span class="nx">popNode</span><span class="p">(</span><span class="nx">node</span><span class="p">)</span> <span class="err">#</span> <span class="nx">self</span><span class="p">.</span><span class="nx">addNode</span><span class="p">(</span><span class="nx">Node</span><span class="p">(</span><span class="nx">key</span><span class="p">,</span> <span class="nx">val</span><span class="p">))</span> <span class="nx">def</span> <span class="k">delete</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">key</span><span class="p">)</span><span class="o">:</span> <span class="nx">node</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nodes</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="nx">key</span><span class="p">,</span> <span class="nx">None</span><span class="p">)</span> <span class="k">if</span> <span class="nx">node</span> <span class="o">!=</span> <span class="nx">None</span>: <span class="kt">self.popNode</span><span class="p">(</span><span class="nx">node</span><span class="p">)</span> <span class="nx">def</span> <span class="nx">popNode</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">node</span><span class="p">)</span><span class="o">:</span> <span class="k">if</span> <span class="nx">node</span><span class="p">.</span><span class="nx">val</span> <span class="o">==</span> <span class="nx">None</span>: <span class="kt">return</span> <span class="err">#</span> <span class="err">使用</span><span class="nx">head</span><span class="err">和</span><span class="nx">tail</span><span class="err">为空</span><span class="nx">node</span><span class="err">时无需检查</span> <span class="err">#</span> <span class="k">if</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span><span class="o">:</span> <span class="err">#</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span><span class="p">.</span><span class="nx">prev</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">prev</span> <span class="err">#</span> <span class="k">else</span><span class="o">:</span> <span class="err">#</span> <span class="nx">self</span><span class="p">.</span><span class="nx">tail</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span> <span class="err">#</span> <span class="k">if</span> <span class="nx">node</span><span class="p">.</span><span class="nx">prev</span><span class="o">:</span> <span class="err">#</span> <span class="nx">node</span><span class="p">.</span><span class="nx">prev</span><span class="p">.</span><span class="nx">next</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span> <span class="err">#</span> <span class="k">else</span><span class="o">:</span> <span class="err">#</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span><span class="p">.</span><span class="nx">prev</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">prev</span> <span class="nx">node</span><span class="p">.</span><span class="nx">prev</span><span class="p">.</span><span class="nx">next</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nowsize</span> <span class="o">-=</span> <span class="mi">1</span> <span class="err">#</span> <span class="err">字典更新</span> <span class="nx">del</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nodes</span><span class="p">[</span><span class="nx">node</span><span class="p">.</span><span class="nx">key</span><span class="p">]</span> <span class="k">return</span> <span class="nx">node</span> <span class="nx">def</span> <span class="nx">addNode</span><span class="p">(</span><span class="nx">self</span><span class="p">,</span> <span class="nx">node</span><span class="p">)</span><span class="o">:</span> <span class="err">#</span> <span class="err">总在链表头加入</span> <span class="k">if</span> <span class="nx">node</span><span class="p">.</span><span class="nx">val</span> <span class="o">==</span> <span class="nx">None</span>: <span class="kt">return</span> <span class="k">if</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nowsize</span> <span class="o">&gt;=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">maxsize</span><span class="o">:</span> <span class="err">#</span> <span class="err">满了,就去掉尾巴再插入</span> <span class="nx">self</span><span class="p">.</span><span class="nx">popNode</span><span class="p">(</span><span class="nx">self</span><span class="p">.</span><span class="nx">tail</span><span class="p">.</span><span class="nx">prev</span><span class="p">)</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span><span class="p">.</span><span class="nx">next</span> <span class="nx">node</span><span class="p">.</span><span class="nx">prev</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span><span class="p">.</span><span class="nx">next</span><span class="p">.</span><span class="nx">prev</span> <span class="o">=</span> <span class="nx">node</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span><span class="p">.</span><span class="nx">next</span> <span class="o">=</span> <span class="nx">node</span> <span class="err">#</span> <span class="err">费时的</span><span class="nx">debug</span><span class="err">错误:这句之后</span><span class="p">[[</span><span class="s1">&#39;c&#39;</span><span class="p">,</span> <span class="mi">12</span><span class="p">]]</span> <span class="o">-&gt;</span> <span class="p">[]</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nowsize</span> <span class="o">+=</span> <span class="mi">1</span> <span class="err">#</span> <span class="err">字典增加</span> <span class="nx">self</span><span class="p">.</span><span class="nx">nodes</span><span class="p">[</span><span class="nx">node</span><span class="p">.</span><span class="nx">key</span><span class="p">]</span> <span class="o">=</span> <span class="nx">node</span> <span class="kd">@property</span> <span class="nx">def</span> <span class="nx">vals</span><span class="p">(</span><span class="nx">self</span><span class="p">)</span><span class="o">:</span> <span class="err">#</span> <span class="nx">debug</span> <span class="err">#</span> <span class="nx">node</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span> <span class="err">#</span> <span class="err">错误:发现用时</span><span class="mi">15</span><span class="err">分钟</span> <span class="nx">node</span> <span class="o">=</span> <span class="nx">self</span><span class="p">.</span><span class="nx">head</span><span class="p">.</span><span class="nx">next</span> <span class="nx">_vals</span> <span class="o">=</span> <span class="p">[]</span> <span class="err">#</span> <span class="k">while</span> <span class="nx">node</span><span class="p">.</span><span class="nx">val</span><span class="o">:</span> <span class="err">#</span> <span class="mi">2019</span><span class="o">-</span><span class="mi">08</span><span class="o">-</span><span class="mi">21</span><span class="err">大坑,</span><span class="nx">node</span><span class="p">.</span><span class="nx">val</span> <span class="o">=</span> <span class="mi">0</span><span class="err">时会失败!费了</span><span class="mi">1</span><span class="err">小时!!!</span> <span class="k">while</span> <span class="nx">node</span> <span class="o">!=</span> <span class="nx">None</span> <span class="nx">and</span> <span class="nx">node</span><span class="p">.</span><span class="nx">val</span> <span class="o">!=</span> <span class="nx">None</span>: <span class="kt">_vals.append</span><span class="p">([</span><span class="nx">node</span><span class="p">.</span><span class="nx">key</span><span class="p">,</span><span class="nx">node</span><span class="p">.</span><span class="nx">val</span><span class="p">])</span> <span class="nx">node</span> <span class="o">=</span> <span class="nx">node</span><span class="p">.</span><span class="nx">next</span> <span class="k">return</span> <span class="nx">_vals</span> <span class="nx">def</span> <span class="nx">pprint</span><span class="p">(</span><span class="nx">self</span><span class="p">)</span><span class="o">:</span> <span class="err">#</span> <span class="nx">debug</span> <span class="nx">print</span><span class="p">(</span><span class="nx">self</span><span class="p">.</span><span class="nx">vals</span><span class="p">,</span> <span class="nx">flush</span><span class="o">=</span><span class="nx">True</span><span class="p">)</span> <span class="k">if</span> <span class="nx">__name__</span> <span class="o">==</span> <span class="s1">&#39;__main__&#39;</span><span class="o">:</span> <span class="nx">lru</span> <span class="o">=</span> <span class="nx">LRUCache</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">set</span><span class="p">(</span><span class="s1">&#39;b&#39;</span><span class="p">,</span> <span class="mi">12</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">print</span><span class="p">(</span><span class="s1">&#39;stage end: -----------------&#39;</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">set</span><span class="p">(</span><span class="s1">&#39;a&#39;</span><span class="p">,</span> <span class="mi">12</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">set</span><span class="p">(</span><span class="s1">&#39;d&#39;</span><span class="p">,</span> <span class="mi">12</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">set</span><span class="p">(</span><span class="s1">&#39;c&#39;</span><span class="p">,</span> <span class="mi">12</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">print</span><span class="p">(</span><span class="s1">&#39;stage end: -----------------&#39;</span><span class="p">)</span> <span class="nx">print</span><span class="p">(</span><span class="nx">lru</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="s1">&#39;a&#39;</span><span class="p">))</span> <span class="nx">print</span><span class="p">(</span><span class="s1">&#39;stage end: -----------------&#39;</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="k">delete</span><span class="p">(</span><span class="s1">&#39;a&#39;</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">print</span><span class="p">(</span><span class="s1">&#39;stage end: -----------------&#39;</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">set</span><span class="p">(</span><span class="s1">&#39;d&#39;</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="nx">lru</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">print</span><span class="p">(</span><span class="s1">&#39;stage end: -----------------&#39;</span><span class="p">)</span> <span class="err">#</span> <span class="nx">leetcode</span><span class="err">的测试用例</span> <span class="nx">cache</span> <span class="o">=</span> <span class="nx">LRUCache</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">put</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">put</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="mi">2</span><span class="p">);</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span> <span class="err">#</span> <span class="err">返回</span> <span class="mi">1</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">put</span><span class="p">(</span><span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">);</span> <span class="err">#</span> <span class="err">该操作会使得密钥</span> <span class="mi">2</span> <span class="err">作废</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="mi">2</span><span class="p">);</span> <span class="err">#</span> <span class="err">返回</span> <span class="o">-</span><span class="mi">1</span> <span class="p">(</span><span class="err">未找到</span><span class="p">)</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">put</span><span class="p">(</span><span class="mi">4</span><span class="p">,</span> <span class="mi">4</span><span class="p">);</span> <span class="err">#</span> <span class="err">该操作会使得密钥</span> <span class="mi">1</span> <span class="err">作废</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span> <span class="err">#</span> <span class="err">返回</span> <span class="o">-</span><span class="mi">1</span> <span class="p">(</span><span class="err">未找到</span><span class="p">)</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">pprint</span><span class="p">()</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="mi">3</span><span class="p">);</span> <span class="err">#</span> <span class="err">返回</span> <span class="mi">3</span> <span class="nx">cache</span><span class="p">.</span><span class="nx">get</span><span class="p">(</span><span class="mi">4</span><span class="p">);</span> <span class="err">#</span> <span class="err">返回</span> <span class="mi">4</span> </pre></div> <h2 id="_2">参考<a class="headerlink" href="#_2" title="Permanent link">&para;</a></h2> <ol> <li> <p>leetcode算法题:146. <span class="caps">LRU</span>缓存机制 <a href="https://leetcode-cn.com/problems/lru-cache/">https://leetcode-cn.com/problems/lru-cache/</a></p> </li> <li> <p>Python 缓存机制与 functools.lru_cache <a href="http://blog.konghy.cn/2016/04/20/python-cache/">http://blog.konghy.cn/2016/04/20/python-cache/</a></p> </li> </ol>