理想和现实的差距 – Redis的近似LRU

最近看一些算法题，各种时间复杂度，空间复杂度充斥脑海。O(N), O(N^2), O(NLogN)。这里拿LRU(Least Recently Used)算法来举一个例子算法和实际的差别。

这个是Leetcode里面的算法: https://leetcode.com/problems/lru-cache/. 没有兴趣的人其实也不用看，基本上就是设计一个LRU算法，保证读取和插入的时间复杂度都是O(N). 代码基本上也就100行左右，貌似很简单。但是如果看Redis的文档我们会发现这段话：

https://redis.io/topics/lru-cache

Redis LRU algorithm is not an exact implementation. This means that Redis is not able to pick the best candidate for eviction, that is, the access that was accessed the most in the past. Instead it will try to run an approximation of the LRU algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys.

既然算法这么简单为什么Redis的默认实现不去做严格的LRU呢？其实原因很简单，为了节省空间。在传统的时间和空间复杂度里面，所有的非指数级的增长都被归纳成一个结果。比如说O(N) 和 O(2n)，或者更夸张的O(100N)或者更多。这在实际中能是一样的？使用double的空间，花费double的时间，再怎么说也不一样的。