Demand scenarios

Data cache or persistence is generally divided into disk cache and memory cache. From the perspective of read and write speed, we certainly want to read books as fast as possible, so memory cache is favored. However, due to the cost limitation of memory cache, we cannot put all the data in memory cache.

LRU

LRU is the abbreviation of Least Recently Used, which means that the Least Recently Used data will still be Used in the future, while the data that has been Used for a long time will not be Used in the future. With this idea we can keep frequently used data in memory!

If we define a list with a specified capacity, each new data will be placed at the top of the list, and each accessed data will be placed at the top of the list. If the added data exceeds the maximum capacity, delete the best one of the list!

Algorithm source code

1. The OC source code

A. implementation

/ / / initialized
/// @param capacity Capacity
- (instancetype)initWithCapacity:(NSUInteger)capacity{
    if(self= = [super init]){
        _capacity = capacity;
    }
    return self;
}

/// Store the object in the cache. If anyValue is nil, the object is deleted
/// @param anyValue value
/// @param key key
- (void)setValue:(id)anyValue forKey:(NSString *)key{
    if(anyValue == nil) {// Delete the object
        return;
    }
    if([self.cacheDict.allKeys containsObject:key]){
        // The current value already exists
        [self.keys removeObject:key];
    }else{
        // The newly saved value
        if(self.keys.count == _capacity){
            // Delete the first item in the stack
            NSString *firstKey = [self.keys firstObject];
            [self.keys removeObject:firstKey];
            [self.cacheDict removeObjectForKey:firstKey]; }} [self.cacheDict setValue:anyValue forKey:key];
    [self.keys addObject:key];
}

/ / / object
/// @param key key
- (id)valueForKey:(NSString *)key{
    // Check whether it exists
    if([self.cacheDict.allKeys containsObject:key]){
        [self.keys removeObject:key];
        [self.keys addObject:key];
        return [self.cacheDict objectForKey:key];
    }else{
        return nil; }}/// Delete the object
/// @param key key
- (void)removeObjectForKey:(NSString *)key{
    if([self.cacheDict.allKeys containsObject:key]){
        [self.keys removeObject:key];
        [self.cacheDict removeObjectForKey:key];
    }else{
        / / / don't exist}}// get all the data
/// @param block key/value callback
- (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); }}]; }/// Update the capacity
/// @param capacity 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;
}
Copy the code

B. Example

- (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;
}
Copy the code

C. Running result

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
Copy the code

Python source code

A. Source code implementation

from collections import OrderedDict class LRUCacheMap(object): def __init__(self, size): super(LRUCacheMap, Self).__init__() # Total capacity self.total_capcity = size # All key value pairs self.cache_map = OrderedDict() # add new value 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: Self.cache_map. popitem(last = False) else: Len (self.cache_map) == self.total_capCity: Self.cache_map [key] = value def get_value(self, key): 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 + ' ')Copy the code

B. Running result

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]
Copy the code