Множество описаний алгоритмов Pseudo LRU включает использование двоичного дерева поиска и установку флажков «отбрасывать» от узла, который вы ищете каждый раз, когда вы обращаетесь к дереву.Алгоритм дерева Pseudo LRU
Это приводит к разумному приближению LRU. Однако из описаний видно, что все узлы, которые считаются LRU, будут листовыми узлами. Существует ли алгоритм псевдо-LRU, который имеет дело со статическим деревом, которое все равно будет работать достаточно хорошо, а определение того, что нелистовые узлы являются подходящими кандидатами LRU?
Редактировать: Я уже реализовал LRU с использованием hashmaps и связанных списков. Мне интересно увидеть влияние производительности использования дерева псевдору (особенно на одновременных чтениях). Вот почему я специально спросил о алгоритмах дерева псевдору, но я должен был сделать это яснее.
Возможно, это убедит вас использовать хеш-таблицу + связанный список: http://stackoverflow.com/questions/2504178/lru-cache-design/2504317#2504317 – 2010-05-22 13:55:55