精选留言(11)

• 
  铁丑-王立丰

  2019-04-04

  嗯嗯，我下午也在想，这个队列应该是一个双向链表，而且新加的哈希表可能还要解决队列节点的冲突问题。设计的再复杂一点这个结构应该能够和原有的那张缓存哈希表融合。这样还能节省内存。

  作者回复: 融合的概念很新颖，代码可读性会弱一点，但是效率很高👍

  

  4
• 
  铁丑-王立丰

  2019-04-03

  查找数据是否在队列这个成本也不小啊

  作者回复: 这是个好问题，正常的情况下，我们假设哈希表和队列里的数据一致，除非发生了异常。 如果是这样，我们可以利用链表来实现队列，然后使用哈希表存储每个被缓存结果所对应的队列结点，这样我们可以快速访问队列的结点，并使用链表结点的移动来实现队列内结点的移动。

  

  4
• 
  失火的夏天

  2019-04-01

  因为篇幅不够，分段截出来了，这里先声明一个内部类，表示为队列（链表）的节点，接下来的Node节点是这个内部类 private class Node{ private Node prev; private Node next; private int key; private int value; Node(int key,int value){ this.key = key; this.value = value; } }

  展开

  

  3
• 
  Paul Shan

  2019-10-14

  缓存意味着数据源有两个，而且这两个数据源访问成本和数据完备度不同。访问成本低的数据不完备，数据完备的访问成本高。要结合这两个数据源来设计访问成本尽可能低，同时数据又是完备的系统。基于队列和哈希表实现的LRU算法是经典算法之一。队列维护缓存大小，满的时候淘汰最近没用到的数据。哈希表提升查询效率。每次访问，先查哈希表，如果数据存在，将该数据放到队列尾部，让其远离被淘汰的位置，然后返回数据。如果数据不存在，就从完备的数据源中取得数据，将数据放入队列，如果队列已满，则淘汰掉最近最少用的数据，然后得到最新返回的数据。队列要面临频繁的插入和改位置操作，选用基于双向链表的队列较为高效。

  展开

  

  2
• 
  建强

  2020-12-13

  受篇幅限制，有部分函数没有列出 # 定义哈希链表的节点 class HashLinkNode: def __init__(self, data, next=None): self.data = data self.next = next class LRUCache: # 缓存初始化 def __init__(self, maxsize): self.maxsize = maxsize self.currsize = 0 self.queue = [] self.hashtable = {} # 淘汰策略 def _takeout(self): data = self.queue.pop(0) # 取出队头元素 hashvalue = self._hashvalue(data) head = self.hashtable.get(hashvalue, None) node = head # 在哈希链表中查找并删除被淘汰的结点 if node is not None: while node.data != data and node.next is not None: node = node.next if node.data == data: if node.next is None: node.data = None else: node.data = node.next.data node.next = node.next.next if head is None or head.data is None: del self.hashtable[hashvalue] # 当前容量减1 self.currsize -= 1 # 数据加入缓存 def add(self, data): # 缓存已满，执行淘汰策略 if self._isfull(): self._takeout() hashvalue = self._hashvalue(data) node = HashLinkNode(data) head = self.hashtable.setdefault(hashvalue, None) node.next = head head = node self.hashtable[hashvalue] = head # 新加入的数据，置于队列尾 self.queue.append(data) # 当前缓存容量加1 self.currsize += 1 # 获取数据 def visit(self, data): hashvalue = self._hashvalue(data) head = self.hashtable.get(hashvalue, None) node = head while node is not None: # 访问命中，命中的数据置于队尾，返回True if node.data == data: del self.queue[self.queue.index(data)] self.queue.append(data) return True node = node.next return False

  展开

  

  1
• 
  qinggeouye

  2019-04-09

  # collections 的 OrderedDict() class LRUCache: def __init__(self, capacity): self.capacity = capacity self.queue = collections.OrderedDict() def get(self, key): if key not in self.queue: return -1 # 要找的数据不在缓存中则返回 -1 value = self.queue.pop(key) # 将命中缓存的数据移除 self.queue[key] = value # 将命中缓存的数据重新添加到头部 return self.queue[key] def put(self, key, value): if key in self.queue: # 如果已经存在缓存中，则先移除老的数据 self.queue.pop(key) elif len(self.queue.items()) == self.capacity: self.queue.popitem(last=False) # 如果不存在缓存并且达到最大容量 则把最后的数据淘汰 self.queue[key] = value # 将新数据添加到头部

  展开

  作者回复: 这部分实现主要侧重于queue实现LRU策略，依赖于Python queue的查找机制，如果Python的queue也有类似哈希表的查询效率，那么也是一种更简洁的实现方式。

  

  1
• 
  失火的夏天

  2019-04-01

  class LRUCache { private Node head;// 最近最少使用，类似列队的头，出队 private Node tail;// 最近最多使用，类似队列的尾，入队 private Map<Integer,Node> cache; private int capacity; public LRUCache(int capacity) { this.cache = new HashMap<>(); this.capacity = capacity; } public int get(int key) { Node node = cache.get(key); if(node == null){ return -1; }else{ moveNode(node); return node.value; } } public void put(int key, int value) { Node node = cache.get(key); if (node != null){ node.value = value; moveNode(node); }else { removeHead(); node = new Node(key,value); addNode(node); } cache.put(key,node); } private void removeHead(){ if (cache.size() == capacity){ Node tempNode = head; cache.remove(head.key); head = head.next; tempNode.next = null; if (head != null){ head.prev = null; } } } /** * 链表加入节点 * @param node */ private void addNode(Node node){ if (head == null){ head = node; tail = node; }else { addNodeToTail(node); } } private void addNodeToTail(Node node){ node.prev = tail; tail.next = node; tail = node; } private void moveNode(Node node){ if(head == node && node != tail){ head = node.next; head.prev = null; node.next = null; addNodeToTail(node); }else if (tail == node){ // 不做任何操作 }else { // 普遍情况，node节点移除链表，加入到尾节点后面，tail指针指向node node.prev.next = node.next; node.next.prev = node.prev; node.next = null; addNodeToTail(node); } } }

  展开

  作者回复: 实现的很仔细👍

  

  1
• 
  013923

  2022-09-23 来自上海

  使用哈希表和队列可以实现高效访问；

  

  
• 
  013923

  2022-09-15 来自上海

  Cache 是计算机OS的基本元件

  

  
• 
  013923

  2022-09-15 来自上海

  学习了Cache缓存系统；计算机基础课程

  

  
• 
  小灰

  2021-10-28

  老师请教一下，(1+7+5)/10^6=13 这个是怎么计算的

  作者回复: 由于排版的关系，应该是(1+7+5)%10^6，其中10^6表示10的6次方，计算优先级最高，所以是13%1000000，而%表示求余，求余为13

  

  