[컴][알고리즘] LRU cache 구현 예제

LRU cache implementation, LRU 캐쉬 구현

C

c 로 만든 LRU cache 이다. Least Requested Used 제일 적게 요청되고, 사용되어진 녀석이 cache 가 max 일 때 먼저 사라진다.
Linked List 로 구현한 queue 를 이용해 구현하고 있다. 그리고 cache 안에서 검색을 위해 hash table 을 이용하고 있다.

http://www.geeksforgeeks.org/implement-lru-cache/

Java

안드로이드 관련 cache 소스는 아래에서 확인할 수 있다.

• LazyList/MemoryCache.java at master · thest1/LazyList · GitHub

이녀석과 구글의 LRUCache class 를 비교해서 보면 이해가 쉬울 것이다.

• platform_frameworks_support/LruCache.java at 39b32a9feea6b821d6a5c92202c400aa1f252200 · android/platform_frameworks_support · GitHub

설명이 필요하다면

• Caching Bitmaps | Android Developers

를 참고하자.




아래는 LazyList/MemoryCache.java 에 대한 주석이 조금 더 들어간 source code 이다.

import android.graphics.Bitmap;
import android.util.Log;

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;

/**
 * source from : https://github.com/thest1/LazyList/blob/master/src/com/fedorvlasov/lazylist/MemoryCache.java
 *
 * This memory cache is modified in reference to the Caching Bitmap
 * {@ref: http://developer.android.com/training/displaying-bitmaps/cache-bitmap.html} article
 * 
 *  
 */
public class MemoryCache {

    private static final String TAG = "MemoryCache";
    private Map<String, Bitmap> cache= Collections.synchronizedMap(
            new LinkedHashMap<String, Bitmap>(10, 1.5f, true));//Last argument true for LRU ordering
    private long size = 0;//current allocated size
    private long limit = 0;//max memory in bytes


    public MemoryCache(){

        // http://javarevisited.blogspot.kr/2012/01/find-max-free-total-memory-in-java.html
        //
        //use 25% of available heap size
        setLimit(Runtime.getRuntime().maxMemory()/4);
    }
    
    public void setLimit(long new_limit){
        limit = new_limit;
        Log.i(TAG, "MemoryCache will use up to " + limit / 1024. / 1024. + "MB");
    }

    public Bitmap get(String id){
        try{
            if(!cache.containsKey(id))
                return null;
            //NullPointerException sometimes happen here http://code.google.com/p/osmdroid/issues/detail?id=78 
            return cache.get(id);
        }catch(NullPointerException ex){
            ex.printStackTrace();
            return null;
        }
    }

    public void put(String id, Bitmap bitmap){
        try{
            if(cache.containsKey(id))
                size -= getSizeInBytes(cache.get(id));
            cache.put(id, bitmap);
            size += getSizeInBytes(bitmap);
            checkSize();
        }catch(Throwable th){
            th.printStackTrace();
        }
    }
    
    private void checkSize() {
        Log.i(TAG, "cache size=" + size + " length=" + cache.size());
        if(size > limit){
                synchronized(cache){    //namh added
                    Iterator<Entry<String, Bitmap>> iter = cache.entrySet().iterator();//least recently accessed item will be the first one iterated
                    while(iter.hasNext()){
                        Entry<String, Bitmap> entry = iter.next();
                        size -= getSizeInBytes(entry.getValue());
                        iter.remove();
                        if(size<=limit)
                            break;
                    }
                }
            Log.i(TAG, "Clean cache. New size " + cache.size());
        }
    }

    public void clear() {
        try{
            //NullPointerException sometimes happen here http://code.google.com/p/osmdroid/issues/detail?id=78

            // http://stackoverflow.com/questions/12218976/cannot-draw-recycled-bitmaps-when-displaying-bitmaps-in-gallery-attached-to-ad
            //
            // recycle() should be called when no reference gets the bitmap.
            // but in this case, when the view is showed, always some bitmap is being used.
            // Thus, you must NOT recycle() here.

            cache.clear();
            size = 0;

            //namh what about this?
            //System.gc();
        }catch(NullPointerException ex){
            ex.printStackTrace();
        }
    }

    long getSizeInBytes(Bitmap bitmap) {
        if(bitmap==null)
            return 0;
        return bitmap.getRowBytes() * bitmap.getHeight();
    }



    // the destructor should also handle the memory in case it still holds memory
    protected void finalize() {
        // http://stackoverflow.com/questions/8996655/android-bitmap-and-memory-management
        //
        synchronized(cache){
            // get HashMap entry iterator
            Iterator<Entry<String, Bitmap>> iter = cache.entrySet().iterator();
            while(iter.hasNext()) {
                // get entry pair
                Entry<String, Bitmap> entry = iter.next();
                // get Bitmap object
                Bitmap image = entry.getValue();
                // recycle if...
                if(image != null && !image.isRecycled()) {
                    image.recycle();
                    image = null;
                }
            }
            cache.clear();
        }// end of synchronized
    }
    
        
    
}

fds