A-A+

算法-LRU存储算法(OC、Python)

2020年05月22日 iOS原创文章 暂无评论
博客主机

需求场景

在这里插入图片描述

数据缓存或者持久化一般分为磁盘缓存和内存缓存,如果从读写速度上我们当然希望数据读取的书读越快越好,所以内存缓存倍受青睐,但是内存缓存由于成本限制,我们不能把全部的数据放在内存缓存里,我们该如何取舍呢?

LRU

LRU是Least Recently Used的缩写,意思是最近最少使用的数据,也就是最近使用的数据在未来的一段时间内任然被使用,已经使用很久的数据在未来的一段时间内任然不会变使用。基于这个理念我们可以在内存中保留常用的数据!

就是我们定义一个指定容量的list,每次新加的数据我们都会放在list的最上面,每次访问的数据也会被放在list的最上面,要是加入的数据超出最大容量,删除list的最好一个!

算法源码

1.OC源码

a.实现

/// 初始化
/// @param capacity 容量大小
- (instancetype)initWithCapacity:(NSUInteger)capacity{
    if(self == [super init]){
        _capacity = capacity;
    }
    return self;
}

/// 将对象存入缓存,如果 anyValue 为 nil,会删除对象
/// @param anyValue value
/// @param key key
- (void)setValue:(id)anyValue forKey:(NSString *)key{
    if(anyValue == nil){
        // 删除对象
        return;
    }
    if([self.cacheDict.allKeys containsObject:key]){
        // 当前值已经存在
        

[self.keys removeObject:key]

; }else{ // 新存入的值 if(self.keys.count == _capacity){ // 超出最大值了 删除栈里第一个 NSString *firstKey = [self.keys firstObject];

[self.keys removeObject:firstKey]

;

[self.cacheDict removeObjectForKey:firstKey]

; } }

[self.cacheDict setValue:anyValue forKey:key]

;

[self.keys addObject:key]

; } /// 取对象 /// @param key key - (id)valueForKey:(NSString *)key{ // 判断是否存在 if([self.cacheDict.allKeys containsObject:key]){

[self.keys removeObject:key]

;

[self.keys addObject:key]

; return [self.cacheDict objectForKey:key]; }else{ return nil; } } /// 删除对象 /// @param key key - (void)removeObjectForKey:(NSString *)key{ if([self.cacheDict.allKeys containsObject:key]){

[self.keys removeObject:key]

;

[self.cacheDict removeObjectForKey:key]

; }else{ /// 不存在 } } /// 获取所有的数据 /// @param block 键值对回调 - (void)enumerateKeysAndValuesUsingBlock:(void (^)(NSString *key, id obj, BOOL *stop))block{

[self.keys enumerateObjectsUsingBlock:^(NSString * _Nonnull key, NSUInteger idx, BOOL * _Nonnull stop) {
if(block){
block(key, [self.cacheDict objectForKey:key]

, stop); } }]; } /// 更新容量大小 /// @param capacity 容量大小 - (void)resetCapacity:(NSInteger)capacity{ _capacity = capacity; } - (NSMutableArray *)keys{ if(_keys == nil){ _keys = [[NSMutableArray alloc] init]; } return _keys; } - (NSMutableDictionary *)cacheDict{ if(_cacheDict == nil){ _cacheDict = [[NSMutableDictionary alloc] init]; } return _cacheDict; }复制代码

b.使用示例

- (void)viewDidLoad {
    

[super viewDidLoad]

; // Do any additional setup after loading the view. for (int i = 1; i<=5; i++) { NSString *key = [NSString stringWithFormat:@"%d",i]; NSString *value = [NSString stringWithFormat:@"%d",i * 100];

[self.lruCacheMap setValue:value forKey:key]

; }

[self.lruCacheMap enumerateKeysAndValuesUsingBlock:^(NSString *key, id obj, BOOL *stop) {
NSLog(@"key, value == %@, %@",key, obj);
}]

; NSLog(@"------------");

[self.lruCacheMap setValue:@"600" forKey:@"6"]

;

[self.lruCacheMap enumerateKeysAndValuesUsingBlock:^(NSString *key, id obj, BOOL *stop) {
NSLog(@"key, value == %@, %@",key, obj);
}]

; NSLog(@"------------"); NSLog(@"%@", [self.lruCacheMap valueForKey:@"5"]);

[self.lruCacheMap enumerateKeysAndValuesUsingBlock:^(NSString *key, id obj, BOOL *stop) {
NSLog(@"key, value == %@, %@",key, obj);
}]

; NSLog(@"------------"); NSLog(@"%@", [self.lruCacheMap valueForKey:@"4"]);

[self.lruCacheMap enumerateKeysAndValuesUsingBlock:^(NSString *key, id obj, BOOL *stop) {
NSLog(@"key, value == %@, %@",key, obj);
}]

; } - (LRUCacheMap *)lruCacheMap{ if(_lruCacheMap == nil){ _lruCacheMap = [[LRUCacheMap alloc] initWithCapacity:5]; } return _lruCacheMap; }复制代码

c.运行结果

2020-05-22 14:47:01.414530+0800 LRUDemo[65621:2173464] key, value == 1, 100
2020-05-22 14:47:01.414716+0800 LRUDemo[65621:2173464] key, value == 2, 200
2020-05-22 14:47:01.414809+0800 LRUDemo[65621:2173464] key, value == 3, 300
2020-05-22 14:47:01.414905+0800 LRUDemo[65621:2173464] key, value == 4, 400
2020-05-22 14:47:01.414995+0800 LRUDemo[65621:2173464] key, value == 5, 500
2020-05-22 14:47:01.415076+0800 LRUDemo[65621:2173464] ------------
2020-05-22 14:47:01.415169+0800 LRUDemo[65621:2173464] key, value == 2, 200
2020-05-22 14:47:01.415272+0800 LRUDemo[65621:2173464] key, value == 3, 300
2020-05-22 14:47:01.415519+0800 LRUDemo[65621:2173464] key, value == 4, 400
2020-05-22 14:47:01.415698+0800 LRUDemo[65621:2173464] key, value == 5, 500
2020-05-22 14:47:01.416035+0800 LRUDemo[65621:2173464] key, value == 6, 600
2020-05-22 14:47:01.416124+0800 LRUDemo[65621:2173464] ------------
2020-05-22 14:47:01.416314+0800 LRUDemo[65621:2173464] 500
2020-05-22 14:47:01.416453+0800 LRUDemo[65621:2173464] key, value == 2, 200
2020-05-22 14:47:01.416681+0800 LRUDemo[65621:2173464] key, value == 3, 300
2020-05-22 14:47:01.416763+0800 LRUDemo[65621:2173464] key, value == 4, 400
2020-05-22 14:47:01.852132+0800 LRUDemo[65621:2173464] key, value == 6, 600
2020-05-22 14:47:01.852262+0800 LRUDemo[65621:2173464] key, value == 5, 500
2020-05-22 14:47:01.852345+0800 LRUDemo[65621:2173464] ------------
2020-05-22 14:47:01.852431+0800 LRUDemo[65621:2173464] 400
2020-05-22 14:47:01.852507+0800 LRUDemo[65621:2173464] key, value == 2, 200
2020-05-22 14:47:01.852596+0800 LRUDemo[65621:2173464] key, value == 3, 300
2020-05-22 14:47:01.852668+0800 LRUDemo[65621:2173464] key, value == 6, 600
2020-05-22 14:47:01.852760+0800 LRUDemo[65621:2173464] key, value == 5, 500
2020-05-22 14:47:01.852835+0800 LRUDemo[65621:2173464] key, value == 4, 400
Message from debugger: Terminated due to signal 15

Python源码

a.源码实现

from collections import OrderedDict

class LRUCacheMap(object):
    def __init__(self, size):
        super(LRUCacheMap, self).__init__()
        # 总的容量大小
        self.total_capcity = size
        # 所有的键值对
        self.cache_map = OrderedDict()

    # 添加新值
    def set_value(self, key, value):
        if key in self.cache_map.keys():
            # 当前值已经存在
            value = self.cache_map.pop(key)
            self.cache_map[key] = value
        else:
            # 新存入的值
            if len(self.cache_map) == self.total_capcity:
                # 超出最大值了 删除栈里第一个
                self.cache_map.popitem(last = False)
            else:
                pass

            # 添加新的值
            self.cache_map[key] = value

    def get_value(self, key):
        # 判断是否存在
        if key in self.cache_map.keys():
            value = self.cache_map.pop(key)
            self.cache_map[key] = value
        else:
            value = None

        return value

if __name__ == '__main__':
    cache_map = LRUCacheMap(5)
    for index in range(1, 6):
        cache_map.set_value(str(index), index * 100)

    print(cache_map.cache_map)
    print('-' * 100 + '
')

    cache_map.set_value('6', 600)

    print(cache_map.cache_map)
    print('-' * 100 + '
')

    print(cache_map.get_value('5'))
    print(cache_map.cache_map)
    print('-' * 100 + '
')

    print(cache_map.get_value('4'))
    print(cache_map.cache_map)
    print('-' * 100 + '
')

b.运行结果

OrderedDict([('1', 100), ('2', 200), ('3', 300), ('4', 400), ('5', 500)])
-------------------------------------------------------------------------

OrderedDict([('2', 200), ('3', 300), ('4', 400), ('5', 500), ('6', 600)])
-------------------------------------------------------------------------

500
OrderedDict([('2', 200), ('3', 300), ('4', 400), ('6', 600), ('5', 500)])
-------------------------------------------------------------------------
400
OrderedDict([('2', 200), ('3', 300), ('6', 600), ('5', 500), ('4', 400)])
-------------------------------------------------------------------------

[Finished in 0.0s]

给我留言

Copyright © ios教程,苹果粉丝,苹果资讯,ios入门教程,ios学习,ios程序员,ios视频教程,ios粉丝网 保留所有权利.   Theme  Ality

用户登录