To jest runda druga.
Pierwsza runda była tym, co wymyśliłem, a potem ponownie przeczytałem komentarze z domeną nieco bardziej zakorzenioną w mojej głowie.
Oto najprostsza wersja z testem jednostkowym, który pokazuje, że działa w oparciu o inne wersje.
Najpierw wersja niewspółbieżna:
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 ();
}
}
Prawdziwa flaga będzie śledzić dostęp do pobierania i wysyłania. Zobacz JavaDocs. RemoveEdelstEntry bez flagi true dla konstruktora po prostu zaimplementowałoby pamięć podręczną FIFO (zobacz uwagi poniżej na temat FIFO i removeEldestEntry).
Oto test, który dowodzi, że działa jako pamięć podręczna LRU:
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 ();
}
Teraz dla wersji równoległej ...
pakiet 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 ();
}
}
Możesz zobaczyć, dlaczego najpierw omawiam wersję, która nie jest współbieżna. Powyższe próby stworzenia pewnych pasków, aby zmniejszyć rywalizację o blokady. Więc haszuje klucz, a następnie wyszukuje ten skrót, aby znaleźć rzeczywistą pamięć podręczną. To sprawia, że rozmiar limitu jest bardziej sugestią / zgadywaniem z dużą ilością błędu, w zależności od tego, jak dobrze rozłożony jest algorytm skrótu kluczy.
Oto test pokazujący, że wersja równoległa prawdopodobnie działa. :) (Test pod ostrzałem byłby prawdziwym sposobem).
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 ();
}
}
To jest ostatni post .. Pierwszy post, który usunąłem, ponieważ był to LFU, a nie pamięć podręczna LRU.
Pomyślałem, że spróbuję jeszcze raz. Próbowałem wymyślić najprostszą wersję pamięci podręcznej LRU przy użyciu standardowego JDK bez zbyt wielu implementacji.
Oto co wymyśliłem. Moja pierwsza próba była trochę katastrofą, ponieważ zaimplementowałem LFU zamiast i LRU, a potem dodałem do niego FIFO i obsługę LRU ... i zdałem sobie sprawę, że staje się potworem. Potem zacząłem rozmawiać z moim kumplem Johnem, który był ledwo zainteresowany, a potem szczegółowo opisałem, jak zaimplementowałem LFU, LRU i FIFO i jak można to zmienić za pomocą prostego argumentu ENUM, a potem zdałem sobie sprawę, że wszystko, czego naprawdę chcę był prostym LRU. Więc zignoruj wcześniejszy post ode mnie i daj mi znać, jeśli chcesz zobaczyć pamięć podręczną LRU / LFU / FIFO, którą można przełączać za pomocą wyliczenia ... nie? Ok .. oto on.
Najprostszy możliwy LRU wykorzystujący tylko JDK. Zaimplementowałem zarówno wersję współbieżną, jak i inną.
Stworzyłem wspólny interfejs (to minimalizm, więc prawdopodobnie brakuje kilku funkcji, które byś chciał, ale działa w moich przypadkach użycia, ale pozwól, jeśli chcesz zobaczyć funkcję XYZ, daj mi znać ... żyję, aby pisać kod.) .
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 ();
}
Możesz się zastanawiać, czym jest getSilent . Używam tego do testów. getSilent nie zmienia wyniku LRU elementu.
Najpierw nierównoczesny ....
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 ();
}
}
Queue.removeFirstOccurrence jest potencjalnie kosztowna operacja, jeśli masz dużą pamięć podręczną. Można wziąć jako przykład LinkedList i dodać mapę skrótów wyszukiwania wstecznego od elementu do węzła, aby operacje usuwania były DUŻO SZYBSZE i bardziej spójne. Ja też zacząłem, ale potem zdałem sobie sprawę, że tego nie potrzebuję. Ale może...
Po wywołaniu put klucz zostanie dodany do kolejki. Po wywołaniu get klucz jest usuwany i ponownie dodawany na początek kolejki.
Jeśli twoja skrzynka jest mała, a budowanie przedmiotu jest drogie, powinna to być dobra skrzynka. Jeśli twoja pamięć podręczna jest naprawdę duża, wyszukiwanie liniowe może być szyjką butelki, zwłaszcza jeśli nie masz gorących obszarów pamięci podręcznej. Im bardziej intensywne są gorące punkty, tym szybsze jest wyszukiwanie liniowe, ponieważ gorące elementy zawsze znajdują się na szczycie wyszukiwania liniowego. W każdym razie ... aby to działało szybciej, jest napisanie innej LinkedList, która ma operację usuwania, która ma odwrotne wyszukiwanie elementu do węzła w celu usunięcia, a następnie usuwanie byłoby tak szybkie, jak usunięcie klucza z mapy skrótów.
Jeśli masz pamięć podręczną poniżej 1000 elementów, powinno to działać dobrze.
Oto prosty test pokazujący jego działanie w akcji.
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 ();
}
}
Ostatnia pamięć podręczna LRU była jednowątkowa i proszę nie pakować jej w nic zsynchronizowanego ....
Oto próba równoległej wersji.
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 ();
}
}
Główne różnice to użycie ConcurrentHashMap zamiast HashMap oraz użycie Lock (mogłem uciec z synchronizacją, ale ...).
Nie testowałem go pod ostrzałem, ale wygląda na to, że jest to prosta pamięć podręczna LRU, która może się sprawdzić w 80% przypadków użycia, w których potrzebujesz prostej mapy LRU.
Czekam na opinie, z wyjątkiem tego, dlaczego nie używasz biblioteki a, b lub c. Powodem, dla którego nie zawsze używam biblioteki, jest to, że nie zawsze chcę, aby każdy plik wojenny miał 80 MB i piszę biblioteki, więc staram się tworzyć wtyczki bibliotek z wystarczająco dobrym rozwiązaniem i ktoś może podłączyć - u innego dostawcy pamięci podręcznej, jeśli chcą. :) Nigdy nie wiem, kiedy ktoś może potrzebować guawy, ehcache lub czegoś innego, czego nie chcę dołączać, ale jeśli stworzę wtyczkę do buforowania, też ich nie wykluczę.
Zmniejszenie zależności ma swoją nagrodę. Uwielbiam otrzymywać opinie na temat tego, jak to uprościć lub przyspieszyć, lub jedno i drugie.
Również jeśli ktoś wie, że jest gotowy do pracy ....
Ok .. Wiem, o czym myślisz ... Dlaczego po prostu nie użyje wpisu removeEldest z LinkedHashMap i cóż, powinienem, ale .... ale .. ale .. To byłoby FIFO, a nie LRU i byliśmy próbując wdrożyć LRU.
Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {
@Override
protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
return this.size () > limit;
}
};
Ten test kończy się niepowodzeniem dla powyższego kodu ...
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 ();
Oto szybka i brudna pamięć podręczna FIFO przy użyciu metody 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 ();
}
}
FIFO są szybkie. Żadnego szukania. Możesz ustawić FIFO przed LRU, a to całkiem nieźle poradzi sobie z większością gorących wpisów. Lepszy LRU będzie potrzebował tego odwróconego elementu do funkcji Node.
W każdym razie ... teraz, gdy napisałem jakiś kod, przejdę przez inne odpowiedzi i zobaczę, co przegapiłem ... gdy zeskanowałem je po raz pierwszy.
O(1)wymagana wersja: stackoverflow.com/questions/23772102/…