多重双向链表实现LFU算法

时间:2020-9-11 作者:admin


导航

前言

昨天在 leetcode 460 上学习LFU算法,看见一个大佬写的O(1) 解法 —— 存储频次的HashMap改为直接用双向链表(最优实现 13ms 双100%),印象颇深,隔了一天之后照着他的思路自己也手写实现了LFU,和原版略有不同,不过思路很值得讲

源码

点击这里获取源码,别忘了点个Star哦~

一、思路

一般来说,我们理解的链表都是这样的:
多重双向链表实现LFU算法

我们可以通过双链表实现LRU,但是LFU呢?它比LRU要多出一个“访问频次”的属性,只靠双链表似乎并不能满足LFU的设计需求

那么我们用很多条链表来做这件事怎么样?既可以通过链表的特性保证访问时间和顺序的关系,又可以让每个链表记录一个频次,里面存放的都是对应频次的数据:
多重双向链表实现LFU算法
在每条链表中又按照频次大小顺序连接着,这也可以形容为“链链表”,用代码来讲,就是:LinkedList<LinkedList<Node>>

那么要如何使用这多重链表呢

  • 在已有多条链表分别存储数据的情况下,put操作时,在频次最大的链表上进行头插(缓存满时,要删除频次最小的链表的尾节点)
  • 在缓存为空时,put操作时,让缓存生成一条频次为0的链表,并在该链表上进行头插
  • 在put,get操作命中缓存时,让缓存中被命中的数据节点移动到(当前频次+1)的频次链表上
  • 若频次最小的链表仅剩的节点被删除,则删除频次最小的链表(即对“链链表”进行尾删

二、核心定义

1. 类的层次

在我的容器设计中,我的类定义的层次如下

// 最外层,LFU缓存容器类
public class MultiLinkedListLFU<K, V> {
	// 中间层,多重链表类
	private class MultiLinkedList {
		// 最内层,链表节点类
		class Entry {
		
		}
	}
}

2. 链表节点类

我的链表节点类存放键值对,如下

        class Entry {
            K key;
            V val;

            Entry pre, next;

            Entry(K key, V val) {
                this.key = key;
                this.val = val;
            }
        }

没什么特别的,不熟的同学建议复习下双向链表

3. 多重链表类

1)类的字段

        /**
         * 记录被访问的频次
         */
        int freq;

        /**
         * 前/后链表
         */
        MultiLinkedList pre, next;

        /**
         * 当前链表的头/尾节点
         */
        Entry head, tail;

        /**
         * 当前链表的长度
         */
        private int size;

这个类的实例是一条链表,每条链表都记录着频次的字段freq,并且有前后指针MultiLinkedList pre, next指向其自身的上一条/下一条链表,除此之外,头/尾节点和链表长度的字段基本上都是一条双向链表要记录的字段

2)构造方法

        /**
         * 无参构造方法
         */
        MultiLinkedList() {
        }

        /**
         * 有参构造方法
         *
         * @param freq
         */
        MultiLinkedList(int freq) {
            this.freq = freq;
        }

有参构造方法为实例记录传入的频次,无参则默认生成频次为0的实例

3)方法实现

a. 添加数据方法put

        /**
         * 添加数据方法
         *
         * @param key
         * @param val
         */
        void put(K key, V val) {
            // 链表为空/不为空,分情况讨论
            if (size == 0) {
                head = new Entry(key, val);
                tail = head;
                ++size;
            } else {
                addToHead(new Entry(key, val));
            }
        }

addToHead方法就是头插方法

b. 删除指定key的节点方法

        /**
         * 通过key删除指定节点
         *
         * @param key
         */
        boolean removeEntryByKey(K key) {
            Entry entry = findEntryByKey(key);
            if (entry == null) {
                //未找到指定节点,删除失败
                return false;
            } else {
                // 当前key得到的节点是尾节点时,直接尾删
                if (key.equals(tail.key)) {
                    removeLast();
                    // 当前key得到的节点是头节点时,直接头删
                } else if (key.equals(head.key)) {
                    removeFirst();
                } else {
                    removeEntry(entry);
                }
                return true;
            }
        }

头删removeFirst(),尾删removeLast,头插addToHead,删除指定节点removeEntry(Entry entry)等方法在往期文章都有提到,就不再赘述

*c. toString方法

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (Entry cur = head; cur != null; cur = cur.next) {
                sb.append(cur.key)
                        .append("->");
            }
            return sb.substring(0, sb.length() - 2).toString();
        }

为了方便测试输出而写

4. LFU实现类

1)类的字段

    /**
     * 记录<键key,频次freq>的哈希图,用于快速定位节点
     */
    private final HashMap<K, Integer> KEY_FREQ_MAP = new HashMap<>();

    /**
     * 头/尾链表
     */
    private MultiLinkedList headList, tailList;

    /**
     * 容器中链表的数量
     */
    private int listAmount;

    /**
     * 容量
     */
    private int capacity;

原作者的HashMap存储的是<key,Node>,他的Node除了存储键值对以外还存储频次,而我的HashMap:private final HashMap<K, Integer> KEY_FREQ_MAP = new HashMap<>();只存储了key和频次,在后面的节点查找中时间复杂度会较大

作为“链链表”套娃的最外层,这里将头/尾节点的概念应用为头/尾链表:private MultiLinkedList headList, tailList,如果你把一条链表当作一个节点来看,那么就很容易说得通了

2)构造方法


    /**
     * 有参构造方法
     *
     * @param capacity
     */
    public MultiLinkedListLFU(int capacity) {
        this.capacity = capacity;
    }

传入一个容量字段,供缓存容器检测缓存是否满了即可

3)私有方法

这里我们将“链链表”做一个定义:

  • 头节点链表headList的频次最高,尾节点链表tailList的频次最低
  • 该进行缓存淘汰时,对尾节点链表tailList进行尾删,如果此时tailList经过尾删后长度为0,则对“链链表”进行尾删,即删除尾节点链表
  • 插入数据时,在头节点链表headList上进行头插
  • 数据被访问时,将该数据移动到其所在链表list的前一个链表list.pre的头部

a. “链链表”的尾删

    /**
     * 删除尾链表
     */
    private void removeTailList() {
        tailList = tailList.pre;
        tailList.next = null;
        --listAmount;
    }

和常规的链表尾删是一样的

b. “链链表”的头插

    /**
     * 新增一条频次比当前头链表多1的链表,并将其作为新头链表
     */
    private void newHeadList() {
        MultiLinkedList newList = new MultiLinkedList(headList.freq + 1);
        newList.next = headList;
        headList.pre = newList;
        headList = newList;
        ++listAmount;
    }

这里除了要注意频次的处理以外,和常规的链表头插也是一样的

c. 基于频次找到对应链表

    /**
     * 基于频次找到对应链表
     *
     * @param freq
     * @return
     */
    private MultiLinkedList findListByFreq(int freq) {
        MultiLinkedList list = headList;
        while (list.freq != freq) {
            list = list.next;
        }
        return list;
    }

暴力的遍历,做得并不好

d. 对内展示缓存中的元素总数

    /**
     * 对内展示缓存元素个数
     *
     * @return
     */
    private int getSumSize() {
        int sum = 0;
        for (MultiLinkedList list = headList; list != null; list = list.next) {
            sum += list.size;
        }
        return sum;
    }

遍历所有链表中的size进行求和

e. 数据频次自增

当数据被访问后,其频次就要自增,这是LFU的核心

    /**
     * 键值频次自增
     *
     * @param list
     * @param key
     * @param val
     */
    private void freqIncrease(MultiLinkedList list, K key, V val) {
        // 将节点放置到比原链表频次+1的新链表
        // 当list不存在前链表,说明list为头链表headList
        if (list.pre == null) {
            newHeadList();
            headList.put(key, val);
            // 记录到KEY_FREQ_MAP
            KEY_FREQ_MAP.put(key, headList.freq);
        } else {
            // 当list存在前链表,将节点在前链表上进行头插
            list.pre.put(key, val);
            // 记录到KEY_FREQ_MAP
            KEY_FREQ_MAP.put(key, list.pre.freq);
        }
    }

不要忘了让HashMap存储最新的频次

4)实例方法

a. 新增数据的put方法

逻辑较复杂,这里简单说说:

  1. 校验缓存中是否存在传入的键,若存在:
    1. 根据键获取节点所在的频次,再根据频次获取节点
    2. 频次自增,将该节点移动到其所在链表(list)的前链表(list.pre)头部
  2. 若不存在:
    1. 检验缓存是否为空,若是,新增链表
    2. 检验缓存是否满了,若是,将尾链表进行尾删
    3. 在头链表上头插新键值
    public void put(K key, V val) {
        // 若缓存中存在与传入键值相同的值
        if (KEY_FREQ_MAP.containsKey(key)) {
            // 获取当前key的频次
            int freq = KEY_FREQ_MAP.get(key);
            // 获取当前频次所对应的链表list
            MultiLinkedList list = findListByFreq(freq);
            // 在list中删去指定节点
            list.removeEntryByKey(key);
            // 键值频次自增
            freqIncrease(list, key, val);
        } else {
            // 当刚初始化,容器中尚不存在链表时
            if (listAmount == 0) {
                headList = new MultiLinkedList();
                tailList = headList;
                ++listAmount;
            }
            // 当容器满,尾删
            if (getSumSize() == capacity) {
                tailList.removeLast();
                //当尾链表为空时,删除尾链表
                if (tailList.isEmpty()) {
                    removeTailList();
                    --listAmount;
                }
            }
            // 刚被添加的数据,频次为0,从尾链表添加
            tailList.put(key, val);
            // 记录到KEY_FREQ_MAP
            KEY_FREQ_MAP.put(key, 0);
        }
    }

b. 获取数据值的get方法

逻辑:
1. 查询缓存中是否存在该key,若不存在,返回控制,若存在,执行步骤2
2. 根据键查询所在的节点,获取节点中的值
3. 将该数据频次自增,并移动到其当前链表的前链表的头部
4. 返回传入键对应的值

    /**
     * get方法
     *
     * @param key
     * @return
     */
    public V get(K key) {
        // 当<key,freq>表中不存在查询key时,返回空值
        if (!KEY_FREQ_MAP.containsKey(key)) {
            return null;
        }
        // 获取查询key的频次
        int freq = KEY_FREQ_MAP.get(key);
        // 根据频次找到数据所在链表
        MultiLinkedList list = findListByFreq(freq);
        V val = list.findEntryByKey(key).val;
        // 在原位置删除原节点
        list.removeEntryByKey(key);
        // 键值频次自增
        freqIncrease(list, key, val);
        // 返回链表中对应键的值
        return val;
    }

注意,无论是put方法还是get方法,都属于数据访问,记得要让频次自增

c. 显示缓存数据个数方法

    /**
     * 对外显示缓存元素个数
     *
     * @return
     */
    public int size() {
        return getSumSize();
    }

调用私有方法getSumSize()即可

*d. toString方法

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (MultiLinkedList cur = headList; cur != null; cur = cur.next) {
            sb.append("频次")
                    .append(cur.freq)
                    .append(":")
                    .append(cur.toString())
                    .append("\n");
        }
        return sb.toString();
    }

遍历每条链表获取其频次和其各自的toString,并换行

总结

根据大佬的大致思路实现了LFU,还是有细节没处理好,但是基本的功能已经实现了

惯例测试:

public class Test {
    public static void main(String[] args) {
        MultiLinkedListLFU<Integer, String> lfu = new MultiLinkedListLFU<>(5);
        lfu.put(1, "a");
        lfu.put(2, "b");
        lfu.put(3, "c");
        lfu.put(4, "d");
        lfu.put(5, "e");
        lfu.put(2, "y");
        System.out.println(lfu.toString());
        /**
         * output:
         * 频次1:2
         * 频次0:5->4->3->1
         */
        System.out.println(lfu.get(1)); // a
        System.out.println(lfu.toString());
        /**
         * output:
         * 频次1:1->2
         * 频次0:5->4->3
         */
        lfu.put(6, "f");
        System.out.println(lfu.toString());
        /**
         * output:
         * 频次1:1->2
         * 频次0:6->5->4
         */
        lfu.put(4, "x");
        System.out.println(lfu.toString());
        /**
         * output:
         * 频次1:4->1->2
         * 频次0:6->5
         */
        System.out.println(lfu.get(6)); // f
        /**
         * output:
         * 频次1:6->4->1->2
         * 频次0:5
         */
        System.out.println(lfu.get(4)); // x
        System.out.println(lfu.toString());
        /**
         * output:
         * 频次2:4
         * 频次1:6->1->2
         * 频次0:5
         */
        lfu.put(7, "g");
        System.out.println(lfu.toString());
        /**
         * output:
         * 频次2:4
         * 频次1:7->6->1->2
         */
    }
}

有不足之处欢迎大佬留言指教~

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。