java: Понимание реализации LRU

Question

Я пытаюсь понять приведенное ниже выполнение LRU. Не удалось выяснить, что:

1. Каково использование addFirst(). Этот метод вызывается из метода put и get.
2. Как двойной список поможет отслеживать самую старую запись? Все записи фактически находятся на карте, где одна запись не знает о другой.

Эти вопросы могут звучать глупо, но я был бы очень благодарен за объяснение.

Код:

import java.util.HashMap; 
import java.util.Map; 
import java.util.Map.Entry; 


public class LRUDLL<K, V> { 

private final Map<K, Entry<K,V>> map; 
private Entry<K, V> oldest; 
private final int lruSize; 

public LRUDLL (int lruSize) { 
    if(lruSize <= 0){ 
     throw new IllegalArgumentException("Size is inappropriate"); 
    } 
    map = new HashMap<K, Entry<K, V>>(); 
    this.lruSize = lruSize; 
} 


    private static class Entry<K, V> { 
     Entry<K, V> left; 
     Entry<K, V> right; 
     K key; 
     V value; 

     Entry(Entry<K, V> left, K key, V value, Entry<K, V> right) { 
      this.left = left; 
      this.key = key; 
      this.value = value; 
      this.right = right; 
     } 
    }; 

    private void addFirst(Entry<K, V> entry) { 
     remove(entry); 
     if(oldest == null) { 
      entry.left = entry.right = entry; 
      oldest = entry; 
     } else { 
      Entry<K, V> tail = entry; 

      tail.right = entry; 
      entry.left = tail; 

      //deal with circulating 
      oldest.left = entry; 
      entry.right = oldest; 
     } 
    } 

    private void remove (Entry<K, V> entry) { 
     assert entry != null; 

     if(entry.left != null) entry.left.right = entry.right; 
     if(entry.right != null) entry.right.left = entry.left; 
     if(entry == oldest) oldest = entry.right; 
    } 

    public synchronized void put (K key, V value) { 
     Entry<K, V> entry = new Entry<K, V>(null, key, value, null); 
     map.put(key, entry); 
     addFirst(entry); 
     if(removeOldestEntry()) { 
      remove(oldest); 
     } 
    } 

    public synchronized V get(K key) { 
     Entry<K, V> entry = map.get(key); 
     if(entry!= null) { 
      addFirst(entry); 
      return entry.value; 
     } 
     return null; 
    } 

    private boolean removeOldestEntry() { 
     return map.size() > lruSize; 
    } 
} 

Answer 1

Я думаю, что ключевым моментом здесь является то, что это не просто двусвязный список, это круглый двунаправленный список. Таким образом, oldest является наименее -использованный элемент, oldest.right является второй-наименьший -использованный элемент,. , , и oldest.left есть больше -recently-used элемент. (И oldest.left.left является вторым наиболее -recently используемый элемент, и так далее.)

Я не уверен, почему это было сделано таким образом, — кажется, было бы проще иметь oldest указывая на наименее недавно использованные и newest, указывающие на самый последний использованный —, но это не имеет большого значения.

Что такое addFirst(). Этот метод вызывается из метода put и get.

addFirst удаляет указанную запись из текущего места в списке, и добавляет его слева от oldest, тем самым пометив его как наиболее недавно используемый элемент.

Как список с двойной связью помогает отслеживать самую старую запись? Все записи фактически находятся на карте, где одна запись не знает о другой.

Ну, так что есть серьезная ошибка в этой реализации: он никогда не удаляет элемент из map, так что это на самом деле не кэш LRU. Хуже того, он никогда не отменяет left и right на записях, которые он якобы «удаляет», а это означает, что когда эти записи впоследствии извлекаются из map, а re addFirst -ed, последовательность списка заканчивается совершенно неправильно. Таким образом, реализация полностью нарушена.

Но как это предполагается работать так: map просто имеет все записи, но это ничего, о которых один является наименее недавно использован не знаю. Список сохраняет все элементы в порядке, как недавно они были использованы, поэтому в любой момент времени oldest является наименее используемым.

(Основная причина ошибки в том, что remove используется для двух отдельных вещей: addFirst просто нужно, чтобы удалить элемент из его позиции в списке, так что он может быть перемещен в новое положение, в то время как put на самом деле должен быть в состоянии удалить oldest из map. Вероятно, текущая версия remove должна быть встраиваемыми в addFirst, и новый removeOldest должен быть создан, который фактически удаляет самый старый элемент.)

Answer 2

Что такое использование AddFirst(). Этот метод вызывается как методом put и get.

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

Как список с двойной связью помогает отслеживать самую старую запись? Все записи на самом деле находятся на карте, где одна запись не знает о другой.

Отметьте реализацию LinkedHashMap. Список с двойным соединением поддерживает порядок доступа. Каждая запись знает, к какой записи обращались до и после нее.