1 LRU算法
LRU（Least recently used余蟹，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問記錄來進行淘汰數(shù)據(jù)梅掠，其核心思想是“如果數(shù)據(jù)最近被訪問過刚盈，那么將來被訪問的幾率也更高”胎许。
這篇文章對LRU緩存算法做了非常詳細的介紹：緩存淘汰算法之LRU-OYK
可惜Foundation框架中并未提供一個比較簡潔的LRU算法找前，NSCache沒怎么看懂，java中有LruCache调俘。
2 使用NSDictionary實現(xiàn)
2.1 實現(xiàn)代碼
為了便于查找伶棒，緩存通常都是Dictionary的形式旺垒，這里也是通過繼承NSMutableDictionary來實現(xiàn)一個包含LRU算法的容器。
頭文件如下肤无，支持泛型：
#import <Foundation/Foundation.h>
@interface LRUMutableDictionary<__covariant KeyType, __covariant ObjectType> : NSObject
// maxCountLRU: 執(zhí)行LRU算法時的最大存儲的元素數(shù)量
- (instancetype)initWithMaxCountLRU:(NSUInteger)maxCountLRU;
//*****NSDictionary
@property (readonly) NSUInteger count;
- (NSEnumerator<KeyType> *)keyEnumerator;
- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(KeyType key, ObjectType obj, BOOL *stop))block;
//*****NSMutableDictionary
- (void)removeObjectForKey:(KeyType)aKey;
- (void)setObject:(ObjectType)anObject forKey:(KeyType <NSCopying>)aKey;
- (void)removeAllObjects;
- (void)removeObjectsForKeys:(NSArray<KeyType> *)keyArray;
//*****LRUMutableDictionary
// 執(zhí)行LRU算法先蒋，當訪問的元素可能是被淘汰的時候，可以通過在block中返回需要訪問的對象舅锄，會根據(jù)LRU機制自動添加到dictionary中
- (ObjectType)objectForKey:(KeyType)aKey returnEliminateObjectUsingBlock:(ObjectType (^)(BOOL maybeEliminate))block;
@end
實現(xiàn)文件如下：
#import "LRUMutableDictionary.h"
@interface LRUMutableDictionary ()
@property (nonatomic, strong) NSMutableDictionary *dict;
@property (nonatomic, strong) NSMutableArray *arrayForLRU;
@property (nonatomic, assign) NSUInteger maxCountLRU;
@end
@implementation LRUMutableDictionary
- (instancetype)initWithMaxCountLRU:(NSUInteger)maxCountLRU
{
self = [super init];
if (self) {
_dict = [[NSMutableDictionary alloc] initWithCapacity:maxCountLRU];
_arrayForLRU = [[NSMutableArray alloc] initWithCapacity:maxCountLRU];
_maxCountLRU = maxCountLRU;
}
return self;
}
#pragma mark - NSDictionary
- (NSUInteger)count
{
return [_dict count];
}
- (NSEnumerator *)keyEnumerator
{
return [_dict keyEnumerator];
}
- (id)objectForKey:(id)aKey
{
return [self objectForKey:aKey returnEliminateObjectUsingBlock:^id(BOOL maybeEliminate) {
return nil;
}];
}
- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block
{
[_dict enumerateKeysAndObjectsUsingBlock:block];
}
#pragma mark - NSMutableDictionary
- (void)removeObjectForKey:(id)aKey
{
[_dict removeObjectForKey:aKey];
[self _removeObjectLRU:aKey];
}
- (void)setObject:(id)anObject forKey:(id<NSCopying>)aKey
{
BOOL isExist = ([_dict objectForKey:aKey] != nil);
[_dict setObject:anObject forKey:aKey];
if (isExist) {
[self _adjustPositionLRU:aKey];
} else {
[self _addObjectLRU:aKey];
}
}
- (void)removeAllObjects
{
[_dict removeAllObjects];
[_arrayForLRU removeAllObjects];
}
- (void)removeObjectsForKeys:(NSArray *)keyArray
{
[_dict removeObjectsForKeys:keyArray];
[_arrayForLRU removeObjectsInArray:keyArray];
}
#pragma mark - LRUMutableDictionary
- (id)objectForKey:(id)aKey returnEliminateObjectUsingBlock:(id (^)(BOOL))block
{
id object = [_dict objectForKey:aKey];
if (object) {
[self _adjustPositionLRU:aKey];
}
if (block) {
BOOL maybeEliminate = object ? NO : YES;
id newObject = block(maybeEliminate);
if (newObject) {
[self setObject:newObject forKey:aKey];
return [_dict objectForKey:aKey];
}
}
return object;
}
#pragma mark - LRU
- (void)_adjustPositionLRU:(id)anObject
{
NSUInteger idx = [_arrayForLRU indexOfObject:anObject];
if (idx != NSNotFound) {
[_arrayForLRU removeObjectAtIndex:idx];
[_arrayForLRU insertObject:anObject atIndex:0];
}
}
- (void)_addObjectLRU:(id)anObject
{
[_arrayForLRU insertObject:anObject atIndex:0];
// 當超出LRU算法限制之后鞭达，將最不常使用的元素淘汰
if ((_maxCountLRU > 0) && (_arrayForLRU.count > _maxCountLRU)) {
[_dict removeObjectForKey:[_arrayForLRU lastObject]];
[_arrayForLRU removeLastObject];
// 【注意】這里不要直接調(diào)用下面這個方法，因為內(nèi)部調(diào)用[_arrayForLRU removeObject:anObject];的時候皇忿，
// 每次都將Array從頭開始遍歷到最后一個畴蹭，這里既然已經(jīng)知道是刪除最后一個了，直接刪除即可鳍烁。
// 使用下面這種方法會增加上百倍的耗時叨襟。
// [self removeObjectForKey:[_arrayForLRU lastObject]];
}
}
- (void)_removeObjectLRU:(id)anObject
{
[_arrayForLRU removeObject:anObject];
}
@end
2.2 實現(xiàn)原理概述
- 實現(xiàn)原理其實很簡單，重寫
NSMutableDictionary的幾個重要方法幔荒，內(nèi)部持有NSMutableDictionary用于存儲緩存數(shù)據(jù)糊闽。持有NSMutableArray用于存儲Key值，Key的順序為LRU算法中的優(yōu)先級爹梁，最前面的元素表示最近使用右犹，最后面的元素表示最近最少使用。 - 每次對
NSMutableDictionary中的元素做數(shù)據(jù)操作姚垃，都認為這個元素是最近使用的元素念链，然后調(diào)整該元素的Key在NSMutableArray中的順序為第一位。 - 設定一個容器可存儲的數(shù)量最大值积糯，當插入元素到超出這個最大值之后掂墓，在
NSMutableArray中找到最后一個元素Key刪除，并在NSMutableDictionary中找到對應的元素刪除看成。
2.3 弊端
- 以上的實現(xiàn)在對性能要求不是特別高的時候君编，已經(jīng)可以滿足需求了。
- 我們知道川慌，
NSMutableArray的內(nèi)部是使用動態(tài)數(shù)組實現(xiàn)的吃嘿，動態(tài)數(shù)組的缺點在這里被完全暴露出來，我們的實現(xiàn)里面基本上都在用到“插入”和“刪除”的操作梦重，這兩個操作對動態(tài)數(shù)組的性能消耗是比較大的兑燥，比較好的實現(xiàn)方式應該是使用“雙向鏈表”，奈何Foundation框架中沒有我們想要的“雙向鏈表”容器忍饰。當然我們可以使用C++的STL庫中的list來實現(xiàn)贪嫂，有興趣的讀者可以嘗試寺庄。 - 容器中有設定一個容器的最大存儲容量值艾蓝，我相信力崇，在使用這個LRU容器時，絕大部分的情況下都是達不到這個最大容量的赢织，淘汰算法應該是屬于一種保護措施不是嗎亮靴？那么問題來了，如果大部分情況下都達不到最大容量于置，或者可能永遠都達不到最大容量茧吊，那我們每次對元素操作時做了LRU算法調(diào)整，不是白費功夫嗎（這個調(diào)整還是要消耗一些性能的）八毯，畢竟這個調(diào)整最終是為了當超出容量時用來將最后面的元素淘汰而做的準備搓侄，想想是不是可以以此做一些優(yōu)化？
3 性能優(yōu)化
針對第三點弊端做一些優(yōu)化话速，當容量達不到最大容量值得時候讶踪，可以完全停止掉LRU算法，這時候這個LRU容器就跟普通的NSMutableDictionary容器沒什么兩樣了泊交，當容量接近最大容量值得時候乳讥，開始啟動LRU算法。
頭文件不變廓俭，來看實現(xiàn)文件：
#import "LRUMutableDictionary.h"
// 定義一個開始準備啟動LRU的值云石，當 (MaxCount - CurCount < LRU_RISK_COUNT) 時才啟動 LRU
#define LRU_RISK_COUNT 100
@interface LRUMutableDictionary ()
@property (nonatomic, strong) NSMutableDictionary *dict; // 存儲數(shù)據(jù)的字典
@property (nonatomic, strong) NSMutableArray *arrayForLRU; // 存放LRU的數(shù)組
@property (nonatomic, assign) NSUInteger maxCountLRU; // 最大存儲值，存儲量超出這個值研乒，啟動LRU淘汰算法
@property (nonatomic, assign) BOOL isOpenLRU; // 是否開啟LRU算法汹忠，如果存儲量遠低于最大存儲值時，其實沒有必要開啟LRU算法
@end
@implementation LRUMutableDictionary
- (instancetype)initWithMaxCountLRU:(NSUInteger)maxCountLRU
{
self = [super init];
if (self) {
_dict = [[NSMutableDictionary alloc] initWithCapacity:maxCountLRU];
_arrayForLRU = [[NSMutableArray alloc] initWithCapacity:maxCountLRU];
_maxCountLRU = maxCountLRU;
}
return self;
}
#pragma mark - NSDictionary
- (NSUInteger)count
{
return [_dict count];
}
- (NSEnumerator *)keyEnumerator
{
return [_dict keyEnumerator];
}
- (id)objectForKey:(id)aKey
{
return [self objectForKey:aKey returnEliminateObjectUsingBlock:^id(BOOL maybeEliminate) {
return nil;
}];
}
- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block
{
[_dict enumerateKeysAndObjectsUsingBlock:block];
}
#pragma mark - NSMutableDictionary
- (void)removeObjectForKey:(id)aKey
{
[_dict removeObjectForKey:aKey];
[self _removeObjectLRU:aKey];
}
- (void)setObject:(id)anObject forKey:(id<NSCopying>)aKey
{
BOOL isExist = ([_dict objectForKey:aKey] != nil);
[_dict setObject:anObject forKey:aKey];
if (isExist) {
[self _adjustPositionLRU:aKey];
} else {
[self _addObjectLRU:aKey];
}
}
- (void)removeAllObjects
{
[_dict removeAllObjects];
[self _removeAllObjectsLRU];
}
- (void)removeObjectsForKeys:(NSArray *)keyArray
{
if (keyArray.count > 0) {
[_dict removeObjectsForKeys:keyArray];
[self _removeObjectsLRU:keyArray];
}
}
#pragma mark - LRUMutableDictionary
- (id)objectForKey:(id)aKey returnEliminateObjectUsingBlock:(id (^)(BOOL))block
{
id object = [_dict objectForKey:aKey];
if (object) {
[self _adjustPositionLRU:aKey];
}
if (block) {
BOOL maybeEliminate = object ? NO : YES;
id newObject = block(maybeEliminate);
if (newObject) {
[self setObject:newObject forKey:aKey];
return [_dict objectForKey:aKey];
}
}
return object;
}
#pragma mark - LRU
- (void)_adjustPositionLRU:(id)anObject
{
if (_isOpenLRU) {
NSUInteger idx = [_arrayForLRU indexOfObject:anObject];
if (idx != NSNotFound) {
[_arrayForLRU removeObjectAtIndex:idx];
[_arrayForLRU insertObject:anObject atIndex:0];
}
}
}
- (void)_addObjectLRU:(id)anObject
{
if (!_isOpenLRU && [self isNeedOpenLRU:_dict.count]) {
// 如果原來沒有開啟 LRU告嘲，現(xiàn)在增加一個元素之后達到了存儲量臨界條件错维，則開啟，一次性將所有的Key導入
[_arrayForLRU removeAllObjects];
[_arrayForLRU addObjectsFromArray:_dict.allKeys];
[_arrayForLRU removeObject:anObject];
_isOpenLRU = YES;
}
if (_isOpenLRU) {
[_arrayForLRU insertObject:anObject atIndex:0];
// 當超出LRU算法限制之后橄唬，將最不常使用的元素淘汰
if ((_maxCountLRU > 0) && (_arrayForLRU.count > _maxCountLRU)) {
[_dict removeObjectForKey:[_arrayForLRU lastObject]];
[_arrayForLRU removeLastObject];
// 【注意】這里不要直接調(diào)用下面這個方法赋焕，因為內(nèi)部調(diào)用[_arrayForLRU removeObject:anObject];的時候，
// 每次都將Array從頭開始遍歷到最后一個仰楚，這里既然已經(jīng)知道是刪除最后一個了隆判，直接刪除即可。
// 使用下面這種方法會增加上百倍的耗時僧界。
// [self removeObjectForKey:[_arrayForLRU lastObject]];
}
}
}
- (void)_removeObjectLRU:(id)anObject
{
if (_isOpenLRU) {
[_arrayForLRU removeObject:anObject];
if (![self isNeedOpenLRU:_arrayForLRU.count]) {
[_arrayForLRU removeAllObjects];
_isOpenLRU = NO;
}
}
}
- (void)_removeObjectsLRU:(NSArray *)otherArray
{
if (_isOpenLRU) {
[_arrayForLRU removeObjectsInArray:otherArray];
if (![self isNeedOpenLRU:_arrayForLRU.count]) {
[_arrayForLRU removeAllObjects];
_isOpenLRU = NO;
}
}
}
- (void)_removeAllObjectsLRU
{
if (_isOpenLRU) {
[_arrayForLRU removeAllObjects];
_isOpenLRU = NO; // 清空全部元素了侨嘀，一定可以關閉LRU
}
}
- (BOOL)isNeedOpenLRU:(NSUInteger)count
{
return (_maxCountLRU - count) < LRU_RISK_COUNT;
}
@end
上面定義 100 接近值可以根據(jù)實際情況做一些修改，以上實現(xiàn)方法已經(jīng)在項目中實際使用捂襟，可以很好的滿足需求咬腕。
讀者如果對于實現(xiàn)LRU算法有更好的方法，歡迎討論葬荷。
本文首發(fā)于我的博客vinnyxiong.cn涨共，歡迎訪問纽帖。
