美文网首页
数据淘汰算法LRU简单实现

数据淘汰算法LRU简单实现

作者: jayhe | 来源:发表于2020-05-08 08:19 被阅读0次

LRU

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法；在我们iOS的内存管理里也广泛使用，一些三方库以及系统的NSCache等都有采用这种算法来淘汰那些古老的很久没有被使用的数据

我们要实现这个规则，那么思路就是能够将数据按照使用的顺序来排列起来，当需要淘汰数据的时候就去淘汰这个排列的后面的数据[这里假设我们将最近使用的数据排在前面，你也可以排在后面]

使用数组数据结构实现

  • 插入数据，将数据记录在数组的头部（数据已存在就移动到头部）
  • 读取数据，将数据移动到数组的头部
  • 删除数据，将数据从数组和数据源中移除
  • 数据超过阀值，从数组的尾部逐一删除数据同时数据源删除数据
  • 数组排序+字典存数据

实现代码
这里使用设置个数的方式来淘汰数据，常用的可以用设置大小或者二者都有的方式

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface LRUByArray : NSObject

@property (nonatomic, assign) NSInteger limitCount;
@property (nonatomic, readonly, strong) NSArray *allItems;

- (void)addObject:(id)obj forKey:(NSString *)key;
- (void)removeObjectByKey:(NSString *)key;
- (id)queryObjectByKey:(NSString *)key;

@end

NS_ASSUME_NONNULL_END

#import "LRUByArray.h"

@interface LRUByArray ()

@property (nonatomic, strong) NSLock *lock;
@property (nonatomic, strong) NSMutableArray *objects; // 用来排序
@property (nonatomic, strong) NSMutableDictionary *map; // 用来存储数据

@end

@implementation LRUByArray

- (instancetype)init {
    self = [super init];
    if (self) {
        _limitCount = 4;
        _lock = [NSLock new];
    }
    
    return self;
}

- (void)addObject:(id)obj forKey:(nonnull NSString *)key {
    if (key == nil) {
        return;
    }
    
    if (obj == nil) {
        [self.lock lock];
        [self.objects removeObject:key];
        [self.map removeObjectForKey:key];
        [self.lock unlock];
        return;
    }
    
    [self.lock lock];
    // 插入数据
    id tmpObj = [self.map objectForKey:key];
    if (tmpObj) {
        [self.objects removeObject:key];
    }
    [self.map setObject:obj forKey:key];
    [self.objects insertObject:key atIndex:0];
    // 判断是否超过限制
    if (self.map.count > self.limitCount) {
        // remove
        while (self.objects.count > self.limitCount) {
            id lastKey = self.objects.lastObject;
            [self.objects removeLastObject];
            [self.map removeObjectForKey:lastKey];
        }
    }
    [self.lock unlock];
}

- (void)removeObjectByKey:(NSString *)key {
    [self.lock lock];
    id obj = [self.map objectForKey:key];
    if (obj) {
        [self.map removeObjectForKey:key];
        [self.objects removeObject:key];
    }
    [self.lock unlock];
}

- (id)queryObjectByKey:(NSString *)key {
    [self.lock lock];
    id obj = [self.map objectForKey:key];
    if (obj) {
        [self.objects removeObject:key];
        [self.objects insertObject:key atIndex:0];
    }
    [self.lock unlock];
    return obj;
}

#pragma mark - Getter && Setter

- (NSMutableDictionary *)map {
    if (_map == nil) {
        _map = [NSMutableDictionary dictionary];
    }
    
    return _map;
}

- (NSMutableArray *)objects {
    if (_objects == nil) {
        _objects = [NSMutableArray arrayWithCapacity:0];
    }
    
    return _objects;
}

- (NSArray *)allItems {
    NSMutableArray *tmpArray = [NSMutableArray arrayWithCapacity:0];
    [_objects enumerateObjectsUsingBlock:^(NSString * _Nonnull key, NSUInteger idx, BOOL * _Nonnull stop) {
        id obj = [self.map objectForKey:key];
        if (obj) {
            [tmpArray addObject:[self.map objectForKey:key]];
        }
    }];
    return tmpArray.copy;
}

@end
  • _objects是用来做排序的，在数据的插入、删除、读取操作的时候会同步更新这个数组，数组存放的是数据对应的key的值，你也可以包装一下存储包含key、value等其他属性的对象，这里只是演示就没有设计的很完善
  • _maps用来存储数据源
  • 实现也比较简单，按照开头介绍的规则去实现基本就没问题了，详细可以看代码

测试用例

- (void)testLRU {
    LRUByArray *lru = [LRUByArray new];
    lru.limitCount = 4;
    for (NSInteger i = 0; i < 8; i ++) {
        [lru addObject:@(i) forKey:@(i * 100).stringValue];
    }
    NSLog(@"all items = %@", lru.allItems);
    /*
    输出：
     all items = (
         7,
         6,
         5,
         4
     )
     */
    [lru queryObjectByKey:@"400"];
    NSLog(@"all items = %@", lru.allItems);
    /*
    输出：
     all items = (
         4,
         7,
         6,
         5
     )
     */
}

可以看到LRU已经实现了，当数据超过阀值会从数组的尾部开始删除数据知道满足限制条件；新插入或者读取的数据都会被放到数据的头部，这样就保证了从尾部开始淘汰数据，淘汰的就是最久未使用的数据了

使用链表的数据结构实现

你可能会说数组的方式不优雅，性能比不上链表的方式；而且一些开源的库，比如YYMemoryCache、Swift版本的NSCache的实现就采用了双向链表的方式来实现LRU的

  • 插入数据，将数据设置为链表的头（数据已存在就移动到头部）
  • 读取数据，将数据移动到链表的头部
  • 删除数据，将数据从链表和数据源中移除
  • 数据超过阀值，从链表的尾部逐一删除数据同时数据源删除数据
  • 双向链表排序+字典存数据

实现代码

NS_ASSUME_NONNULL_BEGIN

@protocol LRUByLinkedListDelegate;

@interface LRUByLinkedList : NSObject

@property (nonatomic, assign) NSInteger limitCount;
@property (nonatomic, readonly, strong) NSArray *allItems;
@property (nonatomic, weak) id<LRUByLinkedListDelegate> delegate;

- (void)addObject:(id)obj forKey:(NSString *)key;
- (void)removeObjectByKey:(NSString *)key;
- (id)queryObjectByKey:(NSString *)key;

@end

@protocol LRUByLinkedListDelegate <NSObject>

- (void)willRemoveObject:(id)object;
- (void)didRemoveObject:(id)object;

@end

NS_ASSUME_NONNULL_END

#import "LRUByLinkedList.h"

@interface HCLinkedNode : NSObject {
    @package
    __unsafe_unretained HCLinkedNode *_pre;
    __unsafe_unretained HCLinkedNode *_next;
    NSString *_key;
    id _value;
}

@end

@implementation HCLinkedNode

@end

@interface HCLinkedList : NSObject {
    @package
    NSMutableDictionary *_map;
    HCLinkedNode *_head;
    HCLinkedNode *_tail;
    NSInteger _costCount;
}

- (void)insertNodeAtHead:(HCLinkedNode *)node;

- (void)bringNodeToHead:(HCLinkedNode *)node;

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

- (HCLinkedNode *)removeTailNode;

- (void)removeAll;

@end

@implementation HCLinkedList

- (instancetype)init {
    self = [super init];
    if (self) {
        _map = [NSMutableDictionary dictionary];
        _costCount = 0;
    }
    
    return self;
}
// [pre][ Node ][next]
- (void)insertNodeAtHead:(HCLinkedNode *)node {
    if (node == nil) {
        return;
    }
    [_map setValue:node forKey:node->_key];
    _costCount++;
    if (_head) { // 头节点存在
        node->_next = _head; // 将插入的节点的后缀节点指向头节点
        _head->_pre = node; // 将头节点的前缀节点指向node
        _head = node; // 设置头节点为插入的新的节点
    } else { // 节点不存在，链表为空的时候
        _head = _tail = node; // 将头尾都设置为首个节点
    }
}

- (void)bringNodeToHead:(HCLinkedNode *)node {
    if (node == nil) {
        return;
    }
    if (_head == node) { // 元素本来就在头部
        return;
    }
    if (_tail == node) { // 元素在尾部
        _tail = node->_pre; // 将尾部设置为node的头
        _tail->_next = nil; // 将尾部的后缀节点设置空
    } else { // 元素在中间位置
        node->_next->_pre = node->_pre; // 将node的后缀节点的前缀设置为node的前节点
        node->_pre->_next = node->_next; // 将node的前缀节点的后缀设置为node的后节点
    }
    node->_next = _head; // 将node的后缀节点设置为之前的头
    node->_pre = nil;
    _head->_pre = node; // 将之前的头节点的前缀设置为node
    _head = node; // 将头设置为首个节点
}

- (void)removeNode:(HCLinkedNode *)node {
    if (node == nil) {
        return;
    }
    [_map removeObjectForKey:node->_key]; // 删除数据源
    _costCount--;
    if (node->_next) { // node不为尾部节点
        node->_next->_pre = node->_pre; // 将node的后缀节点的前缀设置为node的前缀节点
    }
    if (node->_pre) { // node不为头部节点
        node->_pre->_next = node->_next; // 将node的前缀节点的后缀设置为node的后缀节点
    }
    if (_head == node) { // node为头
        _head = node->_next; // 将头节点设置为node的后缀节点
    }
    if (_tail == node) { // node为尾
        _tail = node->_pre; // 将尾节点设置为node的前缀
    }
}

- (HCLinkedNode *)removeTailNode {
    if (_tail == nil) {
        return nil;
    }
    HCLinkedNode *tail = _tail;
    [_map removeObjectForKey:tail->_key];
    _costCount--;
    if (_head == _tail) {
        _head = _tail = nil;
    } else {
        _tail->_pre->_next = nil;
        _tail = _tail->_pre;
    }
    return tail;
}

- (void)removeAll {
    _head = _tail = nil;
    _costCount = 0;
    [_map removeAllObjects];
}

@end

@interface LRUByLinkedList ()

@property (nonatomic, strong) HCLinkedList *lru;
@property (nonatomic, strong) NSLock *lock;

@end

@implementation LRUByLinkedList

- (instancetype)init {
    self = [super init];
    if (self) {
        _lru = [HCLinkedList new];
        _limitCount = 4;
        _lock = [NSLock new];
    }
    
    return self;
}

- (void)addObject:(id)obj forKey:(nonnull NSString *)key {
    if (key == nil) {
        return;
    }
    
    if (obj == nil) {
        [self.lock lock];
        HCLinkedNode *node = [self.lru->_map valueForKey:key];
        if (node) {
            if (self.delegate && [self.delegate respondsToSelector:@selector(willRemoveObject:)]) {
                [self.delegate willRemoveObject:node->_value];
            }
            [self.lru removeNode:node];
            if (self.delegate && [self.delegate respondsToSelector:@selector(didRemoveObject:)]) {
                [self.delegate didRemoveObject:node->_value];
            }
        }
        [self.lock unlock];
        return;
    }
    
    [self.lock lock];
    // 插入数据
    HCLinkedNode *existNode = [self.lru->_map objectForKey:key];
    if (existNode) {
        [self.lru bringNodeToHead:existNode];
    } else {
        HCLinkedNode *node = [HCLinkedNode new];
        node->_key = key;
        node->_value = obj;
        [self.lru insertNodeAtHead:node];
    }
    // 判断是否超出限制
    if (self.lru->_costCount > self.limitCount) {
        NSInteger costCount = self.lru->_costCount;
        while (costCount > self.limitCount) {
            if (self.delegate && [self.delegate respondsToSelector:@selector(willRemoveObject:)]) {
                [self.delegate willRemoveObject:self.lru->_tail];
            }
            HCLinkedNode *removedNode = [self.lru removeTailNode];
            if (self.delegate && [self.delegate respondsToSelector:@selector(didRemoveObject:)]) {
                [self.delegate didRemoveObject:removedNode->_value];
            }
            costCount--;
        }
    }
    [self.lock unlock];
}

- (void)removeObjectByKey:(NSString *)key {
    if (key == nil) {
        return;
    }
    [self.lock lock];
    HCLinkedNode *node = [self.lru->_map objectForKey:key];
    if (node) {
        if (self.delegate && [self.delegate respondsToSelector:@selector(willRemoveObject:)]) {
            [self.delegate willRemoveObject:node->_value];
        }
        [self->_lru removeNode:node];
        if (self.delegate && [self.delegate respondsToSelector:@selector(didRemoveObject:)]) {
            [self.delegate didRemoveObject:node->_value];
        }
    }
    [self.lock unlock];
}

- (id)queryObjectByKey:(NSString *)key {
    HCLinkedNode *node = [self.lru->_map objectForKey:key];
    if (node) {
        [self.lru bringNodeToHead:node];
    }
    return node ? node->_value : nil;
}

#pragma mark - Private Method


#pragma mark - Getter && Setter

- (NSArray *)allItems {
    NSMutableArray *tmpArray = [NSMutableArray arrayWithCapacity:0];
    HCLinkedNode *node = self.lru->_head;
    while (node) {
        [tmpArray addObject:node->_value];
        node = node->_next;
    }
    
    return tmpArray.copy;
}

@end

@interface HCLinkedNode : NSObject {
    @package
    __unsafe_unretained HCLinkedNode *_pre;
    __unsafe_unretained HCLinkedNode *_next;
    NSString *_key;
    id _value;
}

HCLinkedNode这个结构包含pre、next节点、同时保存了数据的key和value；用于作为链表的node

@interface HCLinkedList : NSObject {
    @package
    NSMutableDictionary *_map;
    HCLinkedNode *_head;
    HCLinkedNode *_tail;
    NSInteger _costCount;
}
@end
  • HCLinkedList包含一个map用来保存数据，head和tail分别来记录链表的头和尾(也就是最近使用和最久未使用的数据)、costCount记录链表的长度
  • 同时提供了链表的操作方法insertNodeAtHead、bringNodeToHead、 removeNode、removeTailNode
    来供不同的场景将数据源封装成node放在链表合适的位置；具体实现看代码有注释

测试用例

- (void)testLRUByLinkedList {
    LRUByLinkedList *lru = [LRUByLinkedList new];
    lru.limitCount = 4;
    lru.delegate = self;
    for (NSInteger i = 0; i < 8; i ++) {
        [lru addObject:@(i) forKey:@(i * 100).stringValue];
    }
    NSLog(@"all items = %@", lru.allItems);
    /*
    输出：
     all items = (
         7,
         6,
         5,
         4
     )
     */
    [lru queryObjectByKey:@"400"];
    NSLog(@"all items = %@", lru.allItems);
    /*
    输出：
     all items = (
         4,
         7,
         6,
         5
     )
     */
    [lru addObject:@(8) forKey:@(8 * 100).stringValue]; // -[ViewController didRemoveObject:] 5
}

- (void)willRemoveObject:(id)object {
    
}

- (void)didRemoveObject:(id)object {
    NSLog(@"%s %@", __FUNCTION__, object);
}

看到输出结果也符合我们的预期

总结

我们在数据缓存的时候，往往会用到一些淘汰算房，常用的就是LRU、LFU；实现这两个算法的方式也可以多式多样；这里也是使用了比较常用的两种方式去实现了一下，同时学习了一下链表的结构和使用

相关文章

网友评论

      本文标题：数据淘汰算法LRU简单实现

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

      延伸阅读

      深度阅读

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

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|数据淘汰算法LRU简单实现|投稿指南|网站地图|RSS订阅|排版工具|手机版

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

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

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

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

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