有哪些LFU实现方式

本篇内容免费云主机、域名主要讲解“有哪些LFU实现方式”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“有哪些LFU实现方式”吧!LFU实现力扣原题描述如下：就是要求我们设计一个 LFU 算法，根据访问次数(访问频次)大小来判断应该删除哪个元素，get和put操作都会增加访问频次。当访问频次相等时，就判断哪个元素是最久未使用过的，把它删除。因此，这道题需要考虑两个方面，一个是访问频次，一个是访问时间的先后顺序。方案一：使用优先队列思路：我们可以使用JDK提供的优先队列 PriorityQueue 来实现 。因为优先队列内部维护了一个二叉堆，即可以保证每次 poll 元素的时候，都可以根据我们的要求，取出当前所有元素的最大值或是最小值。只需要我们的实体类实现 Comparable 接口就可以了。因此，我们需要定义一个 Node 来保存当前元素的访问频次 freq，全局的自增的 index，用于比较大小。然后定义一个 Map当 cache 容量不足时，根据访问频次 freq 的大小来删除最小的 freq 。若相等，则删除 index 最小的，因为index是自增的，越大说明越是最近访问过的，越小说明越是很长时间没访问过的元素。因本质是用二叉堆实现，故时间复杂度为O(logn)。方案二：使用一条双向链表思路：只用一条双向链表，来维护频次和时间先后顺序。那么，可以这样想。把频次 freq 小的放前面，频次大的放后面。如果频次相等，就从当前节点往后遍历，直到找到第一个频次比它大的元素，并插入到它前面。(当然，如果遍历到了tail，则插入到tail前面)这样可以保证同频次的元素，最近访问的总是在最后边。因此，总的来说，最低频次，并且最久未访问的元素肯定就是链表中最前面的那一个了。这样的话，当 cache容量满的时候，直接把头结点删除掉就可以了。但是，我们这里为了方便链表的插入和删除操作，用了两个哨兵节点，来表示头节点 head和尾结点tail。因此，删除头结点就相当于删除 head.next。PS：哨兵节点只是为了占位，实际并不存储有效数据，只是为了链表插入和删除时，不用再判断当前节点的位置。不然的话，若当前节点占据了头结点或尾结点的位置，还需要重新赋值头尾节点元素，较麻烦。为了便于理解新节点如何插入到链表中合适的位置，作图如下：代码如下：可以看到不管是插入元素还是删除元素时，都不需要额外的判断，这就是设置哨兵节点的好处。由于每次访问元素的时候，都需要按一定的规则把元素放置到合适的位置，因此，元素需要从前往后一直遍历。所以，时间复杂度 O(n)。方案三：用 LinkedHashSet维护频次链表思路：我们不再使用一条链表，同时维护频次和访问时间了。此处，换为用 map 键值对来维护，用频次作为键，用当前频次对应的一条具有先后访问顺序的链表来作为值。它的结构如下：由于LinkedHashSet 的 iterator迭代方法是按插入顺序的，因此迭代到的第一个元素肯定是当前频次下，最久未访问的元素。这样的话，当缓存 cache满的时候，直接删除迭代到的第一个元素就可以了。另外 freqMap，也需要在每次访问元素的时候，重新维护关系。从当前元素的频次对应的双向链表中移除当前元素，并加入到高频次的链表中。

相关推荐: 怎么写出干净的JS代码

本篇内容介绍了“怎么写出干净的JS代码”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！我们常常会用到数字，比如以下代码：谁知道这个 100 具体指的是什么？我们通…