Алгоритм дерева Pseudo LRU

Множество описаний алгоритмов Pseudo LRU включает использование двоичного дерева поиска и установку флажков «отбрасывать» от узла, который вы ищете каждый раз, когда вы обращаетесь к дереву.Алгоритм дерева Pseudo LRU

Это приводит к разумному приближению LRU. Однако из описаний видно, что все узлы, которые считаются LRU, будут листовыми узлами. Существует ли алгоритм псевдо-LRU, который имеет дело со статическим деревом, которое все равно будет работать достаточно хорошо, а определение того, что нелистовые узлы являются подходящими кандидатами LRU?

Редактировать: Я уже реализовал LRU с использованием hashmaps и связанных списков. Мне интересно увидеть влияние производительности использования дерева псевдору (особенно на одновременных чтениях). Вот почему я специально спросил о алгоритмах дерева псевдору, но я должен был сделать это яснее.

источник

2010-05-03 patros

Возможно, это убедит вас использовать хеш-таблицу + связанный список: http://stackoverflow.com/questions/2504178/lru-cache-design/2504317#2504317 – 2010-05-22 13:55:55

Вы всегда можете подтолкнуть свой внутренний узел к листу, поворачивая ала красно-черные деревья.

Сохранение сбалансированного дерева при выполнении этого может быть жестким. Но у вас есть выбор, из какого поддерева нажать, так что, возможно, это невозможно ...

источник

2010-05-03 19:42:52

Я пытаюсь сохранить старую структуру дерева, чтобы разрешить одновременное чтение , а также по соображениям эффективности. (Я понимаю, что на флагах будут условия гонки, но мне все равно, потому что это все-таки псевдо LRU.) – patros

Как сохранить статическое дерево? Узел, который вы удаляете, и узел, который вы добавляете, не имеют одного и того же ключа, поэтому они идут в разных частях дерева. Вы имеете в виду «статические во время попадания в кэш», чтобы вы могли использовать блокировку чтения для поиска? –

Ключи остаются неизменными. Я сопоставляю свои данные с произвольным индексом (от 0 до (2^глубина) -1). Когда я «удаляю» что-то, я просто добавляю этот узел дерева в список доступных узлов. Когда я добавляю, я не добавляю узел, я просто перезаписываю данные, хранящиеся в узле. Это сохраняет старую структуру дерева, но данные все еще изменяемы. – patros

В соответствии с номерами тестов, представленными здесь Study of Different Cache Line Replacement Algorithms in Embedded Systems, псевдо-LRU (PLRUm, PLRUt, MPLRU) выступают в качестве лучших кандидатов для реализации ,

источник

2016-08-10 21:26:19

Алгоритм дерева Pseudo LRU

ответ

Смежные вопросы