LFU算法

发布时间:2024年01月24日

LFU算法

Least Frequently Used(最不频繁使用)
在这里插入图片描述
Leetcode有原题,之前手写过LRU,数据结构还是习惯于用java实现,实现是copy的评论题解。
题解注释写的很清楚

大致就是说LFUCache类维护一个存放node的map,同时维护两个双向链表,注意这个双向链表里面又包含了两个双向链表,访问的频率是first最大,last最小。其余的就是正常的双向链表的操作了(插入,删除)

import java.util.HashMap;
import java.util.Map;

class LFUCache {

    Map<Integer, Node> cache; // 存储缓存的内容,Node中除了value值外,还有key、freq、所在doublyLinkedList、所在doublyLinkedList中的postNode、所在doublyLinkedList中的preNode,具体定义在下方。

    DoublyLinkedList firstLinkedList; // firstLinkedList.post 是频次最大的双向链表

    DoublyLinkedList lastLinkedList; // lastLinkedList.pre 是频次最小的双向链表,满了之后删除 lastLinkedList.pre.tail.pre
                                     // 这个Node即为频次最小且访问最早的Node

    int size;

    int capacity;

    public LFUCache(int capacity) {

        cache = new HashMap<>(capacity);

        firstLinkedList = new DoublyLinkedList();

        lastLinkedList = new DoublyLinkedList();

        firstLinkedList.post = lastLinkedList;  // 是按照倒序排列的,最大的是first

        lastLinkedList.pre = firstLinkedList;

        this.capacity = capacity;

    }

    public int get(int key) {

        Node node = cache.get(key);

        if (node == null) {

            return -1;

        }

        // 该key访问频次+1

        freqInc(node);

        return node.value;

    }

    public void put(int key, int value) {

        if (capacity == 0) {

            return;

        }

        Node node = cache.get(key);

        // 若key存在,则更新value,访问频次+1

        if (node != null) {

            node.value = value;

            freqInc(node);

        } else {

            // 若key不存在

            if (size == capacity) {

                // 如果缓存满了,删除lastLinkedList.pre这个链表(即表示最小频次的链表)中的tail.pre这个Node(即最小频次链表中最先访问的Node),如果该链表中的元素删空了,则删掉该链表。

                cache.remove(lastLinkedList.pre.tail.pre.key);

                lastLinkedList.removeNode(lastLinkedList.pre.tail.pre);

                size--;

                if (lastLinkedList.pre.head.post == lastLinkedList.pre.tail) {

                    removeDoublyLinkedList(lastLinkedList.pre);

                }

            }

            // cache中put新Key-Node对儿,并将新node加入表示freq为1的DoublyLinkedList中,若不存在freq为1的DoublyLinkedList则新建。

            Node newNode = new Node(key, value);

            cache.put(key, newNode);

            if (lastLinkedList.pre.freq != 1) {

                DoublyLinkedList newDoublyLinedList = new DoublyLinkedList(1);

                addDoublyLinkedList(newDoublyLinedList, lastLinkedList.pre);

                newDoublyLinedList.addNode(newNode);

            } else {

                lastLinkedList.pre.addNode(newNode);

            }

            size++;

        }

    }

    /**
     * node的访问频次 + 1
     */
    void freqInc(Node node) {

        // 将node从原freq对应的双向链表里移除, 如果链表空了则删除链表。

        DoublyLinkedList linkedList = node.doublyLinkedList;

        DoublyLinkedList preLinkedList = linkedList.pre;

        linkedList.removeNode(node);

        if (linkedList.head.post == linkedList.tail) {

            removeDoublyLinkedList(linkedList);

        }

        // 将node加入新freq对应的双向链表,若该链表不存在,则先创建该链表。

        node.freq++;

        if (preLinkedList.freq != node.freq) {

            DoublyLinkedList newDoublyLinedList = new DoublyLinkedList(node.freq);

            addDoublyLinkedList(newDoublyLinedList, preLinkedList);

            newDoublyLinedList.addNode(node);

        } else {

            preLinkedList.addNode(node);

        }

    }

    /**
     * 增加代表某1频次的双向链表
     */
    void addDoublyLinkedList(DoublyLinkedList newDoublyLinedList, DoublyLinkedList preLinkedList) {

        newDoublyLinedList.post = preLinkedList.post;

        newDoublyLinedList.post.pre = newDoublyLinedList;

        newDoublyLinedList.pre = preLinkedList;

        preLinkedList.post = newDoublyLinedList;

    }

    /**
     * 删除代表某1频次的双向链表
     */
    void removeDoublyLinkedList(DoublyLinkedList doublyLinkedList) {

        doublyLinkedList.pre.post = doublyLinkedList.post;

        doublyLinkedList.post.pre = doublyLinkedList.pre;

    }

}

class Node {

    int key;

    int value;

    int freq = 1;

    Node pre; // Node所在频次的双向链表的前继Node

    Node post; // Node所在频次的双向链表的后继Node

    DoublyLinkedList doublyLinkedList; // Node所在频次的双向链表

    public Node() {
    }

    public Node(int key, int value) {

        this.key = key;

        this.value = value;

    }

}

class DoublyLinkedList {

    int freq; // 该双向链表表示的频次

    DoublyLinkedList pre; // 该双向链表的前继链表(pre.freq < this.freq)

    DoublyLinkedList post; // 该双向链表的后继链表 (post.freq > this.freq)

    Node head; // 该双向链表的头节点,新节点从头部加入,表示最近访问

    Node tail; // 该双向链表的尾节点,删除节点从尾部删除,表示最久访问

    public DoublyLinkedList() {

        head = new Node();

        tail = new Node();

        head.post = tail;

        tail.pre = head;

    }

    public DoublyLinkedList(int freq) {

        head = new Node();

        tail = new Node();

        head.post = tail;

        tail.pre = head;

        this.freq = freq;

    }

    void removeNode(Node node) {

        node.pre.post = node.post;

        node.post.pre = node.pre;

    }

    void addNode(Node node) {

        node.post = head.post;

        head.post.pre = node;

        head.post = node;

        node.pre = head;
        node.doublyLinkedList = this;

    }

}

文章来源:https://blog.csdn.net/qq_40896190/article/details/135826178
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。