LRU Cache

LRU란?

Least Recently Used의 약자이다.
OS의 페이지 교체 알고리즘 중 하나로 페이지를 교체할 때
가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 삼는 기법이다.

LRU Cache

LRU Cache는 OS가 아닌 캐시에서 동작한다.
캐시에서 공간이 부족할 때 가장 오랫동안 사용하지 않은 것을 제거하고 새로운 것을 배치하는 형식이다.
LRU방식으로 캐시 메모리를 운영하면 캐시 히트율을 높게 유지할 수 있다는 장점이 있다.
이런 장점으로 인해 가장 많이 사용되는 알고리즘이다.

구현방식을 공부하기 전 필자의 구현방식

우선 필자는 list와 map을 사용해 구현하였다.

val cacheMap: MutableMap<String, cacheItem> = mutableMapOf()
val list: MutableList<String> = mutableListOf()

cacheMap의 key를 String, value를 cacheItem으로 선언하고
list를 최근 참조를 알기 위해 선언하였다.

list에서 최근 참조한 것은 remove하고 add를 해 마지막에 두는 방식으로 구현했다.
가장 참조가 안된 것은 자연스럽게 list의 0번째 index로 갈 것이 뻔하기 때문이다.

우선 무지성 구현을 하고 공부를 더 했다.

공부를 하고보니 이게 뭐람 다른 사람들의 블로그를 확인해보니 사람들은
참조를 할 때마다 index의 0번으로 두고
참조가 가장 덜된 녀석이 index의 가장 마지막으로 가게 두는 방식이였다.
android LRU cache는 0번이 참조가 적게된 것을 확인했다..

뭐 아무튼 구현의 차이를 알고
android에서 lru cache가 어떻게 구현되어 있나를 확인해 보았다.

android LRU cache

안드로이드에서 LRUCache라는 자료구조를 제공한다. 내부구현을 확인해보면

public class LruCache<K, V> {
    @UnsupportedAppUsage
    private final LinkedHashMap<K, V> map;

    /** Size of this cache in units. Not necessarily the number of elements. */
    private int size;
    private int maxSize;
		
		...
}

나는 List랑 Map을 2개 사용했는데 LinkedHashMap이라는 자료구조를 사용했다.
참 비교된다..
생각을 조금만 더 해보면 list와 map을 2개를 사용할 게 아니라
LinkedHashMap을 사용해 적절하게 알맞는 자료구조를 사용할 수 있었다.
LinkedHashMap은 DoubleLinkedList를 사용해 HashMap의 순서를 유지한다.
LinkedHashMap은 accessOrder라는 값을 가지는데 이게 true일 경우 접근 빈도에 따라
data의 순서가 바뀐다.

아무튼 정리를 하자면..
구현할 때 가장 적절한 자료구조를 선택하면서 생각을 좀 더 해보고 더 괜찮은 자료구조가 없나 조금만 생각을 더 해보면 좋을 것 같다..

나중에 해볼 거

Bitmap 캐싱에 있어서 대부분 Glide를 사용한다고 한다(그렇다고 하더라?).
그 외 최근 사용한 데이터 캐싱이 필요한 경우 LruCache사용을 고려할 수 있다고 한다(그렇다고 하더라?).
다음에 혼자서 어플 만들면서 둘다 사용해서 구현해봐야겠다..

참고자료

https://velog.io/@haero_kim/LRU-Cache-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0
https://doublesprogramming.tistory.com/254
https://www.charlezz.com/?p=44551
https://developer.android.com/reference/kotlin/android/util/LruCache