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

2023-05-16 本文已影响0人顶级蜗牛

前言

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

一、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

前言

一、LRU的实现理论

1.队列方式实现LRU

2.链表+Hash表实现LRU

二、LRU的队列实现案例

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

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

猜你喜欢

热点阅读

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

前言

一、LRU的实现理论

1.队列方式实现LRU

2.链表+Hash表 实现LRU

二、LRU的队列实现案例

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

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

猜你喜欢

热点阅读

2.链表+Hash表实现LRU

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

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