Wie würden Sie einen LRU-Cache in Java implementieren?

169

Bitte sagen Sie nicht EHCache oder OSCache usw. Nehmen Sie für die Zwecke dieser Frage an, dass ich meine eigene nur mit dem SDK implementieren möchte (Learning by Doing). Welche Datenstrukturen würden Sie verwenden, da der Cache in einer Multithread-Umgebung verwendet wird? Ich habe bereits eine mit LinkedHashMap und Collections # synchronizedMap implementiert , bin aber gespannt, ob eine der neuen gleichzeitigen Sammlungen bessere Kandidaten wäre.

UPDATE: Ich habe gerade Yegges neueste Version gelesen, als ich dieses Nugget gefunden habe:

Wenn Sie einen zeitlich konstanten Zugriff benötigen und die Einfügereihenfolge beibehalten möchten, können Sie nichts Besseres tun als eine LinkedHashMap, eine wirklich wunderbare Datenstruktur. Der einzige Weg, wie es möglicherweise wundervoller sein könnte, wäre, wenn es eine gleichzeitige Version gäbe. Aber leider.

Ich habe fast genau das Gleiche gedacht, bevor ich mich für die oben erwähnte LinkedHashMap+ Collections#synchronizedMapImplementierung entschieden habe. Gut zu wissen, dass ich nicht einfach etwas übersehen hatte.

Basierend auf den bisherigen Antworten scheint es meine beste Wahl für eine hochkonkurrierende LRU zu sein, ConcurrentHashMap mit der gleichen Logik zu erweitern, die auch LinkedHashMapverwendet wird.

Hank Gay
quelle
O(1)Erforderliche Version: stackoverflow.com/questions/23772102/…
Ciro Santilli 法轮功 冠状 病 六四 法轮功 法轮功
Sehr ähnliche Frage auch hier
Mifeet

Antworten:

102

Ich mag viele dieser Vorschläge, aber ich denke, ich bleibe vorerst bei LinkedHashMap+ Collections.synchronizedMap. Wenn ich dies in Zukunft noch einmal besuche, werde ich wahrscheinlich daran arbeiten, auf ConcurrentHashMapdie gleiche Weise zu LinkedHashMaperweitern HashMap.

AKTUALISIEREN:

Auf Anfrage hier der Kern meiner aktuellen Implementierung.

private class LruCache<A, B> extends LinkedHashMap<A, B> {
    private final int maxEntries;

    public LruCache(final int maxEntries) {
        super(maxEntries + 1, 1.0f, true);
        this.maxEntries = maxEntries;
    }

    /**
     * Returns <tt>true</tt> if this <code>LruCache</code> has more entries than the maximum specified when it was
     * created.
     *
     * <p>
     * This method <em>does not</em> modify the underlying <code>Map</code>; it relies on the implementation of
     * <code>LinkedHashMap</code> to do that, but that behavior is documented in the JavaDoc for
     * <code>LinkedHashMap</code>.
     * </p>
     *
     * @param eldest
     *            the <code>Entry</code> in question; this implementation doesn't care what it is, since the
     *            implementation is only dependent on the size of the cache
     * @return <tt>true</tt> if the oldest
     * @see java.util.LinkedHashMap#removeEldestEntry(Map.Entry)
     */
    @Override
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {
        return super.size() > maxEntries;
    }
}

Map<String, String> example = Collections.synchronizedMap(new LruCache<String, String>(CACHE_SIZE));
Hank Gay
quelle
15
Ich möchte hier jedoch die Kapselung anstelle der Vererbung verwenden. Dies habe ich von Effective Java gelernt.
Kapil D
10
@KapilD Es ist eine Weile her, aber ich bin mir fast sicher, dass die JavaDocs LinkedHashMapdiese Methode zum Erstellen einer LRU-Implementierung explizit unterstützen.
Hank Gay
7
@HankGay Javas LinkedHashMap (mit drittem Parameter = true) ist kein LRU-Cache. Dies liegt daran, dass das erneute Einfügen eines Eintrags keinen Einfluss auf die Reihenfolge der Einträge hat (ein echter LRU-Cache platziert den zuletzt eingefügten Eintrag am Ende der Iterationsreihenfolge, unabhängig davon, ob dieser Eintrag ursprünglich im Cache vorhanden ist)
Pacerier
2
@ Pacerier Ich sehe dieses Verhalten überhaupt nicht. Mit der zu accessOrder aktivierten Zuordnung wird bei allen Aktionen ein Eintrag als zuletzt verwendet (am aktuellsten) vorgenommen: Erstes Einfügen, Aktualisieren von Werten und Abrufen von Werten. Vermisse ich etwas
Esailija
3
@Pacerier "Das erneute Einfügen eines Eintrags hat keinen Einfluss auf die Reihenfolge der Einträge", dies ist falsch. Wenn Sie sich die Implementierung von LinkedHashMap für die "put" -Methode ansehen, erbt sie die Implementierung von HashMap. Und Javadoc von HashMap sagt: "Wenn die Karte zuvor eine Zuordnung für den Schlüssel enthielt, wird der alte Wert ersetzt." Wenn Sie beim Ersetzen des alten Werts den Quellcode auschecken, wird die recordAccess-Methode aufgerufen. In der recordAccess-Methode von LinkedHashMap sieht dies folgendermaßen aus: if (lm.accessOrder) {lm.modCount ++; entfernen(); addBefore (lm.header);}
Nybon
18

Wenn ich das heute noch einmal von Grund auf machen würde, würde ich Guavas verwenden CacheBuilder.

Hank Gay
quelle
10

Dies ist die zweite Runde.

Die erste Runde war das, was ich mir ausgedacht habe, dann habe ich die Kommentare mit der Domain noch einmal etwas tiefer in meinem Kopf verwurzelt gelesen.

Hier ist also die einfachste Version mit einem Komponententest, der zeigt, dass sie auf der Grundlage einiger anderer Versionen funktioniert.

Zuerst die nicht gleichzeitige Version:

import java.util.LinkedHashMap;
import java.util.Map;

public class LruSimpleCache<K, V> implements LruCache <K, V>{

    Map<K, V> map = new LinkedHashMap (  );


    public LruSimpleCache (final int limit) {
           map = new LinkedHashMap <K, V> (16, 0.75f, true) {
               @Override
               protected boolean removeEldestEntry(final Map.Entry<K, V> eldest) {
                   return super.size() > limit;
               }
           };
    }
    @Override
    public void put ( K key, V value ) {
        map.put ( key, value );
    }

    @Override
    public V get ( K key ) {
        return map.get(key);
    }

    //For testing only
    @Override
    public V getSilent ( K key ) {
        V value =  map.get ( key );
        if (value!=null) {
            map.remove ( key );
            map.put(key, value);
        }
        return value;
    }

    @Override
    public void remove ( K key ) {
        map.remove ( key );
    }

    @Override
    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }


}

Das True-Flag verfolgt den Zugriff auf Gets und Puts. Siehe JavaDocs. Der removeEdelstEntry ohne das true-Flag für den Konstruktor würde lediglich einen FIFO-Cache implementieren (siehe Hinweise unten zu FIFO und removeEldestEntry).

Hier ist der Test, der beweist, dass er als LRU-Cache funktioniert:

public class LruSimpleTest {

    @Test
    public void test () {
        LruCache <Integer, Integer> cache = new LruSimpleCache<> ( 4 );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();


        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();


        if ( !ok ) die ();

    }

Nun zur gleichzeitigen Version ...

Paket org.boon.cache;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class LruSimpleConcurrentCache<K, V> implements LruCache<K, V> {

    final CacheMap<K, V>[] cacheRegions;


    private static class CacheMap<K, V> extends LinkedHashMap<K, V> {
        private final ReadWriteLock readWriteLock;
        private final int limit;

        CacheMap ( final int limit, boolean fair ) {
            super ( 16, 0.75f, true );
            this.limit = limit;
            readWriteLock = new ReentrantReadWriteLock ( fair );

        }

        protected boolean removeEldestEntry ( final Map.Entry<K, V> eldest ) {
            return super.size () > limit;
        }


        @Override
        public V put ( K key, V value ) {
            readWriteLock.writeLock ().lock ();

            V old;
            try {

                old = super.put ( key, value );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return old;

        }


        @Override
        public V get ( Object key ) {
            readWriteLock.writeLock ().lock ();
            V value;

            try {

                value = super.get ( key );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;
        }

        @Override
        public V remove ( Object key ) {

            readWriteLock.writeLock ().lock ();
            V value;

            try {

                value = super.remove ( key );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;

        }

        public V getSilent ( K key ) {
            readWriteLock.writeLock ().lock ();

            V value;

            try {

                value = this.get ( key );
                if ( value != null ) {
                    this.remove ( key );
                    this.put ( key, value );
                }
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;

        }

        public int size () {
            readWriteLock.readLock ().lock ();
            int size = -1;
            try {
                size = super.size ();
            } finally {
                readWriteLock.readLock ().unlock ();
            }
            return size;
        }

        public String toString () {
            readWriteLock.readLock ().lock ();
            String str;
            try {
                str = super.toString ();
            } finally {
                readWriteLock.readLock ().unlock ();
            }
            return str;
        }


    }

    public LruSimpleConcurrentCache ( final int limit, boolean fair ) {
        int cores = Runtime.getRuntime ().availableProcessors ();
        int stripeSize = cores < 2 ? 4 : cores * 2;
        cacheRegions = new CacheMap[ stripeSize ];
        for ( int index = 0; index < cacheRegions.length; index++ ) {
            cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
        }
    }

    public LruSimpleConcurrentCache ( final int concurrency, final int limit, boolean fair ) {

        cacheRegions = new CacheMap[ concurrency ];
        for ( int index = 0; index < cacheRegions.length; index++ ) {
            cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
        }
    }

    private int stripeIndex ( K key ) {
        int hashCode = key.hashCode () * 31;
        return hashCode % ( cacheRegions.length );
    }

    private CacheMap<K, V> map ( K key ) {
        return cacheRegions[ stripeIndex ( key ) ];
    }

    @Override
    public void put ( K key, V value ) {

        map ( key ).put ( key, value );
    }

    @Override
    public V get ( K key ) {
        return map ( key ).get ( key );
    }

    //For testing only
    @Override
    public V getSilent ( K key ) {
        return map ( key ).getSilent ( key );

    }

    @Override
    public void remove ( K key ) {
        map ( key ).remove ( key );
    }

    @Override
    public int size () {
        int size = 0;
        for ( CacheMap<K, V> cache : cacheRegions ) {
            size += cache.size ();
        }
        return size;
    }

    public String toString () {

        StringBuilder builder = new StringBuilder ();
        for ( CacheMap<K, V> cache : cacheRegions ) {
            builder.append ( cache.toString () ).append ( '\n' );
        }

        return builder.toString ();
    }


}

Sie können sehen, warum ich zuerst die nicht gleichzeitige Version behandele. Die obigen Versuche versuchen, einige Streifen zu erstellen, um Sperrenkonflikte zu reduzieren. Also hasht es den Schlüssel und sucht dann diesen Hash, um den tatsächlichen Cache zu finden. Dies macht die Grenzgröße eher zu einem Vorschlag / einer groben Vermutung innerhalb einer angemessenen Menge von Fehlern, abhängig davon, wie gut Ihr Schlüssel-Hash-Algorithmus verbreitet ist.

Hier ist der Test, um zu zeigen, dass die gleichzeitige Version wahrscheinlich funktioniert. :) (Test unter Beschuss wäre der echte Weg).

public class SimpleConcurrentLRUCache {


    @Test
    public void test () {
        LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 1, 4, false );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );

        puts (cache);
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();


        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();

        cache.put ( 8, 8 );
        cache.put ( 9, 9 );

        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();


        puts (cache);


        if ( !ok ) die ();

    }


    @Test
    public void test2 () {
        LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 400, false );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        for (int index =0 ; index < 5_000; index++) {
            cache.get(0);
            cache.get ( 1 );
            cache.put ( 2, index  );
            cache.put ( 3, index );
            cache.put(index, index);
        }

        boolean ok = cache.getSilent ( 0 ) == 0 || die ();
        ok |= cache.getSilent ( 1 ) == 1 || die ();
        ok |= cache.getSilent ( 2 ) != null || die ();
        ok |= cache.getSilent ( 3 ) != null || die ();

        ok |= cache.size () < 600 || die();
        if ( !ok ) die ();



    }

}

Dies ist der letzte Beitrag. Der erste Beitrag, den ich gelöscht habe, war eine LFU und kein LRU-Cache.

Ich dachte, ich würde es noch einmal versuchen. Ich habe versucht, die einfachste Version eines LRU-Caches mit dem Standard-JDK ohne zu viel Implementierung zu entwickeln.

Folgendes habe ich mir ausgedacht. Mein erster Versuch war ein bisschen katastrophal, als ich anstelle von und LRU eine LFU implementierte und dann FIFO und LRU-Unterstützung hinzufügte ... und dann merkte ich, dass es ein Monster wurde. Dann fing ich an, mit meinem Kumpel John zu sprechen, der kaum interessiert war, und dann beschrieb ich ausführlich, wie ich eine LFU, LRU und FIFO implementierte und wie man sie mit einem einfachen ENUM-Argument wechseln konnte, und dann wurde mir klar, dass alles, was ich wirklich wollte war eine einfache LRU. Ignorieren Sie also den früheren Beitrag von mir und lassen Sie mich wissen, ob Sie einen LRU / LFU / FIFO-Cache sehen möchten, der über eine Aufzählung umgeschaltet werden kann ... nein? Ok .. hier geht er.

Die einfachste mögliche LRU, die nur das JDK verwendet. Ich habe sowohl eine gleichzeitige als auch eine nicht gleichzeitige Version implementiert.

Ich habe eine gemeinsame Benutzeroberfläche erstellt (es ist ein Minimalismus, dem wahrscheinlich einige Funktionen fehlen, die Sie möchten, aber er funktioniert für meine Anwendungsfälle. Wenn Sie jedoch die Funktion XYZ sehen möchten, lassen Sie es mich wissen ... Ich lebe, um Code zu schreiben.) .

public interface LruCache<KEY, VALUE> {
    void put ( KEY key, VALUE value );

    VALUE get ( KEY key );

    VALUE getSilent ( KEY key );

    void remove ( KEY key );

    int size ();
}

Sie fragen sich vielleicht, was getSilent ist. Ich benutze dies zum Testen. getSilent ändert die LRU-Punktzahl eines Elements nicht.

Zuerst die nicht gleichzeitige ....

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LruCacheNormal<KEY, VALUE> implements LruCache<KEY,VALUE> {

    Map<KEY, VALUE> map = new HashMap<> ();
    Deque<KEY> queue = new LinkedList<> ();
    final int limit;


    public LruCacheNormal ( int limit ) {
        this.limit = limit;
    }

    public void put ( KEY key, VALUE value ) {
        VALUE oldValue = map.put ( key, value );

        /*If there was already an object under this key,
         then remove it before adding to queue
         Frequently used keys will be at the top so the search could be fast.
         */
        if ( oldValue != null ) {
            queue.removeFirstOccurrence ( key );
        }
        queue.addFirst ( key );

        if ( map.size () > limit ) {
            final KEY removedKey = queue.removeLast ();
            map.remove ( removedKey );
        }

    }


    public VALUE get ( KEY key ) {

        /* Frequently used keys will be at the top so the search could be fast.*/
        queue.removeFirstOccurrence ( key );
        queue.addFirst ( key );
        return map.get ( key );
    }


    public VALUE getSilent ( KEY key ) {

        return map.get ( key );
    }

    public void remove ( KEY key ) {

        /* Frequently used keys will be at the top so the search could be fast.*/
        queue.removeFirstOccurrence ( key );
        map.remove ( key );
    }

    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }
}

Die queue.removeFirstOccurrence ist eine möglicherweise teure Operation, wenn Sie einen großen Cache haben. Man könnte LinkedList als Beispiel nehmen und eine Reverse-Lookup-Hash-Map von Element zu Knoten hinzufügen, um Entfernungsoperationen VIEL SCHNELLER und konsistenter zu machen. Ich habe auch angefangen, aber dann wurde mir klar, dass ich es nicht brauche. Aber vielleicht...

Wenn put aufgerufen wird, wird der Schlüssel zur Warteschlange hinzugefügt. Wenn get aufgerufen wird, wird der Schlüssel entfernt und oben in der Warteschlange wieder hinzugefügt.

Wenn Ihr Cache klein ist und das Erstellen eines Elements teuer ist, sollte dies ein guter Cache sein. Wenn Ihr Cache wirklich groß ist, kann die lineare Suche ein Flaschenhals sein, insbesondere wenn Sie keine heißen Cache-Bereiche haben. Je intensiver die Hot Spots sind, desto schneller ist die lineare Suche, da Hot Items immer ganz oben in der linearen Suche stehen. Wie auch immer ... Damit dies schneller geht, muss eine weitere LinkedList geschrieben werden, die über eine Entfernungsoperation verfügt, bei der ein umgekehrtes Element zur Knotensuche zum Entfernen verwendet wird. Das Entfernen ist dann ungefähr so ​​schnell wie das Entfernen eines Schlüssels aus einer Hash-Map.

Wenn Sie einen Cache unter 1.000 Elementen haben, sollte dies gut funktionieren.

Hier ist ein einfacher Test, um seine Operationen in Aktion zu zeigen.

public class LruCacheTest {

    @Test
    public void test () {
        LruCache<Integer, Integer> cache = new LruCacheNormal<> ( 4 );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 0 ) == 0 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 0 ) == null || die ();
        ok |= cache.getSilent ( 1 ) == null || die ();
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();

        if ( !ok ) die ();

    }
}

Der letzte LRU-Cache war Single-Threaded, und bitte verpacken Sie ihn nicht in etwas Synchronisiertes.

Hier ist ein Stich in eine gleichzeitige Version.

import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantLock;

public class ConcurrentLruCache<KEY, VALUE> implements LruCache<KEY,VALUE> {

    private final ReentrantLock lock = new ReentrantLock ();


    private final Map<KEY, VALUE> map = new ConcurrentHashMap<> ();
    private final Deque<KEY> queue = new LinkedList<> ();
    private final int limit;


    public ConcurrentLruCache ( int limit ) {
        this.limit = limit;
    }

    @Override
    public void put ( KEY key, VALUE value ) {
        VALUE oldValue = map.put ( key, value );
        if ( oldValue != null ) {
            removeThenAddKey ( key );
        } else {
            addKey ( key );
        }
        if (map.size () > limit) {
            map.remove ( removeLast() );
        }
    }


    @Override
    public VALUE get ( KEY key ) {
        removeThenAddKey ( key );
        return map.get ( key );
    }


    private void addKey(KEY key) {
        lock.lock ();
        try {
            queue.addFirst ( key );
        } finally {
            lock.unlock ();
        }


    }

    private KEY removeLast( ) {
        lock.lock ();
        try {
            final KEY removedKey = queue.removeLast ();
            return removedKey;
        } finally {
            lock.unlock ();
        }
    }

    private void removeThenAddKey(KEY key) {
        lock.lock ();
        try {
            queue.removeFirstOccurrence ( key );
            queue.addFirst ( key );
        } finally {
            lock.unlock ();
        }

    }

    private void removeFirstOccurrence(KEY key) {
        lock.lock ();
        try {
            queue.removeFirstOccurrence ( key );
        } finally {
            lock.unlock ();
        }

    }


    @Override
    public VALUE getSilent ( KEY key ) {
        return map.get ( key );
    }

    @Override
    public void remove ( KEY key ) {
        removeFirstOccurrence ( key );
        map.remove ( key );
    }

    @Override
    public int size () {
        return map.size ();
    }

    public String toString () {
        return map.toString ();
    }
}

Die Hauptunterschiede sind die Verwendung der ConcurrentHashMap anstelle von HashMap und die Verwendung der Sperre (ich hätte mit synchronisiert davonkommen können, aber ...).

Ich habe es nicht unter Beschuss getestet, aber es scheint ein einfacher LRU-Cache zu sein, der in 80% der Anwendungsfälle funktioniert, in denen Sie eine einfache LRU-Karte benötigen.

Ich freue mich über Feedback, außer warum Sie die Bibliothek a, b oder c nicht verwenden. Der Grund, warum ich nicht immer eine Bibliothek verwende, ist, dass ich nicht immer möchte, dass jede War-Datei 80 MB groß ist, und ich schreibe Bibliotheken, sodass ich die Bibliotheken mit einer ausreichend guten Lösung steckbar mache und jemand einstecken kann -in einem anderen Cache-Anbieter, wenn sie möchten. :) Ich weiß nie, wann jemand Guava oder ehcache oder etwas anderes benötigt, das ich nicht einschließen möchte, aber wenn ich das Caching steckbar mache, werde ich sie auch nicht ausschließen.

Die Reduzierung von Abhängigkeiten hat ihre eigene Belohnung. Ich freue mich über Feedback, wie ich dies noch einfacher oder schneller oder beides machen kann.

Auch wenn jemand von einem Ready to Go weiß ....

Ok .. ich weiß was du denkst ... Warum benutzt er nicht einfach den Eintrag removeEldest von LinkedHashMap und nun sollte ich aber ... aber ... aber ... das wäre ein FIFO, kein LRU und wir waren es versuchen, eine LRU zu implementieren.

    Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {

        @Override
        protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
            return this.size () > limit;
        }
    };

Dieser Test schlägt für den obigen Code fehl ...

        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();

Hier ist also ein schneller und schmutziger FIFO-Cache mit removeEldestEntry.

import java.util.*;

public class FifoCache<KEY, VALUE> implements LruCache<KEY,VALUE> {

    final int limit;

    Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {

        @Override
        protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
            return this.size () > limit;
        }
    };


    public LruCacheNormal ( int limit ) {
        this.limit = limit;
    }

    public void put ( KEY key, VALUE value ) {
         map.put ( key, value );


    }


    public VALUE get ( KEY key ) {

        return map.get ( key );
    }


    public VALUE getSilent ( KEY key ) {

        return map.get ( key );
    }

    public void remove ( KEY key ) {
        map.remove ( key );
    }

    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }
}

FIFOs sind schnell. Keine Suche. Sie könnten ein FIFO vor eine LRU stellen, und das würde die meisten heißen Einträge recht gut handhaben. Eine bessere LRU benötigt dieses Reverse-Element zur Node-Funktion.

Wie auch immer ... jetzt, wo ich Code geschrieben habe, lass mich die anderen Antworten durchgehen und sehen, was ich verpasst habe ... als ich sie das erste Mal gescannt habe.

RickHigh
quelle
9

LinkedHashMapist O (1), erfordert jedoch eine Synchronisation. Dort muss das Rad nicht neu erfunden werden.

2 Optionen zur Erhöhung der Parallelität:

1. Erstellen Sie mehrere LinkedHashMapund hashen Sie sie ein: Beispiel : LinkedHashMap[4], index 0, 1, 2, 3. Wählen Sie auf der Taste do key%4 (oder binary ORon [key, 3]) aus, welche Karte zum Put / Get / Remove verwendet werden soll.

2. Sie können eine "fast" LRU erstellen ConcurrentHashMap, indem Sie eine verknüpfte Hash-Map-ähnliche Struktur in jeder der darin enthaltenen Regionen erstellen. Das Sperren würde granularer erfolgen als das LinkedHashMap, das synchronisiert wird. Bei einem putoder putIfAbsentnur einem Schloss am Kopf und am Ende der Liste wird benötigt (pro Region). Beim Entfernen oder Abrufen muss die gesamte Region gesperrt werden. Ich bin gespannt, ob Atomic-verknüpfte Listen hier helfen könnten - wahrscheinlich auch für den Kopf der Liste. Vielleicht für mehr.

Die Struktur würde nicht die Gesamtreihenfolge beibehalten, sondern nur die Reihenfolge pro Region. Solange die Anzahl der Einträge viel größer ist als die Anzahl der Regionen, ist dies für die meisten Caches ausreichend. Jede Region muss eine eigene Anzahl von Einträgen haben. Diese wird anstelle der globalen Anzahl für den Räumungsauslöser verwendet. Die Standardanzahl von Regionen in a ConcurrentHashMapist 16, was für die meisten Server heutzutage ausreichend ist.

  1. wäre einfacher zu schreiben und schneller bei mäßiger Parallelität.

  2. Es wäre schwieriger zu schreiben, aber bei sehr hoher Parallelität viel besser zu skalieren. Es wäre langsamer für den normalen Zugriff (genauso wie ConcurrentHashMapes langsamer ist als dort, HashMapwo es keine Parallelität gibt)

Jiaweizhang
quelle
8

Es gibt zwei Open Source-Implementierungen.

Apache Solr hat ConcurrentLRUCache: https://lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html

Es gibt ein Open Source-Projekt für eine ConcurrentLinkedHashMap: http://code.google.com/p/concurrentlinkedhashmap/

Ron
quelle
2
Solrs Lösung ist eigentlich keine LRU, aber die ConcurrentLinkedHashMapist interessant. Es wird behauptet, MapMakervon Guava übernommen worden zu sein, aber ich habe es in den Dokumenten nicht entdeckt. Irgendeine Idee, was mit dieser Anstrengung los ist?
Hank Gay
3
Eine vereinfachte Version wurde integriert, aber die Tests wurden noch nicht abgeschlossen, sodass sie noch nicht öffentlich sind. Ich hatte viele Probleme mit einer tieferen Integration, aber ich hoffe, sie zu beenden, da es einige nette algorithmische Eigenschaften gibt. Die Möglichkeit, eine Räumung (Kapazität, Ablauf, GC) anzuhören, wurde hinzugefügt und basiert auf dem Ansatz von CLHM (Listener Queue). Ich möchte auch die Idee der "gewichteten Werte" einbringen, da dies beim Zwischenspeichern von Sammlungen nützlich ist. Leider war ich aufgrund anderer Verpflichtungen zu überfüllt, um die Zeit zu verwenden, die Guave verdient (und die ich Kevin / Charles versprochen habe).
Ben Manes
3
Update: Die Integration wurde in Guava r08 abgeschlossen und veröffentlicht. Dies erfolgt über die Einstellung #maximumSize ().
Ben Manes
7

Ich würde in Betracht ziehen, java.util.concurrent.PriorityBlockingQueue zu verwenden , wobei die Priorität durch einen "numberOfUses" -Zähler in jedem Element bestimmt wird. Ich würde sehr, sehr vorsichtig sein , um alle meine Synchronisationen korrekt zu machen, da der Zähler "numberOfUses" impliziert, dass das Element nicht unveränderlich sein kann.

Das Elementobjekt wäre ein Wrapper für die Objekte im Cache:

class CacheElement {
    private final Object obj;
    private int numberOfUsers = 0;

    CacheElement(Object obj) {
        this.obj = obj;
    }

    ... etc.
}
Steve McLeod
quelle
meinst du nicht muss unveränderlich sein?
Shsteimer
2
Beachten Sie, dass Sie, wenn Sie versuchen, die von Steve Mcleod erwähnte Priorityblockingqueue-Version auszuführen, das Element unveränderlich machen sollten, da das Ändern des Elements in der Warteschlange keine Auswirkungen hat. Sie müssen das Element entfernen und erneut hinzufügen, um dies zu tun Priorisieren Sie es neu.
James
James unten zeigt einen Fehler, den ich gemacht habe. Was ich als Beweis dafür anbiete, wie schwierig es ist, zuverlässige, robuste Caches zu schreiben.
Steve McLeod
6

Hoffe das hilft .

import java.util.*;
public class Lru {

public static <K,V> Map<K,V> lruCache(final int maxSize) {
    return new LinkedHashMap<K, V>(maxSize*4/3, 0.75f, true) {

        private static final long serialVersionUID = -3588047435434569014L;

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize;
        }
    };
 }
 public static void main(String[] args ) {
    Map<Object, Object> lru = Lru.lruCache(2);      
    lru.put("1", "1");
    lru.put("2", "2");
    lru.put("3", "3");
    System.out.println(lru);
}
}
Murasing
quelle
1
Schönes Beispiel! Könnten Sie kommentieren, warum die Kapazität maxSize * 4/3 eingestellt werden muss?
Akvel
1
@Akvel heißt Anfangskapazität, kann ein beliebiger [ganzzahliger] Wert sein, während 0,75f der Standardladefaktor ist. Ich hoffe, dieser Link hilft: ashishsharma.me/2011/09/custom-lru-cache-java.html
Murasing
5

Der LRU-Cache kann mithilfe einer ConcurrentLinkedQueue und einer ConcurrentHashMap implementiert werden, die auch im Multithreading-Szenario verwendet werden können. Der Kopf der Warteschlange ist das Element, das sich am längsten in der Warteschlange befunden hat. Das Ende der Warteschlange ist das Element, das sich in kürzester Zeit in der Warteschlange befunden hat. Wenn ein Element in der Map vorhanden ist, können wir es aus der LinkedQueue entfernen und am Ende einfügen.

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

public class LRUCache<K,V> {
  private ConcurrentHashMap<K,V> map;
  private ConcurrentLinkedQueue<K> queue;
  private final int size; 

  public LRUCache(int size) {
    this.size = size;
    map = new ConcurrentHashMap<K,V>(size);
    queue = new ConcurrentLinkedQueue<K>();
  }

  public V get(K key) {
    //Recently accessed, hence move it to the tail
    queue.remove(key);
    queue.add(key);
    return map.get(key);
  }

  public void put(K key, V value) {
    //ConcurrentHashMap doesn't allow null key or values
    if(key == null || value == null) throw new NullPointerException();
    if(map.containsKey(key) {
      queue.remove(key);
    }
    if(queue.size() >= size) {
      K lruKey = queue.poll();
      if(lruKey != null) {
        map.remove(lruKey);
      }
    }
    queue.add(key);
    map.put(key,value);
  }

}
Sanjanab
quelle
Dies ist nicht threadsicher. Beispielsweise können Sie die maximale LRU-Größe leicht durch gleichzeitiges Aufrufen überschreiten put.
dpeacock
Bitte korrigiere es. Erstens wird es nicht in der Zeile map.containsKey (Schlüssel) kompiliert. Zweitens sollten Sie in get () überprüfen, ob der Schlüssel wirklich entfernt wurde, da sonst Map und Queue nicht mehr synchron sind und "queue.size ()> = size" immer wahr wird. Ich werde meine Version veröffentlichen, in der dies behoben ist, da mir Ihre Idee, diese beiden Sammlungen zu verwenden, gefallen hat.
Aleksander Lech
3

Hier ist meine Implementierung für LRU. Ich habe PriorityQueue verwendet, das im Grunde genommen als FIFO und nicht threadsicher funktioniert. Verwendeter Komparator basierend auf der Erstellung der Seitenzeit und basierend auf der Ausführung der Reihenfolge der Seiten für die zuletzt verwendete Zeit.

Zu berücksichtigende Seiten: 2, 1, 0, 2, 8, 2, 4

In den Cache hinzugefügte Seite ist: 2
In den Cache hinzugefügte Seite ist: 1
In den Cache hinzugefügte Seite ist: 0
Seite: 2 bereits im Cache vorhanden. Zuletzt aktualisierte Zugriffszeit Seitenfehler
, SEITE: 1, ersetzt durch SEITE: 8 Die
in den Cache hinzugefügte Seite ist: 8
Seite: 2 ist bereits im Cache vorhanden. Zuletzt aktualisierte
Zugriffszeit Seitenfehler, SEITE: 0, Ersetzt durch SEITE: 4 Die
in den Cache hinzugefügte Seite ist: 4

AUSGABE

LRUCache-Seiten
-------------
Seitenname: 8, PageCreationTime: 1365957019974
PageName: 2, PageCreationTime: 1365957020074
PageName: 4, PageCreationTime: 1365957020174

Code hier eingeben

import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;


public class LRUForCache {
    private PriorityQueue<LRUPage> priorityQueue = new PriorityQueue<LRUPage>(3, new LRUPageComparator());
    public static void main(String[] args) throws InterruptedException {

        System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4");
        System.out.println("----------------------------------------------\n");

        LRUForCache cache = new LRUForCache();
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("1"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("0"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("8"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("4"));
        Thread.sleep(100);

        System.out.println("\nLRUCache Pages");
        System.out.println("-------------");
        cache.displayPriorityQueue();
    }


    public synchronized void  addPageToQueue(LRUPage page){
        boolean pageExists = false;
        if(priorityQueue.size() == 3){
            Iterator<LRUPage> iterator = priorityQueue.iterator();

            while(iterator.hasNext()){
                LRUPage next = iterator.next();
                if(next.getPageName().equals(page.getPageName())){
                    /* wanted to just change the time, so that no need to poll and add again.
                       but elements ordering does not happen, it happens only at the time of adding
                       to the queue

                       In case somebody finds it, plz let me know.
                     */
                    //next.setPageCreationTime(page.getPageCreationTime()); 

                    priorityQueue.remove(next);
                    System.out.println("Page: " + page.getPageName() + " already exisit in cache. Last accessed time updated");
                    pageExists = true;
                    break;
                }
            }
            if(!pageExists){
                // enable it for printing the queue elemnts
                //System.out.println(priorityQueue);
                LRUPage poll = priorityQueue.poll();
                System.out.println("Page Fault, PAGE: " + poll.getPageName()+", Replaced with PAGE: "+page.getPageName());

            }
        }
        if(!pageExists){
            System.out.println("Page added into cache is : " + page.getPageName());
        }
        priorityQueue.add(page);

    }

    public void displayPriorityQueue(){
        Iterator<LRUPage> iterator = priorityQueue.iterator();
        while(iterator.hasNext()){
            LRUPage next = iterator.next();
            System.out.println(next);
        }
    }
}

class LRUPage{
    private String pageName;
    private long pageCreationTime;
    public LRUPage(String pagename){
        this.pageName = pagename;
        this.pageCreationTime = System.currentTimeMillis();
    }

    public String getPageName() {
        return pageName;
    }

    public long getPageCreationTime() {
        return pageCreationTime;
    }

    public void setPageCreationTime(long pageCreationTime) {
        this.pageCreationTime = pageCreationTime;
    }

    @Override
    public boolean equals(Object obj) {
        LRUPage page = (LRUPage)obj; 
        if(pageCreationTime == page.pageCreationTime){
            return true;
        }
        return false;
    }

    @Override
    public int hashCode() {
        return (int) (31 * pageCreationTime);
    }

    @Override
    public String toString() {
        return "PageName: " + pageName +", PageCreationTime: "+pageCreationTime;
    }
}


class LRUPageComparator implements Comparator<LRUPage>{

    @Override
    public int compare(LRUPage o1, LRUPage o2) {
        if(o1.getPageCreationTime() > o2.getPageCreationTime()){
            return 1;
        }
        if(o1.getPageCreationTime() < o2.getPageCreationTime()){
            return -1;
        }
        return 0;
    }
}
Deepak Singhvi
quelle
2

Hier ist meine getestete leistungsstärkste gleichzeitige LRU-Cache-Implementierung ohne synchronisierten Block:

public class ConcurrentLRUCache<Key, Value> {

private final int maxSize;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

/**
 * @param key - may not be null!
 * @param value - may not be null!
 */
public void put(final Key key, final Value value) {
    if (map.containsKey(key)) {
        queue.remove(key); // remove the key from the FIFO queue
    }

    while (queue.size() >= maxSize) {
        Key oldestKey = queue.poll();
        if (null != oldestKey) {
            map.remove(oldestKey);
        }
    }
    queue.add(key);
    map.put(key, value);
}

/**
 * @param key - may not be null!
 * @return the value associated to the given key or null
 */
public Value get(final Key key) {
    return map.get(key);
}

}}

Zoltan Boda
quelle
1
@zoltan boda .... Sie haben nicht eine Situation behandelt .. was ist, wenn das gleiche Objekt mehrmals verwendet wird? In diesem Fall sollten wir nicht mehrere Einträge für dasselbe Objekt hinzufügen ... stattdessen sollte sein Schlüssel sein
5
Warnung: Dies ist kein LRU-Cache. In einem LRU-Cache werfen Sie die Elemente weg, auf die zuletzt zugegriffen wurde. Dieser wirft die zuletzt weggeschriebenen Gegenstände weg. Es ist auch ein linearer Scan, um die Operation queue.remove (key) auszuführen.
Dave L.
Auch ConcurrentLinkedQueue # size () ist keine Operation mit konstanter Zeit.
NateS
3
Ihre Put-Methode sieht nicht sicher aus - sie enthält einige Check-Then-Act-Anweisungen, die mit mehreren Threads unterbrochen werden.
Assylias
2

Dies ist der von mir verwendete LRU-Cache, der eine LinkedHashMap kapselt und die Parallelität mit einer einfachen Synchronisierungssperre behandelt, die die saftigen Stellen schützt. Es "berührt" Elemente, wenn sie verwendet werden, so dass sie wieder das "frischeste" Element werden, so dass es tatsächlich LRU ist. Ich hatte auch die Anforderung, dass meine Elemente eine minimale Lebensdauer haben, die Sie auch als "maximal zulässige Leerlaufzeit" betrachten können, dann sind Sie zur Räumung bereit.

Ich stimme jedoch Hanks Schlussfolgerung zu und akzeptiere die Antwort - wenn ich heute wieder damit anfangen würde, würde ich mir Guavas ansehen CacheBuilder.

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;


public class MaxIdleLRUCache<KK, VV> {

    final static private int IDEAL_MAX_CACHE_ENTRIES = 128;

    public interface DeadElementCallback<KK, VV> {
        public void notify(KK key, VV element);
    }

    private Object lock = new Object();
    private long minAge;
    private HashMap<KK, Item<VV>> cache;


    public MaxIdleLRUCache(long minAgeMilliseconds) {
        this(minAgeMilliseconds, IDEAL_MAX_CACHE_ENTRIES);
    }

    public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries) {
        this(minAgeMilliseconds, idealMaxCacheEntries, null);
    }

    public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries, final DeadElementCallback<KK, VV> callback) {
        this.minAge = minAgeMilliseconds;
        this.cache = new LinkedHashMap<KK, Item<VV>>(IDEAL_MAX_CACHE_ENTRIES + 1, .75F, true) {
            private static final long serialVersionUID = 1L;

            // This method is called just after a new entry has been added
            public boolean removeEldestEntry(Map.Entry<KK, Item<VV>> eldest) {
                // let's see if the oldest entry is old enough to be deleted. We don't actually care about the cache size.
                long age = System.currentTimeMillis() - eldest.getValue().birth;
                if (age > MaxIdleLRUCache.this.minAge) {
                    if ( callback != null ) {
                        callback.notify(eldest.getKey(), eldest.getValue().payload);
                    }
                    return true; // remove it
                }
                return false; // don't remove this element
            }
        };

    }

    public void put(KK key, VV value) {
        synchronized ( lock ) {
//          System.out.println("put->"+key+","+value);
            cache.put(key, new Item<VV>(value));
        }
    }

    public VV get(KK key) {
        synchronized ( lock ) {
//          System.out.println("get->"+key);
            Item<VV> item = getItem(key);
            return item == null ? null : item.payload;
        }
    }

    public VV remove(String key) {
        synchronized ( lock ) {
//          System.out.println("remove->"+key);
            Item<VV> item =  cache.remove(key);
            if ( item != null ) {
                return item.payload;
            } else {
                return null;
            }
        }
    }

    public int size() {
        synchronized ( lock ) {
            return cache.size();
        }
    }

    private Item<VV> getItem(KK key) {
        Item<VV> item = cache.get(key);
        if (item == null) {
            return null;
        }
        item.touch(); // idle the item to reset the timeout threshold
        return item;
    }

    private static class Item<T> {
        long birth;
        T payload;

        Item(T payload) {
            this.birth = System.currentTimeMillis();
            this.payload = payload;
        }

        public void touch() {
            this.birth = System.currentTimeMillis();
        }
    }

}
broc.seib
quelle
2

Nun, für einen Cache suchen Sie im Allgemeinen einige Daten über ein Proxy-Objekt (eine URL, eine Zeichenfolge ...), sodass Sie in Bezug auf die Benutzeroberfläche eine Karte benötigen. Aber um die Dinge rauszuwerfen, möchten Sie eine Warteschlangenstruktur. Intern würde ich zwei Datenstrukturen pflegen, eine Priority-Queue und eine HashMap. Hier ist eine Implementierung, die in der Lage sein sollte, alles in O (1) Zeit zu erledigen.

Hier ist eine Klasse, die ich ziemlich schnell zusammengestellt habe:

import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V>
{
    int maxSize;
    int currentSize = 0;

    Map<K, ValueHolder<K, V>> map;
    LinkedList<K> queue;

    public LRUCache(int maxSize)
    {
        this.maxSize = maxSize;
        map = new HashMap<K, ValueHolder<K, V>>();
        queue = new LinkedList<K>();
    }

    private void freeSpace()
    {
        K k = queue.remove();
        map.remove(k);
        currentSize--;
    }

    public void put(K key, V val)
    {
        while(currentSize >= maxSize)
        {
            freeSpace();
        }
        if(map.containsKey(key))
        {//just heat up that item
            get(key);
            return;
        }
        ListNode<K> ln = queue.add(key);
        ValueHolder<K, V> rv = new ValueHolder<K, V>(val, ln);
        map.put(key, rv);       
        currentSize++;
    }

    public V get(K key)
    {
        ValueHolder<K, V> rv = map.get(key);
        if(rv == null) return null;
        queue.remove(rv.queueLocation);
        rv.queueLocation = queue.add(key);//this ensures that each item has only one copy of the key in the queue
        return rv.value;
    }
}

class ListNode<K>
{
    ListNode<K> prev;
    ListNode<K> next;
    K value;
    public ListNode(K v)
    {
        value = v;
        prev = null;
        next = null;
    }
}

class ValueHolder<K,V>
{
    V value;
    ListNode<K> queueLocation;
    public ValueHolder(V value, ListNode<K> ql)
    {
        this.value = value;
        this.queueLocation = ql;
    }
}

class LinkedList<K>
{
    ListNode<K> head = null;
    ListNode<K> tail = null;

    public ListNode<K> add(K v)
    {
        if(head == null)
        {
            assert(tail == null);
            head = tail = new ListNode<K>(v);
        }
        else
        {
            tail.next = new ListNode<K>(v);
            tail.next.prev = tail;
            tail = tail.next;
            if(tail.prev == null)
            {
                tail.prev = head;
                head.next = tail;
            }
        }
        return tail;
    }

    public K remove()
    {
        if(head == null)
            return null;
        K val = head.value;
        if(head.next == null)
        {
            head = null;
            tail = null;
        }
        else
        {
            head = head.next;
            head.prev = null;
        }
        return val;
    }

    public void remove(ListNode<K> ln)
    {
        ListNode<K> prev = ln.prev;
        ListNode<K> next = ln.next;
        if(prev == null)
        {
            head = next;
        }
        else
        {
            prev.next = next;
        }
        if(next == null)
        {
            tail = prev;
        }
        else
        {
            next.prev = prev;
        }       
    }
}

So funktioniert das. Schlüssel werden in einer verknüpften Liste mit den ältesten Schlüsseln vorne in der Liste gespeichert (neue Schlüssel gehen nach hinten). Wenn Sie also etwas "auswerfen" müssen, legen Sie es einfach von der Vorderseite der Warteschlange ab und verwenden Sie dann den Schlüssel, um Entfernen Sie den Wert aus der Karte. Wenn auf ein Element verwiesen wird, nehmen Sie den ValueHolder aus der Karte und verwenden dann die Variable queuelocation, um den Schlüssel von seiner aktuellen Position in der Warteschlange zu entfernen und ihn dann am Ende der Warteschlange abzulegen (es ist jetzt die zuletzt verwendete). Das Hinzufügen von Dingen ist ziemlich gleich.

Ich bin mir sicher, dass es hier eine Menge Fehler gibt und ich habe keine Synchronisation implementiert. Diese Klasse bietet jedoch O (1) Hinzufügen zum Cache, O (1) Entfernen alter Elemente und O (1) Abrufen von Cache-Elementen. Selbst eine triviale Synchronisation (nur jede öffentliche Methode synchronisieren) hätte aufgrund der Laufzeit immer noch wenig Sperrenkonflikte. Wenn jemand clevere Synchronisationstricks hat, wäre ich sehr interessiert. Ich bin mir auch sicher, dass es einige zusätzliche Optimierungen gibt, die Sie mithilfe der Variablen maxsize in Bezug auf die Karte implementieren können.

Luke
quelle
Vielen Dank für den Detaillierungsgrad, aber wo kann die LinkedHashMap+ Collections.synchronizedMap()Implementierung implementiert werden?
Hank Gay
Leistung, ich weiß es nicht genau, aber ich glaube nicht, dass LinkedHashMap eine O (1) -Einfügung hat (wahrscheinlich O (log (n))). Eigentlich könnten Sie ein paar Methoden hinzufügen, um die Kartenschnittstelle in meiner Implementierung zu vervollständigen Verwenden Sie dann Collections.synchronizedMap, um Parallelität hinzuzufügen.
Luke
In der LinkedList-Klasse oben in der add-Methode befindet sich ein Code im else-Block, dh if (tail.prev == null) {tail.prev = head; head.next = tail; } Wann wird dieser Code ausgeführt? Ich bin ein paar Trockenläufe gelaufen und ich denke, dies wird niemals ausgeführt und sollte entfernt werden.
Dipesh
1

Schauen Sie sich ConcurrentSkipListMap an . Es sollte Ihnen log (n) Zeit zum Testen und Entfernen eines Elements geben, wenn es bereits im Cache enthalten ist, und konstante Zeit zum erneuten Hinzufügen.

Sie benötigen lediglich einen Zähler usw. und ein Wrapper-Element, um die Reihenfolge der LRU-Reihenfolge zu erzwingen und sicherzustellen, dass aktuelle Inhalte verworfen werden, wenn der Cache voll ist.

Madlep
quelle
Würde ConcurrentSkipListMapeine einfache Implementierung Vorteile bringen ConcurrentHashMap, oder geht es einfach darum, pathologische Fälle zu vermeiden?
Hank Gay
Dies würde die Dinge einfacher machen, da ConcurrentSkipListMap Elemente bestellt, mit denen Sie verwalten können, in welcher Reihenfolge Dinge verwendet wurden. ConcurrentHashMap tut dies nicht, sodass Sie im Grunde den gesamten Cache-Inhalt durchlaufen müssen, um die letzten Elemente eines Elements zu aktualisieren gebrauchter Zähler 'oder was auch immer
madlep
Mit der ConcurrentSkipListMapImplementierung würde ich also eine neue Implementierung der MapSchnittstelle erstellen, die an eine ConcurrentSkipListMapArt Wrapping delegiert und diese ausführt, sodass die beliebigen Schlüsseltypen in einen Typ eingeschlossen werden, der leicht nach dem letzten Zugriff sortiert werden kann.
Hank Gay
1

Hier ist meine kurze Implementierung, bitte kritisieren oder verbessern Sie sie!

package util.collection;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
 * Limited size concurrent cache map implementation.<br/>
 * LRU: Least Recently Used.<br/>
 * If you add a new key-value pair to this cache after the maximum size has been exceeded,
 * the oldest key-value pair will be removed before adding.
 */

public class ConcurrentLRUCache<Key, Value> {

private final int maxSize;
private int currentSize = 0;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

private synchronized void freeSpace() {
    Key key = queue.poll();
    if (null != key) {
        map.remove(key);
        currentSize = map.size();
    }
}

public void put(Key key, Value val) {
    if (map.containsKey(key)) {// just heat up that item
        put(key, val);
        return;
    }
    while (currentSize >= maxSize) {
        freeSpace();
    }
    synchronized(this) {
        queue.add(key);
        map.put(key, val);
        currentSize++;
    }
}

public Value get(Key key) {
    return map.get(key);
}
}
Zoltan Boda
quelle
1
Dies ist kein LRU-Cache, sondern nur ein FIFO-Cache.
lslab
1

Hier ist meine eigene Implementierung zu diesem Problem

simplelrucache bietet threadsicheres, sehr einfaches, nicht verteiltes LRU-Caching mit TTL-Unterstützung. Es bietet zwei Implementierungen:

  • Concurrent basierend auf ConcurrentLinkedHashMap
  • Synchronisiert basierend auf LinkedHashMap

Sie finden es hier: http://code.google.com/p/simplelrucache/

Daimon
quelle
1

Der beste Weg, dies zu erreichen, ist die Verwendung einer LinkedHashMap, die die Einfügereihenfolge der Elemente beibehält. Es folgt ein Beispielcode:

public class Solution {

Map<Integer,Integer> cache;
int capacity;
public Solution(int capacity) {
    this.cache = new LinkedHashMap<Integer,Integer>(capacity); 
    this.capacity = capacity;

}

// This function returns false if key is not 
// present in cache. Else it moves the key to 
// front by first removing it and then adding 
// it, and returns true. 

public int get(int key) {
if (!cache.containsKey(key)) 
        return -1; 
    int value = cache.get(key);
    cache.remove(key); 
    cache.put(key,value); 
    return cache.get(key); 

}

public void set(int key, int value) {

    // If already present, then  
    // remove it first we are going to add later 
       if(cache.containsKey(key)){
        cache.remove(key);
    }
     // If cache size is full, remove the least 
    // recently used. 
    else if (cache.size() == capacity) { 
        Iterator<Integer> iterator = cache.keySet().iterator();
        cache.remove(iterator.next()); 
    }
        cache.put(key,value);
}

}}

Dhirendra Gautam
quelle
0

Ich suche nach einem besseren LRU-Cache mit Java-Code. Können Sie Ihren Java LRU-Cache-Code mit LinkedHashMapund freigeben Collections#synchronizedMap? Derzeit verwende ich LRUMap implements Mapund der Code funktioniert einwandfrei, aber ich mache ArrayIndexOutofBoundExceptionmit der folgenden Methode Lasttests mit 500 Benutzern. Die Methode verschiebt das zuletzt verwendete Objekt vor die Warteschlange.

private void moveToFront(int index) {
        if (listHead != index) {
            int thisNext = nextElement[index];
            int thisPrev = prevElement[index];
            nextElement[thisPrev] = thisNext;
            if (thisNext >= 0) {
                prevElement[thisNext] = thisPrev;
            } else {
                listTail = thisPrev;
            }
            //old listHead and new listHead say new is 1 and old was 0 then prev[1]= 1 is the head now so no previ so -1
            // prev[0 old head] = new head right ; next[new head] = old head
            prevElement[index] = -1;
            nextElement[index] = listHead;
            prevElement[listHead] = index;
            listHead = index;
        }
    }

get(Object key)und put(Object key, Object value)Methode ruft die obige moveToFrontMethode auf.

Raj Pandian
quelle
0

Wollte der Antwort von Hank einen Kommentar hinzufügen, aber einige, wie ich nicht in der Lage bin - bitte behandeln Sie es als Kommentar

LinkedHashMap verwaltet die Zugriffsreihenfolge auch basierend auf den in seinem Konstruktor übergebenen Parametern. Es wird eine doppelt gezeichnete Liste geführt, um die Reihenfolge aufrechtzuerhalten (siehe LinkedHashMap.Entry).

@Pacerier Es ist richtig, dass LinkedHashMap während der Iteration dieselbe Reihenfolge beibehält, wenn das Element erneut hinzugefügt wird, dies gilt jedoch nur für den Einfügungsreihenfolgenmodus.

Dies ist, was ich in Java-Dokumenten des LinkedHashMap.Entry-Objekts gefunden habe

    /**
     * This method is invoked by the superclass whenever the value
     * of a pre-existing entry is read by Map.get or modified by Map.set.
     * If the enclosing Map is access-ordered, it moves the entry
     * to the end of the list; otherwise, it does nothing.
     */
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
    }

Diese Methode sorgt dafür, dass das Element, auf das kürzlich zugegriffen wurde, an das Ende der Liste verschoben wird. Alles in allem ist LinkedHashMap also die beste Datenstruktur für die Implementierung von LRUCache.

Abhishek Gayakwad
quelle
0

Ein weiterer Gedanke und sogar eine einfache Implementierung mit der LinkedHashMap-Sammlung von Java.

LinkedHashMap hat die Methode removeEldestEntry bereitgestellt, die auf die im Beispiel erwähnte Weise überschrieben werden kann. Standardmäßig ist die Implementierung dieser Sammlungsstruktur falsch. Wenn die wahre Größe dieser Struktur über die ursprüngliche Kapazität hinausgeht, werden die ältesten oder älteren Elemente entfernt.

Wir können ein Pageno und einen Seiteninhalt haben. In meinem Fall ist Pageno eine Ganzzahl und ein Seiteninhalt. Ich habe die Zeichenfolge für die Seitenzahlwerte beibehalten.

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author Deepak Singhvi
 *
 */
public class LRUCacheUsingLinkedHashMap {


     private static int CACHE_SIZE = 3;
     public static void main(String[] args) {
        System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99");
        System.out.println("----------------------------------------------\n");


// accessOrder is true, so whenever any page gets changed or accessed,    // its order will change in the map, 
              LinkedHashMap<Integer,String> lruCache = new              
                 LinkedHashMap<Integer,String>(CACHE_SIZE, .75F, true) {

           private static final long serialVersionUID = 1L;

           protected boolean removeEldestEntry(Map.Entry<Integer,String>                           

                     eldest) {
                          return size() > CACHE_SIZE;
                     }

                };

  lruCache.put(2, "2");
  lruCache.put(1, "1");
  lruCache.put(0, "0");
  System.out.println(lruCache + "  , After first 3 pages in cache");
  lruCache.put(2, "2");
  System.out.println(lruCache + "  , Page 2 became the latest page in the cache");
  lruCache.put(8, "8");
  System.out.println(lruCache + "  , Adding page 8, which removes eldest element 2 ");
  lruCache.put(2, "2");
  System.out.println(lruCache+ "  , Page 2 became the latest page in the cache");
  lruCache.put(4, "4");
  System.out.println(lruCache+ "  , Adding page 4, which removes eldest element 1 ");
  lruCache.put(99, "99");
  System.out.println(lruCache + " , Adding page 99, which removes eldest element 8 ");

     }

}

Das Ergebnis der obigen Codeausführung ist wie folgt:

 Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99
--------------------------------------------------
    {2=2, 1=1, 0=0}  , After first 3 pages in cache
    {2=2, 1=1, 0=0}  , Page 2 became the latest page in the cache
    {1=1, 0=0, 8=8}  , Adding page 8, which removes eldest element 2 
    {0=0, 8=8, 2=2}  , Page 2 became the latest page in the cache
    {8=8, 2=2, 4=4}  , Adding page 4, which removes eldest element 1 
    {2=2, 4=4, 99=99} , Adding page 99, which removes eldest element 8 
Deepak Singhvi
quelle
Das ist ein FIFO. Er bat um eine LRU.
RickHigh
Dieser Test schlägt fehl ... cache.get (2); cache.get (3); cache.put (6, 6); cache.put (7, 7); ok | = cache.size () == 4 || die ("size" + cache.size ()); ok | = cache.getSilent (2) == 2 || sterben (); ok | = cache.getSilent (3) == 3 || sterben (); ok | = cache.getSilent (4) == null || sterben (); ok | = cache.getSilent (5) == null || sterben ();
RickHigh
0

Nach dem @ sanjanab-Konzept (aber nach Korrekturen) habe ich meine Version des LRUCache erstellt, die auch den Consumer bereitstellt, der es ermöglicht, bei Bedarf etwas mit den entfernten Elementen zu tun.

public class LRUCache<K, V> {

    private ConcurrentHashMap<K, V> map;
    private final Consumer<V> onRemove;
    private ConcurrentLinkedQueue<K> queue;
    private final int size;

    public LRUCache(int size, Consumer<V> onRemove) {
        this.size = size;
        this.onRemove = onRemove;
        this.map = new ConcurrentHashMap<>(size);
        this.queue = new ConcurrentLinkedQueue<>();
    }

    public V get(K key) {
        //Recently accessed, hence move it to the tail
        if (queue.remove(key)) {
            queue.add(key);
            return map.get(key);
        }
        return null;
    }

    public void put(K key, V value) {
        //ConcurrentHashMap doesn't allow null key or values
        if (key == null || value == null) throw new IllegalArgumentException("key and value cannot be null!");

        V existing = map.get(key);
        if (existing != null) {
            queue.remove(key);
            onRemove.accept(existing);
        }

        if (map.size() >= size) {
            K lruKey = queue.poll();
            if (lruKey != null) {
                V removed = map.remove(lruKey);
                onRemove.accept(removed);
            }
        }
        queue.add(key);
        map.put(key, value);
    }
}
Aleksander Lech
quelle
-1

Android bietet eine Implementierung eines LRU-Cache . Der Code ist sauber und unkompliziert.

Elioks
quelle