LRUCache(独立模块 lru_cache.py)
  • collection.MutableMapping是一个Abstract Base Class, LRUCache这个类继承他来提供mutalbeMapping的功能.Inherited Mapping methods and pop, popitem, clear, update, and setdefault
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

# MutableMapping是第一个虚类,当实现__getitem__,__setitem__等方法的时候,可以使用类似update等方法
class LRUCache(collections.MutableMapping):
"""This class is not thread safe"""

def __init__(self, timeout=60, close_callback=None, *args, **kwargs):
self.timeout = timeout
self.close_callback = close_callback
self._store = {} # k/v的实际存储区域
self._time_to_keys = collections.defaultdict(list) # {time1:[a,b,c], time2:[c,d,e]}
self._keys_to_last_time = {} # {a:time1, b:time1, c:time2}
self._last_visits = collections.deque() #未被sweep的lastvisits
self._closed_values = set() # 临时区域,当sweep的时候来记录有多少被sweep
self.update(dict(*args, **kwargs)) # use the free update to set keys

def __getitem__(self, key):
# O(1)
t = time.time()
self._keys_to_last_time[key] = t
self._time_to_keys[t].append(key)
self._last_visits.append(t)
return self._store[key]

def __setitem__(self, key, value):
# O(1)
t = time.time()
self._keys_to_last_time[key] = t
self._store[key] = value
self._time_to_keys[t].append(key)
self._last_visits.append(t)

def __delitem__(self, key):
# O(1)
del self._store[key]
del self._keys_to_last_time[key]

def __iter__(self):
return iter(self._store)

def __len__(self):
return len(self._store)

def sweep(self):
# O(m)
now = time.time()
c = 0
while len(self._last_visits) > 0:
least = self._last_visits[0]
if now - least <= self.timeout:
break
self._last_visits.popleft()
for key in self._time_to_keys[least]:
if key in self._store:
if now - self._keys_to_last_time[key] > self.timeout:
if self.close_callback is not None:
value = self._store[key]
if value not in self._closed_values:
self.close_callback(value)
self._closed_values.add(value)
del self._store[key]
del self._keys_to_last_time[key]
c += 1
del self._time_to_keys[least]
if c:
self._closed_values.clear()
logging.debug('%d keys swept' % c)

# 当最近有操作的时候,取出最近一次访问的时间,找出相应的值,确定这些值都已经超时,并清除,同时调用close_callback,告知这个值被清除掉

下面是类似具体存储的表示

1
2
3
time_to_keys = {time1:[a, b, c], time2:[c, d, e]}
last_visit = [time1, time2]
keys_to_last_time = {a:time1, b:time1, c:time2 ...}
延伸:SDWebImage的Cache
  • SDWebImage的cache分为memcache和diskcache两种。memcache集成自NSCache,就是在收到内存警告的时候autopurge(removeAllObjects)
  • diskcache其实是在清理最近不使用的图片,https://swiftcafe.io/2017/02/19/sdimage-cache/ ,在文件夹中根据最近的modifytime来排序,同时会看具体释放了多少空间以及有没有达到config里面大小的要求
1
2
3
4
5
NSArray<NSString *> *resourceKeys = @[NSURLIsDirectoryKey, NSURLContentModificationDateKey, NSURLTotalFileAllocatedSizeKey];
NSDirectoryEnumerator *fileEnumerator = [_fileManager enumeratorAtURL:diskCacheURL
includingPropertiesForKeys:resourceKeys
options:NSDirectoryEnumerationSkipsHiddenFiles
errorHandler:NULL];
延伸:YYMemoryCache

YYMemoryCache里面其实有OC下的LRU的实现思路,这个就比较典型,用双向链表和Dictionary来实现O(1)的读取以及O(1)的添加删除

要注意的几个点

  • 时间使用了CACurrentMediaTime,http://nshipster.cn/benchmarking/,这个时间跟NSDate等不一样,不会因为时区变化,夏令制等等产生影响
  • 使用pthread_mutex_lock(&_lock);pthread_mutex_unlock(&_lock); 来加锁。
  • yycache中的双向链表是反着的,读源码的时候要注意(开始看了半天没明白,后来网上找到别人的图才发现他的head和tail居然是反着的)

pasted image

https://blog.ibireme.com/2015/10/26/yycache/
https://github.com/ibireme/YYCache/blob/master/YYCache/YYMemoryCache.m

双向链表的节点:

1
2
3
4
5
6
7
8
9
10
@interface _YYLinkedMapNode : NSObject {
@package
__unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
__unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
id _key;
id _value;
NSUInteger _cost;
NSTimeInterval _time;
}
@end