美文网首页
数据结构与算法(五)：LRU

数据结构与算法(五)：LRU

作者: 顶级蜗牛 | 来源:发表于2023-05-16 09:53 被阅读0次

    相关文献：
    数据结构与算法(一)：基础理论
    数据结构与算法(二)：线性表的实现
    数据结构与算法(三)：线性表算法设计练习
    数据结构与算法(四)：斐波那契数列
    数据结构与算法(五)：LRU
    数据结构与算法(六)：栈
    数据结构与算法(七)：栈/队列的算法解题思想
    数据结构与算法(八)：队列
    数据结构与算法(九)：二叉树/线索化二叉树
    数据结构与算法(十)：哈夫曼树

    前言

    在应用程序中往往使用到缓存，而缓存它是有一个容量限制的，当我们需要把数据缓存的时候，这个容量满了，我们需要设计一个算法去告诉应用程序应该移除哪些旧的缓存数据。

    一、LRU的实现理论

    • LRU(最近最少使⽤)：是⼀种缓存淘汰算法。顾名思义，最⻓时间没有被使⽤的元素会被从缓存中淘汰。
    1.队列方式实现LRU

    先进来的元素先被优先淘汰，这样的特性像极了队列。于是就可以分析：

    • Queue（队列）：此队列将具有特定容量，因为缓存的
      ⼤⼩有限。当引⼊⼀个新元素时，它就会被添加到队列
      的尾部。需要淘汰的元素放在队列的头部；先进先出；
    • 时间复杂度是：O(n)
    • 空间复杂度是：O(n)
    • 每⼀项存储的是key-value，通过key取value时，需
      要遍历。
    通过队列来实现LRU机制

    而缓存里的元素被再次使用的话，就又会把这个元素移动到队列的尾部，这种情况无疑时间复杂度是O(n)。
    如何减⼩缓存命中的时间复杂度减⼩到O(1)？

    2.链表+Hash表 实现LRU
    • 通过链表与Hash表：
      Hash表⽤来存储key-value，减⼩缓存命中时间；
      链表负责管理缓存元素的顺序。
    链表与Hash表来实现LRU机制

    为什么要用双链表？
    单向链表：删除节点需要访问前驱节点，O(n)
    双向链表：结点有前驱指针，删除/移动节点都是纯指针变动，O(1)

    使用链表+Hash表方式的话，虽然时间复杂度降低了，但是空间复杂度上来了。
    那么就会引发一个选型的问题。如果我的数据量足够多的话，程序会更在意查找速度，更适用于方式2；如果我得数据量较少查找起来很快，更使用于方式1。

    二、LRU的队列实现案例

    我们平常使用颜色UIColor是可以通过字符串、rgb数值等等解析而来。我们常常会重复地使用一个颜色，但是那玩意儿之前就已经解析过了，没必要重复解析吧，所以我们可以设计一个算法去缓存它。
    比如开源框架SYColor

    开源框架SYColor

    像这样的解析颜色缓存数据量较少查找起来很快，更使用于方式1去实现LRU。

    那我们来设计一个简单的缓存类TinyLRUCache:

    通过队列来实现LRU机制 
    //
//  TinyLRUCache.h
//

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

// key<TinyLRUCachePolicy> -> createValue -> value
// 用来创建value的
@protocol TinyLRUCachePolicy <NSObject>

- (id)createValue;

@end

@interface TinyLRUCache<__covariant KeyType, __covariant ObjectType> : NSObject
- (instancetype)initWithCapacity:(NSUInteger)numItems;
// 1. key 存在 -》
// 1. key不存在
- (nullable ObjectType)objectForKey:(KeyType<TinyLRUCachePolicy>)aKey;
@end

NS_ASSUME_NONNULL_END

    //
//  TinyLRUCache.m
//

#import "TinyLRUCache.h"

// Array <key-value>
// key存在的时候，更新key

// Entry是缓存里的一个数据对象
@interface Entry : NSObject 

@property (strong, nonatomic) id key; // key
@property (strong, nonatomic) id object; // value

+ (instancetype)entryWithObject:(id)object forKey:(id)key;

@end

@implementation Entry
+ (instancetype)entryWithObject:(id)object forKey:(id)key {
    Entry *entry = [self new];
    entry.key = key;
    entry.object = object;
    return entry;
}
@end

// TinyLRUCache是缓存类
@interface TinyLRUCache() {
    NSUInteger _numItems;
    NSMutableArray <Entry *>*_cache; // 使用数组 
}
@end

@implementation TinyLRUCache
// 初始化限定缓存的数量
- (instancetype)initWithCapacity:(NSUInteger)numItems {
    self = [super init];
    if (self) {
        _numItems = numItems;
        // malloc
        _cache = [NSMutableArray arrayWithCapacity:numItems];
    }
    return self;
}

/**
  通过key找value
 1. removeNode
 1. moveNodeToHead
 2. removeTailNode
 3. addNodeToHead
 */
- (nullable id)objectForKey:(id<TinyLRUCachePolicy>)aKey {
    
    for (size_t i = 0; i < _cache.count; i++) {
        // key没有命中
        if (_cache[i].key != aKey) {
            continue;
        }
        // key命中_cache
        if (i == _cache.count - 1) {
            return _cache[i].object;
        }
        
        // key命中,不是_cache的末尾
        Entry *entry = _cache[i];
        [_cache removeObjectAtIndex:i];
        [_cache addObject:entry];
        return _cache[_cache.count - 1].object;
    }
    // 最近最少使用
    if (_cache.count == _numItems) {
        [_cache removeObjectAtIndex:0];
    }
    
    if ([aKey respondsToSelector:@selector(createValue)]) {
        [_cache addObject:[Entry entryWithObject:[aKey createValue] forKey:aKey]];
    }
    
    return _cache.lastObject.object;
}

- (NSString *)description {
    if (_cache.count == 0) {
        return @"<empty cache>";
    }
    NSMutableString *all = [NSMutableString stringWithString:@"\n|------------TinyLRUCache----------|\n"];

    [_cache enumerateObjectsUsingBlock:^(Entry * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        [all appendString:[NSString stringWithFormat:@"|-%lu-|--key:--%@--value:--%@--|\n",(unsigned long) (unsigned long)idx, obj.key, obj.object]];
    }];
    return all;
}
@end

    使用TinyLRUCache:

    //
//  ViewController.m
//

#import "ViewController.h"
#import "TinyLRUCache.h"

@implementation NSString(TinyLRUCachePolicy)

- (NSString *)createValue {
    return [NSString stringWithFormat:@"%@_Cat1237", self];
}

@end

@interface ViewController ()

@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    TinyLRUCache <NSString *, NSString *>*cache = [[TinyLRUCache alloc] initWithCapacity:5];
    NSLog(@"%@", [cache objectForKey:@"1"]);
    NSLog(@"%@", [cache objectForKey:@"2"]);
    NSLog(@"%@", [cache objectForKey:@"3"]);
    NSLog(@"%@", [cache objectForKey:@"4"]);
    NSLog(@"%@", [cache objectForKey:@"5"]);
    NSLog(@"%@", [cache objectForKey:@"2"]);

    NSLog(@"%@", cache);
    
}
@end

    三、LRU的Hash表+链表 实现案例(链表无头结点)

    • 最近最多使用的存储在头
    • 最近最少使用的存储在尾
    • 使用_head头指针指向首元结点
    • 使用_tail尾指针指向尾结点
    • 不需要初始化虚拟头结点_head/尾结点_tail

    创建一个LRUCache缓存类

    //
//  LRUCache.h
//

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN
@protocol TinyLRUCachePolicy <NSObject>

- (id)createValue;

@end

@interface LRUCache<__covariant KeyType, __covariant ObjectType> : NSObject
- (instancetype)initWithCapacity:(NSUInteger)numItems;

- (nullable ObjectType)objectForKey:(KeyType<TinyLRUCachePolicy>)aKey;

@end

NS_ASSUME_NONNULL_END

    //
//  LRUCache.m
//

#import "LRUCache.h"

// 定义一个双向链表节点 _DoubleLinkNode
@interface _DoubleLinkNode : NSObject {
    @package
    __weak _DoubleLinkNode *_prev; // 前驱
    __weak _DoubleLinkNode *_next; // 后继
    // 数据域
    id _key;
    id _value;
}
@end
@implementation _DoubleLinkNode
@end


@interface _DoubleLink : NSObject
@end

@interface _DoubleLink() {
    @package
    NSMutableDictionary *_dic; // hash表
    NSUInteger _count; // 已有节点个数
    NSUInteger _capacity; // 节点最大数量
    // 双向链表
    // 无虚拟头结点 - 不需要初始化
    _DoubleLinkNode *_head; // 头节点
    _DoubleLinkNode *_tail; // 尾结点
}
- (void)addNodeToHead:(_DoubleLinkNode *)node;

- (void)moveNodeToHead:(_DoubleLinkNode *)node;

- (void)removeNode:(_DoubleLinkNode *)node;

- (_DoubleLinkNode *)removeTailNode;
@end

@implementation _DoubleLink
- (instancetype)initWithCapacity:(NSUInteger)numItems {
    self = [super init];
    if (self) {
        _capacity = numItems;
        // 初始化哈希表
        _dic = [NSMutableDictionary dictionaryWithCapacity:numItems];
    }
    return self;
}

// 添加节点到头部
- (void)addNodeToHead:(_DoubleLinkNode *)node {
    _dic[node->_key] = node; // 将节点保存到hash表
    _count++;
    if (_head) {
        // 头插
        node->_next = _head;
        _head->_prev = node;
        _head = node;
    } else {
        // 说明双向链表还没有元素
        // 头结点/尾结点都是第一个元素
        _head = _tail = node;
    }
}

// 节点移动到头部
- (void)moveNodeToHead:(_DoubleLinkNode *)node {
    if (_head == node) return; // 如果移动的是头节点，则不需要移动
    
    if (_tail == node) { // 如果被移动的节点是尾结点
        _tail = node->_prev;
        _tail->_next = nil;
    } else { // 被移动节点是中间节点
        node->_next->_prev = node->_prev;
        node->_prev->_next = node->_next;
    }
    node->_next = _head;
    node->_prev = nil;
    _head->_prev = node;
    _head = node;
}

// 移除节点
- (void)removeNode:(_DoubleLinkNode *)node {
    [_dic removeObjectForKey:node->_key]; // 从hash表中移除数据
    _count--;
    // 节点移除
    if (node->_next) node->_next->_prev = node->_prev;
    if (node->_prev) node->_prev->_next = node->_next;
    if (_head == node) _head = node->_next; // 移除的是头部
    if (_tail == node) _tail = node->_prev; // 移除的是尾部
}

// 移除尾结点
- (_DoubleLinkNode *)removeTailNode {
    if (!_tail) return nil;
    _DoubleLinkNode *tail = _tail; // 先保存，后面需要返回出去
    [_dic removeObjectForKey:_tail->_key]; // 从hash表中移除数据
    _count--;
    if (_head == _tail) {
        _head = _tail = nil;
    } else {
        _tail = _tail->_prev;
        _tail->_next = nil;
    }
    return tail;
}

@end

@interface LRUCache() {
    _DoubleLink *_lru; // hash表+双向链表
    NSUInteger _numItems; // 缓存个数
}

@end

@implementation LRUCache

- (instancetype)initWithCapacity:(NSUInteger)numItems {
    self = [super init];
    if (self) {
        _numItems = numItems;
        _lru = [[_DoubleLink alloc] initWithCapacity:numItems];
    }
    return self;
}

- (nullable id)objectForKey:(id<TinyLRUCachePolicy>)aKey {
    _DoubleLinkNode *node = _lru->_dic[aKey];
    // value如何产生你自己说了算，这里只做演示
    id value = nil;
    if ([aKey respondsToSelector:@selector(createValue)]) {
        value = [aKey createValue];
    }
    if (node) {
        // 把节点移动到头部
        node->_value = value;
        [_lru moveNodeToHead:node];
    } else {
        // 超出限制，删除双向链表的尾部节点
        if (_lru->_count == _numItems) {
            [_lru removeTailNode];
        }
        node = [_DoubleLinkNode new];
        node->_key = aKey;
        node->_value = value;
        [_lru addNodeToHead:node];
    }
    return node;
}

- (NSString *)description {
    if (_numItems == 0) {
        return @"<empty cache>";
    }
    NSMutableString *all = [NSMutableString stringWithString:@"\n|------------LRUCache----------|\n"];

    _DoubleLinkNode *node = _lru->_head;
    int index = 0;
    while (node && node->_key) {
        [all appendString:[NSString stringWithFormat:@"|-%d-|--key:--%@--value:--%@--|\n",index, node->_key, node->_value]];
        node = node->_next;
        index++;
    }
    return all;
}
@end


    //
// main.m
//
#import <Foundation/Foundation.h>
#import "LRUCache.h"

@implementation NSString(TinyLRUCachePolicy)
- (NSString *)createValue {
    return [NSString stringWithFormat:@"%@_Cat1237", self];
}
@end

int main(int argc, const char * argv[]) {
    LRUCache <NSString *, NSString *>*cache = [[LRUCache alloc] initWithCapacity:5];
    [cache objectForKey:@"1"];
    [cache objectForKey:@"2"];
    [cache objectForKey:@"3"];
    [cache objectForKey:@"4"];
    [cache objectForKey:@"5"];
    [cache objectForKey:@"2"];
//    [cache objectForKey:@"1"];

    NSLog(@"%@", cache);
    return 0;
}

    四、LRU的Hash表+链表 实现案例(链表有头结点)

    • 最近最多使用的存储在头
    • 最近最少使用的存储在尾
    • 使用_head头指针指向头结点
    • 使用_tail尾指针指向尾结点
    • 初始化虚拟头结点_head/尾结点_tail

    创建一个LRUCache缓存类

    //
//  LRUCache.h
//

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN
@protocol TinyLRUCachePolicy <NSObject>

- (id)createValue;

@end

@interface LRUCache<__covariant KeyType, __covariant ObjectType> : NSObject
- (instancetype)initWithCapacity:(NSUInteger)numItems;

- (nullable ObjectType)objectForKey:(KeyType<TinyLRUCachePolicy>)aKey;

@end

NS_ASSUME_NONNULL_END


    //
//  LRUCache.m
//

#import "LRUCache.h"

@interface _DoubleLinkNode : NSObject
{
    @package
    _DoubleLinkNode *_prev;
    _DoubleLinkNode *_next;
    id _key;
    id _value;
}
@end


@implementation _DoubleLinkNode

@end

@interface _DoubleLink : NSObject

@end

@interface _DoubleLink() {
    @package
    NSMutableDictionary *_dic; // hash表
    NSUInteger _count; // 缓存节点个数
    NSUInteger _capacity; // 最大缓存个数
    // 双向链表
    _DoubleLinkNode *_head; // 头结点-有虚拟头结点
    _DoubleLinkNode *_tail; // 尾结点-有虚拟尾结点
}
- (void)addNodeToHead:(_DoubleLinkNode *)node;

- (void)moveNodeToHead:(_DoubleLinkNode *)node;

- (void)removeNode:(_DoubleLinkNode *)node;

- (_DoubleLinkNode *)removeTailNode;

@end

@implementation _DoubleLink
- (instancetype)initWithCapacity:(NSUInteger)numItems {
    self = [super init];
    if (self) {
        _capacity = numItems;
        _dic = [NSMutableDictionary dictionaryWithCapacity:numItems];
        // 虚拟头部和虚拟尾部节点
        _head = [_DoubleLinkNode new];
        _tail = [_DoubleLinkNode new];
        // 双向链表
        _head->_next = _tail;
        _tail->_prev = _head;
    }
    return self;
}

// 添加节点到首元节点处
- (void)addNodeToHead:(_DoubleLinkNode *)node {
    _dic[node->_key] = node; // 节点元素添加到hash表
    _count++;
    node->_prev = _head;
    node->_next = _head->_next;
    node->_next->_prev = node;
    _head->_next = node;
}

// 节点移动到首元结点处
- (void)moveNodeToHead:(_DoubleLinkNode *)node {
    // 先移除后添加
    [self removeNode:node];
    [self addNodeToHead:node];
}

// 移除节点
- (void)removeNode:(_DoubleLinkNode *)node {
    [_dic removeObjectForKey:node->_key]; // 节点元素从hash表上移除
    _count--;
    node->_prev->_next = node->_next;
    node->_next->_prev = node->_prev;
}

// 移除最后一个节点元素
- (_DoubleLinkNode *)removeTailNode {
    _DoubleLinkNode *node = _tail->_prev;
    [self removeNode:node];
    return node;
}

@end

@interface LRUCache() {
    _DoubleLink *_lru; // hash表+双向链表
    NSUInteger _numItems; // 最大缓存数
}

@end

@implementation LRUCache

- (instancetype)initWithCapacity:(NSUInteger)numItems {
    self = [super init];
    if (self) {
        _numItems = numItems;
        _lru = [[_DoubleLink alloc] initWithCapacity:numItems];
    }
    return self;
}

- (nullable id)objectForKey:(id<TinyLRUCachePolicy>)aKey {
    _DoubleLinkNode *node = _lru->_dic[aKey];
    // value怎么创建的自己定，这里只做演示
    id value = nil;
    if ([aKey respondsToSelector:@selector(createValue)]) {
        value = [aKey createValue];
    }
    if (node) {
        // 如果缓存中存在节点 - 更新数据，并移动到链表首元节点处
        node->_value = value;
        [_lru moveNodeToHead:node];
    } else {
        // 超出限制，删除双向链表的尾部节点
        if (_lru->_count == _numItems) {
            [_lru removeTailNode];
        }
        node = [_DoubleLinkNode new];
        node->_key = aKey;
        node->_value = value;
        [_lru addNodeToHead:node];
    }
    return node;
}

- (NSString *)description {
    if (_numItems == 0) {
        return @"<empty cache>";
    }
    NSMutableString *all = [NSMutableString stringWithString:@"\n|------------LRUCache----------|\n"];

    _DoubleLinkNode *node = _lru->_head->_next;
    int index = 0;
    while (node && node->_key) {
        [all appendString:[NSString stringWithFormat:@"|-%d-|--key:--%@--value:--%@--|\n",index, node->_key, node->_value]];
        node = node->_next;
        index++;
    }
    return all;
}
@end


    //
//  main.m
//

#import <Foundation/Foundation.h>
#import "LRUCache.h"


@implementation NSString(TinyLRUCachePolicy)

- (NSString *)createValue {
    return [NSString stringWithFormat:@"%@_Cat1237", self];
}

@end

int main(int argc, const char * argv[]) {
    LRUCache <NSString *, NSString *>*cache = [[LRUCache alloc] initWithCapacity:5];
    [cache objectForKey:@"1"];
    [cache objectForKey:@"2"];
    [cache objectForKey:@"3"];
    [cache objectForKey:@"4"];
    [cache objectForKey:@"5"];
    [cache objectForKey:@"2"];
    [cache objectForKey:@"1"];

    NSLog(@"%@", cache);
    return 0;
}

    相关文章

      网友评论

          本文标题：数据结构与算法(五)：LRU

          本文链接：https://www.haomeiwen.com/subject/ytnxsdtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|数据结构与算法(五)：LRU|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！