생산 코드에서 LRU 구현

StackOverflow https://stackoverflow.com/questions/2057424

  •  20-09-2019
  •  | 
  •  

문제

LRU 기술을 사용하여 캐시 교체를 구현 해야하는 C ++ 코드가 있습니다.
지금까지 LRU 캐시 교체를 구현하는 두 가지 방법을 알고 있습니다.

  1. 캐시 된 데이터에 액세스 할 때마다 타임 스탬프를 사용하고 최종적으로 교체시 타임 스탬프를 비교합니다.
  2. 캐시 된 품목 스택을 사용하여 최근에 액세스 할 경우 상단으로 이동하므로 마지막으로 바닥에는 LRU 후보가 포함됩니다.

그렇다면이 중 생산 코드에서 사용하는 것이 더 나은 것은 무엇입니까?
그들의 다른 더 나은 방법이 있습니까?

도움이 되었습니까?

해결책

최근에 해시 맵에 링크 된 목록 스프레드를 사용하여 LRU 캐시를 구현했습니다. 

    /// Typedef for URL/Entry pair
    typedef std::pair< std::string, Entry > EntryPair;

    /// Typedef for Cache list
    typedef std::list< EntryPair > CacheList;

    /// Typedef for URL-indexed map into the CacheList
    typedef boost::unordered_map< std::string, CacheList::iterator > CacheMap;

    /// Cache LRU list
    CacheList mCacheList;

    /// Cache map into the list
    CacheMap mCacheMap;

모든 중요한 작업에 대해 O (1)이라는 이점이 있습니다.

삽입 알고리즘 :

// create new entry
Entry iEntry( ... );

// push it to the front;
mCacheList.push_front( std::make_pair( aURL, iEntry ) );

// add it to the cache map
mCacheMap[ aURL ] = mCacheList.begin();

// increase count of entries
mEntries++;

// check if it's time to remove the last element
if ( mEntries > mMaxEntries )
{
    // erease from the map the last cache list element
    mCacheMap.erase( mCacheList.back().first );

    // erase it from the list
    mCacheList.pop_back();

    // decrease count
    mEntries--;
}

다른 팁

다음은 LRU 캐시의 매우 간단한 구현입니다

https://github.com/lamerman/cpp-lru-cache .

사용하기 쉽고 작동 방식을 이해합니다. 코드의 총 크기는 약 50 줄입니다.

단순화하기 위해 Boost의 멀티 index 맵을 사용하는 것을 고려해야 할 것입니다. 키를 데이터와 분리하면 동일한 데이터에서 여러 키 세트를 지원합니다.

에서 [ http://old.nabble.com/realization-of-rast-recently-used-cache-with-boost%3a%3amulti_index-td222326432.html ]:

"... 두 가지 인덱스 사용 : 1) 키로 값을 검색하기 위해 해시 됨) 최근에 사용 된 마지막 항목을 추적하기위한 순차적 (Sequesnce에서 기능을 최종 항목으로 가져 오기. 캐시에서 일부 항목을 제거 해야하는 경우 삭제할 수 있습니다. 시퀀스 시작부터). "

"프로젝트"연산자 "를 통해 프로그래머는 동일한 Multi_index_Container의 다른 지수를 효율적으로 이동할 수 있습니다.

이것 기사 한 쌍의 STL 컨테이너 (키 값 맵과 키 액세스 기록 목록) 또는 단일 쌍을 사용한 구현을 설명합니다. boost::bimap.

우리의 생산 환경에서 우리는 C ++ Double Linked List를 사용하여 Linux 커널 링크 목록. 그것의 아름다움은 원하는만큼 링크 된 목록에 객체를 추가 할 수 있고 목록 작업이 빠르고 간단하다는 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top