欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

python实现LRU算法

程序员文章站 2022-09-16 20:50:50
LRU算法python实现​学习mysql数据库时,了解了一下ib_buffer_pool的存储机制,使用LRU算法施行将少用的数据淘汰,保存使用更频繁的数据。​再基于3.6版本python的字典数据类型改变,想试试新字典默认有序的话能否直接使用于LRU算法。​from collections import OrderedDictclass Lrulru_dict(): def __init__(self, capacity): # 传入缓存容量 sel...

LRU算法python实现

​ 学习mysql数据库时,了解了一下ib_buffer_pool的存储机制,使用LRU算法施行将少用的数据淘汰,保存使用更频繁的数据。

​ 再基于3.6版本python的字典数据类型改变,想试试新字典默认有序的话能否直接使用于LRU算法。

from collections import OrderedDict
class Lrulru_dict():
    def __init__(self, capacity):
        # 传入缓存容量
        self.capacity = capacity
        # 新建字典
        self.lru_dict = {}

    # 定义查询数据的函数
    def get(self, key):
        # 当key不在字典中时
        if key not in self.lru_dict:
            return None
        else:
            # 把数据先删再赋值,使其添加到entries数组末尾
            self.lru_dict[key] = self.lru_dict.pop(key)

    # 定义添加数据的函数
    def set(self, key, value):
        # 当key在字典中时重复上述操作
        if key in self.lru_dict:
            # 删掉老数据
            self.lru_dict.pop(key)
            # 存入新值
            self.lru_dict[key] = value
        else:
            # 当缓存满了的时候
            if len(self.lru_dict) == self.capacity:
                #  这里如果继续使用字典结构dict.popitem实行的是末尾淘汰,不能申明last字段
                #   只能调用OrderedDict强转再操作
                self.lru_dict = OrderedDict(self.lru_dict)
                self.lru_dict.popitem(last=False)
                #  添加新值
            self.lru_dict[key] = value


c = Lrulru_dict(5)

for i in range(5, 10):
    c.set(i, 10 * i)

print(c.lru_dict, c.lru_dict.keys())

c.get(5)
c.get(7)

print(c.lru_dict, c.lru_dict.keys())

c.set(10, 100)
print(c.lru_dict, c.lru_dict.keys())

c.set(9, 44)
print(c.lru_dict, c.lru_dict.keys())

>>> {5: 50, 6: 60, 7: 70, 8: 80, 9: 90} dict_keys([5, 6, 7, 8, 9])
>>> {6: 60, 8: 80, 9: 90, 5: 50, 7: 70} dict_keys([6, 8, 9, 5, 7])
>>> OrderedDict([(8, 80), (9, 90), (5, 50), (7, 70), (10, 100)]) odict_keys([8, 9, 5, 7, 10])
>>> OrderedDict([(8, 80), (5, 50), (7, 70), (10, 100), (9, 44)]) odict_keys([8, 5, 7, 10, 9])

所以仍需使用OrderDict对象才能指定剔除使用最少的数组头部数据。

本文地址:https://blog.csdn.net/Asaue/article/details/107528142