تنفيذ LRU في كود الإنتاج

Question

لدي بعض أكواد C++ حيث أحتاج إلى تنفيذ استبدال ذاكرة التخزين المؤقت باستخدام تقنية LRU.
أعرف حتى الآن طريقتين لتنفيذ استبدال ذاكرة التخزين المؤقت LRU:

1. استخدام الطابع الزمني في كل مرة يتم فيها الوصول إلى البيانات المخزنة مؤقتًا، وأخيرًا مقارنة الطوابع الزمنية في وقت الاستبدال.
2. استخدام مجموعة من العناصر المخزنة مؤقتًا ونقلها إلى الأعلى إذا تم الوصول إليها مؤخرًا، وبالتالي سيحتوي الجزء السفلي في النهاية على مرشح LRU.

إذن، أي من هذه الأشياء أفضل للاستخدام في كود الإنتاج؟
هل لديهم أي طرق أخرى أفضل؟

Answer 1

لقد قمت مؤخرًا بتنفيذ ذاكرة تخزين مؤقت 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--;
}

Answer 2

فيما يلي تطبيق بسيط جدًا لذاكرة التخزين المؤقت LRU

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

إنه سهل الاستخدام وفهم كيفية عمله.الحجم الإجمالي للكود هو حوالي 50 سطرًا.

Answer 3

من أجل البساطة، ربما ينبغي عليك التفكير في استخدام خريطة Boost's MultiIndex.إذا قمنا بفصل المفتاح عن البيانات، فإننا ندعم مجموعات متعددة من المفاتيح على نفس البيانات.

من [ http://old.nabble.com/realization-of-Last-Recently-Used-cache-with-boost%3A%3Amulti_index-td22326432.html ]:

"... استخدم فهرسين:1) مجزأة للبحث عن القيمة حسب المفتاح 2) تسلسلي لتتبع آخر العناصر المستخدمة مؤخرًا (احصل على عنصر وضع الوظيفة كعنصر أخير في التسلسل.إذا كنا بحاجة إلى إزالة بعض العناصر من ذاكرة التخزين المؤقت، فقد نقوم بحذفها من بداية التسلسل)."

لاحظ أن عامل تشغيل "المشروع" "يسمح للمبرمج بالتنقل بين مؤشرات مختلفة لنفس حاوية الفهرس المتعددة" بكفاءة.

Answer 4

هذا شرط يصف التنفيذ باستخدام زوج من حاويات STL (خريطة قيمة المفتاح بالإضافة إلى قائمة لسجل الوصول إلى المفتاح)، أو حاوية واحدة boost::bimap.

Answer 5

في بيئة الإنتاج الخاصة بنا، نستخدم قائمة مرتبطة مزدوجة C++ والتي تشبه قائمة قائمة مرتبطة بنواة لينكس.يكمن جمال ذلك في أنه يمكنك إضافة كائن إلى أي عدد تريده من القوائم المرتبطة، كما أن عملية القائمة سريعة وبسيطة.