快捷導(dǎo)航

python基于雙向鏈表實(shí)現(xiàn)LFU算法

更新時(shí)間：2022年05月25日 14:17:52 作者：旺旺小小超

這篇文章主要為大家詳細(xì)介紹了python基于雙向鏈表實(shí)現(xiàn)LFU算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

本文實(shí)例為大家分享了python實(shí)現(xiàn)LFU算法的具體代碼，供大家參考，具體內(nèi)容如下

在第一節(jié)中實(shí)現(xiàn)了雙向鏈表DoubleLinkedList類，上一節(jié)中基于雙向鏈表實(shí)現(xiàn)了LRU算法，本節(jié)課我們繼續(xù)基于雙向鏈表實(shí)現(xiàn)LFU(Least frequently used 最不經(jīng)常使用)算法。

一、重寫Node節(jié)點(diǎn)類

構(gòu)建LFUNode類繼承自第一節(jié)中的Node類，添加freq屬性用來表示節(jié)點(diǎn)使用頻率

class LFUNode(Node):

? ? def __init__(self, key, value):
? ? ? ? """
? ? ? ? LFU節(jié)點(diǎn) 增加頻率屬性
? ? ? ? :param key:
? ? ? ? :param value:
? ? ? ? """
? ? ? ? self.freq = 0
? ? ? ? super(LFUNode, self).__init__(key, value)

二、LFU實(shí)現(xiàn)

LFU的實(shí)現(xiàn)除了get和put之外還有一個(gè)私有的__update_freq更新節(jié)點(diǎn)頻率方法，讀寫某節(jié)點(diǎn)時(shí)都需要對(duì)該節(jié)點(diǎn)的頻率屬性進(jìn)行更新。除了map之外新增加一個(gè)freq_map來存儲(chǔ)每個(gè)頻率下的雙向鏈表，當(dāng)達(dá)到最大容量時(shí)移除最小頻率下的頭部的節(jié)點(diǎn)。

class LFUCache(object):

? ? def __init__(self, capacity=0xffffffff):
? ? ? ? """
? ? ? ? LFU緩存置換算法 最不經(jīng)常使用
? ? ? ? :param capacity:
? ? ? ? """
? ? ? ? self.capacity = capacity
? ? ? ? self.size = 0
? ? ? ? self.map = {}
? ? ? ? self.freq_map = {}

? ? def __update_freq(self, node):
? ? ? ? """
? ? ? ? 更新節(jié)點(diǎn)頻率
? ? ? ? :param node:
? ? ? ? :return:
? ? ? ? """
? ? ? ? freq = node.freq

? ? ? ? # 當(dāng)前節(jié)點(diǎn)所在頻率存在 在當(dāng)前頻率鏈表中移除當(dāng)前節(jié)點(diǎn)
? ? ? ? if freq in self.freq_map:
? ? ? ? ? ? node = self.freq_map[freq].remove(node)
? ? ? ? ? ? # 當(dāng)前頻率鏈表為空時(shí)刪除該頻率鏈表
? ? ? ? ? ? if self.freq_map[freq].size == 0:
? ? ? ? ? ? ? ? del self.freq_map[freq]

? ? ? ? # 將節(jié)點(diǎn)按照新頻率寫入頻率鏈表
? ? ? ? freq += 1
? ? ? ? node.freq = freq
? ? ? ? if freq not in self.freq_map:
? ? ? ? ? ? self.freq_map[freq] = DoubleLinkedList()
? ? ? ? self.freq_map[freq].append(node)

? ? ? ? return node

? ? def get(self, key):
? ? ? ? """
? ? ? ? 獲取元素
? ? ? ? :return:
? ? ? ? """
? ? ? ? # 節(jié)點(diǎn)不存在
? ? ? ? if key not in self.map:
? ? ? ? ? ? return None

? ? ? ? # 節(jié)點(diǎn)存在 更新使用頻率
? ? ? ? old_node = self.map.get(key)
? ? ? ? new_node = self.__update_freq(old_node)
? ? ? ? self.map[key] = new_node

? ? ? ? return new_node.value

? ? def put(self, key, value):
? ? ? ? """
? ? ? ? 設(shè)置元素
? ? ? ? :param key:
? ? ? ? :param value:
? ? ? ? :return:
? ? ? ? """
? ? ? ? # 節(jié)點(diǎn)已存在 更新頻率
? ? ? ? if key in self.map:
? ? ? ? ? ? old_node = self.map.get(key)
? ? ? ? ? ? old_node.value = value
? ? ? ? ? ? new_node = self.__update_freq(old_node)
? ? ? ? ? ? self.map[key] = new_node
? ? ? ? else:
? ? ? ? ? ? # 節(jié)點(diǎn)容量達(dá)到上限 移除最小頻率鏈表頭部的節(jié)點(diǎn)
? ? ? ? ? ? if self.size >= self.capacity:
? ? ? ? ? ? ? ? min_freq = min(self.freq_map)
? ? ? ? ? ? ? ? node = self.freq_map[min_freq].pop()
? ? ? ? ? ? ? ? del self.map[node.key]
? ? ? ? ? ? ? ? self.size -= 1

? ? ? ? ? ? # 構(gòu)建新的節(jié)點(diǎn) 更新頻率
? ? ? ? ? ? new_node = LFUNode(key, value)
? ? ? ? ? ? new_node = self.__update_freq(new_node)
? ? ? ? ? ? self.map[key] = new_node
? ? ? ? ? ? self.size += 1

? ? ? ? return new_node

? ? def print(self):
? ? ? ? """
? ? ? ? 打印當(dāng)前鏈表
? ? ? ? :return:
? ? ? ? """
? ? ? ? for freq, link in self.freq_map.items():
? ? ? ? ? ? print("frequencies： %d" % freq)
? ? ? ? ? ? link.print()

三、測試邏輯

if __name__ == '__main__':
? ? lfu_cache = LFUCache(4)
? ? lfu_cache.put(1, 1)
? ? lfu_cache.print()
? ? lfu_cache.put(2, 2)
? ? lfu_cache.print()
? ? print(lfu_cache.get(1))
? ? lfu_cache.print()
? ? lfu_cache.put(3, 3)
? ? lfu_cache.print()
? ? lfu_cache.put(4, 4)
? ? lfu_cache.print()
? ? lfu_cache.put(5, 5)
? ? lfu_cache.print()
? ? print(lfu_cache.get(2))
? ? lfu_cache.put(4, 400)
? ? lfu_cache.print()

測試結(jié)果: