python基於雙向連結串列實現LFU演演算法

class LFUNode(Node):

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

class LFUCache(object):

    def __init__(self, capacity=0xffffffff):
        """
        LFU快取置換演演算法 最不經常使用
        :param capacity:
        """
        self.capacity = capacity
        self.size = 0
        self.map = {}
        self.freq_map = {}

    def __update_freq(self, node):
        """
        更新節點頻率
        :param node:
        :return:
        """
        freq = node.freq

        # 當前節點所在頻率存在 在當前頻率連結串列中移除當前節點
        if freq in self.freq_map:
            node = self.freq_map[freq].remove(node)
            # 當前頻率連結串列為空時刪除該頻率連結串列
            if self.freq_map[freq].size == 0:
                del self.freq_map[freq]

        # 將節點按照新頻率寫入頻率連結串列
        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:
        """
        # 節點不存在
        if key not in self.map:
            return None

        # 節點存在 更新使用頻率
        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):
        """
        設定元素
        :param key:
        :param value:
        :return:
        """
        # 節點已存在 更新頻率
        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:
            # 節點容量達到上限 移除最小頻率連結串列頭部的節點
            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

            # 構建新的節點 更新頻率
            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):
        """
        列印當前連結串列
        :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()