网站快捷按钮以什么方式做,DW做的网站怎么弄兼容性,移动商城积分兑换话费,建设银行网银网站特色1、背景介绍
LRU、LFU都是内存管理淘汰算法#xff0c;内存管理是计算机技术中重要的一环#xff0c;也是多数操作系统中必备的模块。应用场景#xff1a;假设 给定你一定内存空间#xff0c;需要你维护一些缓存数据#xff0c;LRU、LFU就是在内存已经满了的情况下#…1、背景介绍
LRU、LFU都是内存管理淘汰算法内存管理是计算机技术中重要的一环也是多数操作系统中必备的模块。应用场景假设 给定你一定内存空间需要你维护一些缓存数据LRU、LFU就是在内存已经满了的情况下如果再次添加新的数据该淘汰哪些数据来留出新数据的内存空间
2、LRU(least recently used)
LRU(east recently used)即最近最少使用 也就是说 在内存满的情况下将会淘汰很久都没有使用过的数据。例如 leetcode 146题。
需求现在需要设计一个算法使得插入新数据、获取已经存入的数据使得平均时间复杂度O(1)。
设计思路因为插入、获取数据时都会更新时间戳还需要使得平均时间复杂度O(1)可以使用双链表哈希表的方式来存储。 如上图哈希表里存储 键与双链表节点双链表的head表示最近使用过的数据tail表示很久都没使用过的数据。 插入数据时在哈希表建立key与Node节点然后把Node节点插入双链表的头部位置。 获取数据时从哈希表拿到Node节点然后把Node节点从双链表中分离出来插入双链表的头部位置即可。
以上两个步骤时间复杂度都是O(1)。所以符合题意。
代码如下
// lc146题 直接能过的代码
class LRUCache {// LRU最近最少使用// 用双链表节点包装进行连接private HashMapInteger, Node map; // 哈希表存储key与双链表节点private int maxSize; // 缓存的最大容量private Node head, tail; // 头部是最近使用的尾部 是很久没使用的private static class Node { // 双链表节点int key, val;Node left, right;public Node(int k, int v) {key k;val v;}}public LRUCache(int capacity) {map new HashMap();maxSize capacity;}public int get(int key) {if(!map.containsKey(key)) return -1;Node node map.get(key);if (node head) return node.val;apart(node); //分离出node节点node.right head; // 插入到双链表的头部位置head.left node;head node;return node.val;}public void put(int key, int value) {if (!map.containsKey(key)) {Node node new Node(key, value);node.right head;if (head ! null) head.left node;if (tail null) tail node;head node;map.put(key, node);if (map.size() maxSize) { // 容量超了删除双链表的尾部元素if (tail.left ! null) {tail.left.right null;}map.remove(tail.key);Node pre tail.left;tail.left null;tail pre;}} else {Node node map.get(key);node.val value;get(key); // 调用get使其向前移动}}// node的左右两边连接将node抽离出private void apart(Node node) {node.left.right node.right;if (node.right ! null) {node.right.left node.left;}if (node tail) {tail node.left;}node.left node.right null;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj new LRUCache(capacity);* int param_1 obj.get(key);* obj.put(key,value);*/3、LFU(least frequancy used)
LFU(least frequancy used), 即不常用算法按照每个数据的访问次数来判断数据的使用情况。如果一个数据在近一段时间内没有被访问或者被访问的可能性小则会被淘汰。简单点说就是按照“使用频率”来分级的例题leetcode 460题
需求现在需要设计一个算法使得插入、获取数据的平均时间复杂度O(1)。
设计思路按照使用频率进行划分相同频率的数据放在同一个“桶”内从左往右频率逐渐升高而桶内部是从上往下按照插入桶内的时间来排序新插入的节点在桶的顶部很久之前插入的节点在桶的底部如下图所示 注意当内存满了的时候会删除 频率最低的桶内最后的一个数据节点。
代码实现如下
public class LFUCache {public LFUCache(int K) {capacity K;size 0;records new HashMap();heads new HashMap();headList null;}private int capacity; // 缓存的大小限制即Kprivate int size; // 缓存目前有多少个节点private HashMapInteger, Node records;// 表示key(Integer)由哪个节点(Node)代表private HashMapNode, NodeList heads; // 表示节点(Node)在哪个桶(NodeList)里private NodeList headList; // 整个结构中位于最左的桶// 节点的数据结构public static class Node {public Integer key;public Integer value;public Integer times; // 这个节点发生get或者set的次数总和public Node up; // 节点之间是双向链表所以有上一个节点public Node down;// 节点之间是双向链表所以有下一个节点public Node(int k, int v, int t) {key k;value v;times t;}}// 桶结构public static class NodeList {public Node head; // 桶的头节点public Node tail; // 桶的尾节点public NodeList last; // 桶之间是双向链表所以有前一个桶public NodeList next; // 桶之间是双向链表所以有后一个桶public NodeList(Node node) {head node;tail node;}// 把一个新的节点加入这个桶新的节点都放在顶端变成新的头部public void addNodeFromHead(Node newHead) {newHead.down head;head.up newHead;head newHead;}// 判断这个桶是不是空的public boolean isEmpty() {return head null;}// 删除node节点并保证node的上下环境重新连接public void deleteNode(Node node) {if (head tail) {head null;tail null;} else {if (node head) {head node.down;head.up null;} else if (node tail) {tail node.up;tail.down null;} else {node.up.down node.down;node.down.up node.up;}}node.up null;node.down null;}}// removeNodeList刚刚减少了一个节点的桶// 这个函数的功能是判断刚刚减少了一个节点的桶是不是已经空了。// 1如果不空什么也不做//// 2)如果空了removeNodeList还是整个缓存结构最左的桶(headList)。// 删掉这个桶的同时也要让最左的桶变成removeNodeList的下一个。//// 3)如果空了removeNodeList不是整个缓存结构最左的桶(headList)。// 把这个桶删除并保证上一个的桶和下一个桶之间还是双向链表的连接方式//// 函数的返回值表示刚刚减少了一个节点的桶是不是已经空了空了返回true不空返回falseprivate boolean modifyHeadList(NodeList removeNodeList) {if (removeNodeList.isEmpty()) {if (headList removeNodeList) {headList removeNodeList.next;if (headList ! null) {headList.last null;}} else {removeNodeList.last.next removeNodeList.next;if (removeNodeList.next ! null) {removeNodeList.next.last removeNodeList.last;}}return true;}return false;}// 函数的功能// node这个节点的次数1了这个节点原来在oldNodeList里。// 把node从oldNodeList删掉然后放到次数1的桶中// 整个过程既要保证桶之间仍然是双向链表也要保证节点之间仍然是双向链表private void move(Node node, NodeList oldNodeList) {oldNodeList.deleteNode(node);// preList表示次数1的桶的前一个桶是谁// 如果oldNodeList删掉node之后还有节点oldNodeList就是次数1的桶的前一个桶// 如果oldNodeList删掉node之后空了oldNodeList是需要删除的所以次数1的桶的前一个桶是oldNodeList的前一个NodeList preList modifyHeadList(oldNodeList) ? oldNodeList.last : oldNodeList;// nextList表示次数1的桶的后一个桶是谁NodeList nextList oldNodeList.next;if (nextList null) {NodeList newList new NodeList(node);if (preList ! null) {preList.next newList;}newList.last preList;if (headList null) {headList newList;}heads.put(node, newList);} else {if (nextList.head.times.equals(node.times)) {nextList.addNodeFromHead(node);heads.put(node, nextList);} else {NodeList newList new NodeList(node);if (preList ! null) {preList.next newList;}newList.last preList;newList.next nextList;nextList.last newList;if (headList nextList) {headList newList;}heads.put(node, newList);}}}public void put(int key, int value) {if (capacity 0) {return;}if (records.containsKey(key)) {Node node records.get(key);node.value value;node.times;NodeList curNodeList heads.get(node);move(node, curNodeList);} else {if (size capacity) {Node node headList.tail;headList.deleteNode(node);modifyHeadList(headList);records.remove(node.key);heads.remove(node);size--;}Node node new Node(key, value, 1);if (headList null) {headList new NodeList(node);} else {if (headList.head.times.equals(node.times)) {headList.addNodeFromHead(node);} else {NodeList newList new NodeList(node);newList.next headList;headList.last newList;headList newList;}}records.put(key, node);heads.put(node, headList);size;}}public int get(int key) {if (!records.containsKey(key)) {return -1;}Node node records.get(key);node.times;NodeList curNodeList heads.get(node);move(node, curNodeList);return node.value;}
}
