LRU 缓存的魔力

2019-07-16 本文已影响12人陈林峰LeonChen1024

原文首发于 https://leonchen1024.com/2018/12/23/S1ep1-The-macgic-of-LRU-Cache/

场景

假设这么一个情况,当你需要多次展示同一个图片的时候,如果你重复从硬盘中加载图片的话,那么会造成资源的浪费,甚至可能会OOM.

这个时候我们可以使用 cache 来避免这种情况,我们只从硬盘中加载一次到内存中,然后在需要的时候反复使用这个照片.

但是,当这个 cache 里的资源已经装满的时候,那么我们就必须移除cache里面的某些数据,来给要加入的数据腾出空间.

解决方案

在这种情况下,我们应该选择移除哪些资源才是最有优的呢?显而易见的,我们应该移除之后不会用到的资源,还有就是间隔最久才会用到的资源.这里有一个详细的最优算法如下:

T = m * T_m + T_h + E

其中:

T = 平均内存引用时间

m = 没选中的概率 = 1 - (选中的概率)

T_m = 当没选中的时候主内存访问的时间(或者,如果是多级缓存的时候,还要算上更低级的缓存内存引用时间的平均值)

T_h = 延迟 : 当选中该资源的时候缓存引用的时间

E = 各种副作用,比如多处理器系统中的排队效应

原文首发于 https://leonchen1024.com/2018/12/23/S1ep1-The-macgic-of-LRU-Cache/
LRU

要得到一个完美的方法是很复杂的,这里我们介绍一个常用的算法,叫做 LRU cache (least recently used),它的原理很简单,就是把使用的元素提到队列的开始,这样最近使用的资源将会在开始的地方,而那些长期未被使用的资源将会在后面,然后当空间不够的时候将会从后面开始释放资源.LRU 的思路是最近使用的资源他们就推测他在未来也有更大的可能性会被使用.

LRU 并不是一个普通的容器.他需要一些策略来实现他的要求.

LruCache 由键值对组成 , 形如 LruCache<key,value>
它需要有一个最大值,要注意它的取值,太小的话那么缓存不了多少东西,会导致频繁的重新读取,导致失去缓存的意义,太大的话可能会导致 oom.所以最好是根据你的应用当前可用的内存来决定这个大小.

//set the max memory used by lru

ActivityManager am = (ActivityManager)getSystemService(Context.ACTIVITY_SERVICE);
int availMemInBytes = am.getMemoryClass() * 1024 * 1024;
//8 is a common value , we can twist it by how much memory can we app used,
//and what kind of the phone we run on.
LruCache bitmapCache = new LruCache<String,Bitmap>(availMemInBytes / 8);

其中 8 是一个比较通用的值,当然你可以根据你的应用所占用的内存来进行调整,还有运行的机型的限制等.

我们还需要知道里面存储的每一个对象的值的大小.比如我们可以
Public class ThumbnailCache extends LruCache<String,Bitmap>{
@Override
protected int sizeOf(String key,Bitmap value){
//return the size of the in-memory bitmap,
//counted against maxSizeBytes
return value.getByteCount();
}
}
当我们从 LruCache 中获取数据的时候,需要对数据已经被回收或者没有进入过缓存的情况做处理.
// get data from Lru and put data to Lru
```
Bitmap bmpToDraw = mCache.get(filename);
if(bmpToDraw == null){
    bmpToDraw = BitmapFactory.decodeFile(filename);
    mCache.put(filename,bmpToDraw);
}
```

还要注意的一点是,当你存进一个较大的对象的时候,有时候 LruCache 会同时清理多个资源来给这个对象腾出位置.

原文首发于 https://leonchen1024.com/2018/12/23/S1ep1-The-macgic-of-LRU-Cache/

Resource

https://www.youtube.com/playlist?list=PLWz5rJ2EKKc9CBxr3BVjPTPoDPLdPIFCE

About Me

我的博客 leonchen1024.com

我的 GitHub https://github.com/LeonChen1024

微信公众号

LRU 缓存的魔力

猜你喜欢

热点阅读