[C++] map을 활용한 LRU 간단 알고리듬 Develop Tip

LRU(Least Recently Used)라는 것이 있습니다.
글자 그대로 번역을 하면 가장 잘 사용되지 않는.. 이라는 뜻인데요,
OS에서 시스템 페이지를 캐슁 등을 할 때 이용되는 알고리듬 중에 하나입니다.

그런데 이런 방식이 꼭 OS에서만 사용되는 것이 아니라,
일반적인 이용 방식에도 필요할 때가 많습니다.

예를 들어 어떤 리소를 사용하는 Handle 이 있는데,
이 리소스가 여러개 있고 Pool 식으로 자주 사용되는 것은
계속 Open, Close 하지 않고 캐쉬에 있는 것을 바로 사용하는 
것이지요.
만약 이 캐슁 크기가 꽉 찼지만 새로운 자원을 Open해서 가지고 있어야 할 때
가장 현재 부터 먼 시간에 Open되고 사용되지 않은 것을
캐슁에서 제외시키는 것이 유리합니다.

이와 같은 것을 하는 것을 g++의 map 을 이용하여 간단하게 작성하여 보았습니다.


위의 소스를
리눅스에서 (우분투 14.04에서 테스트 하였습니다)

$ g++ -o lru_map lru_map.cpp

이라고 하고 실행시키면,

lru_test: key=<aaa>,target=<0000000000000001>
====================#lruMap=1====================
  key=<aaa>,target=<0000000000000001>,time_t=<1444825622>
lru_test: key=<ccc>,target=<0000000000000003>
====================#lruMap=2====================
  key=<aaa>,target=<0000000000000001>,time_t=<1444825622>
  key=<ccc>,target=<0000000000000003>,time_t=<1444825623>
lru_test: key=<bbb>,target=<0000000000000002>
====================#lruMap=3====================
  key=<aaa>,target=<0000000000000001>,time_t=<1444825622>
  key=<bbb>,target=<0000000000000002>,time_t=<1444825624>
  key=<ccc>,target=<0000000000000003>,time_t=<1444825623>
lru_test: key=<aaa>,target=<0000000000000001>
====================#lruMap=3====================
  key=<aaa>,target=<0000000000000001>,time_t=<1444825625>
  key=<bbb>,target=<0000000000000002>,time_t=<1444825624>
  key=<ccc>,target=<0000000000000003>,time_t=<1444825623>
lru_test: Deleted Target=<0000000000000003>
lru_test: key=<ddd>,target=<0000000000000004>
====================#lruMap=3====================
  key=<aaa>,target=<0000000000000001>,time_t=<1444825625>
  key=<bbb>,target=<0000000000000002>,time_t=<1444825624>
  key=<ddd>,target=<0000000000000004>,time_t=<1444825626>
====================#lruMap=3====================
  key=<aaa>,target=<0000000000000001>,time_t=<1444825625>
  key=<bbb>,target=<0000000000000002>,time_t=<1444825624>
  key=<ddd>,target=<0000000000000004>,time_t=<1444825626>

라고 결과가 나옵니다.

그 결과는 조금만 살펴보면 알 수 있습니다.

위에서 C++의 Map은 Tree 구조라 Skewed 되어 있다면 효율이 안 좋을 수도 있습니다.
(이것이 어느 문서에서는 Binary-Tree라는 곳도 있고 Blanced-Tree 라는 곳도 있습니다.
 만약 Blanced-Tree 라면 생각보다는 잘 나올 수도 있겠네요)

캐슁 사이즈가 비교적 크고 (수천개 이상) 더 빨리 찾기를 원한다면,
해쉬 (키:값) 또는 judyarray를 이용하면 되겠다는 생각이 듭니다.


어느분께는 도움이 되셨기를....


덧글

  • Hide_D 2015/10/15 23:55 # 답글

    일반적으로 STL의 map은 balanced binary tree인 Red-Black tree로 구현합니다. (적어도 Visual Studio와 GCC에선 그렇습니다!)

    코드를 보니 삭제 작업을 O(n)의 시간복잡도로 구현하셨는데,
    LRU를 구현할때에는 list와 map, 또는 해시가 가능한 경우 list와 unordered_map의 조합으로 사용하시는것이 효율이 좋습니다.

    이경우엔 삽입, 삭제가 list+map의 경우엔 O(log n), list+unordered_map의 경우엔 O(1)로 동작합니다.
  • 지훈현서아빠 2015/10/16 09:09 #

    넵. 일단 unorderd_map 으로 해 보면 해슁으로 인해서 더 나은 결과를 가져오겠군요.
    훌륭한 조언 감사드립니다. ^^
댓글 입력 영역

구글애드텍스트