キャッシュアルゴリズム(FIFO、LRU、LFUの3つのアルゴリズムの違い)-テール要素を削除する機能がない.

FIFOアルゴリズム
FIFOアルゴリズムは比較的容易に実現できるアルゴリズムである.その思想は先入先出(FIFO、キュー)であり、これは最も簡単で公平な思想であり、つまりデータが一番先に入ると、将来的に訪問される可能性が低いと考えられています.スペースがいっぱいになると、最初に入ったデータが一番早く置き換えられます.
FIFOアルゴリズムの説明:構造時にサイズを決定し、サイズをKと仮定して、2つの機能があるキャッシュ構造を設計する.

set(key,value):この構造に記録(key,value)を挿入する.キャッシュがいっぱいになると、最初にキャッシュに入ったデータを置換します.

get(key):keyに対応するvalue値を返す.

実現:FIFOキューを維持し、各データ(割り当て済みページ)を時間順にリンクしてキューを構成し、置換ポインタを列の先頭に向ける.また置換を行う場合は、置換ポインタが指すデータ(ページ)を順番に交換し、新たに加入したデータを列の最後に差し込むだけでいいです.
短所:一つのページ置換アルゴリズムの優劣を判断する指標はページレートが欠けていることであり、FIFOアルゴリズムの著しい欠点は、ある特定の時点でページ不足率が逆に割り当てページの増加に伴って増加することであり、これをBelady現象と呼ぶ.Belady現象が発生した理由は、FIFO置換アルゴリズムはプロセスアクセスメモリの動的特徴と互換性がなく、置き換えられたメモリページは頻繁にアクセスされたり、あるいはプロセスに十分なページが割り当てられていないため、FIFOアルゴリズムはいくつかのページを頻繁にメモリに入れ替えたり、再登録したりすることによって、欠落率が増加するからである.したがって、今はFIFOアルゴリズムを使用しません.
LRUアルゴリズム
LRU(The Least Recently Used)は、多くの分散キャッシュシステム(Redis、Memcachedなど)で広く使用されている一般的なキャッシュアルゴリズムである.
LRUアルゴリズムの考えは、データがこの間に訪問されなかった場合、将来的にアクセスされる可能性も低いと考えられる.したがって、空間がいっぱいになると、一番長い間訪問していないデータが最初に置き換えられます.
LRUアルゴリズムの説明:構造時にサイズを決定し、サイズをKと仮定して2つの機能を有するキャッシュ構造を設計する.

set(key,value):この構造に記録(key,value)を挿入する.キャッシュがいっぱいになったら、一番長く使われていないデータを置換します.

get(key):keyに対応するvalue値を返す.

実現:一番素朴な思想は配列＋タイムスタンプの方式ですが、効率は低いです.したがって、私たちは双方向リンク(LinkdList)＋ハッシュ・テーブル(hashMap)を用いて、Javaに対応するデータ構造のLinkdHashMapを実現することができる.
LInkedhashMap菗JavaのLinkedHashMapを用いて、非常に簡単なコードで、LRUアルゴリズムに基づくCache機能を実現する.

import java.util.LinkedHashMap;
import java.util.Map;
/**
 *    LinkedHashMap    LRU     
 */
public class LRUCache extends LinkedHashMap {
    private int cacheSize;
    public LRUCache(int cacheSize) {
        super(16, (float) 0.75, true);
        this.cacheSize = cacheSize;
    }
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > cacheSize;
    }
}

テスト:

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class LRUCacheTest {
    private static final Logger log = LoggerFactory.getLogger(LRUCacheTest.class);
    private static LRUCache cache = new LRUCache<>(10);

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            cache.put("k" + i, i);
        }
        log.info("all cache :'{}'",cache);
        cache.get("k3");
        log.info("get k3 :'{}'", cache);
        cache.get("k4");
        log.info("get k4 :'{}'", cache);
        cache.get("k4");
        log.info("get k4 :'{}'", cache);
        cache.put("k" + 10, 10);
        log.info("After running the LRU algorithm cache :'{}'", cache);
    }
}

Output:

all cache :'{k0=0, k1=1, k2=2, k3=3, k4=4, k5=5, k6=6, k7=7, k8=8, k9=9}'
get k3 :'{k0=0, k1=1, k2=2, k4=4, k5=5, k6=6, k7=7, k8=8, k9=9, k3=3}'
get k4 :'{k0=0, k1=1, k2=2, k5=5, k6=6, k7=7, k8=8, k9=9, k3=3, k4=4}'
get k4 :'{k0=0, k1=1, k2=2, k5=5, k6=6, k7=7, k8=8, k9=9, k3=3, k4=4}'
After running the LRU algorithm cache :'{k1=1, k2=2, k5=5, k6=6, k7=7, k8=8, k9=9, k3=3, k4=4, k10=10}'

LFUアルゴリズム
LFU(Least Frequently Used、最近は少なくともアルゴリズムを使用)も一般的なキャッシュアルゴリズムである.
名前の通り、LFUアルゴリズムの考えは、データが最近あまりアクセスされない場合、将来的にアクセスされる可能性も低いと考えられます.したがって、空間がいっぱいになると、最小周波数のアクセスデータが最初に淘汰されます.
LFUアルゴリズムの説明:
構造時にサイズを決定し、仮にサイズがKであると仮定して、2つの機能があるキャッシュ構造を設計する.

set(key,value):この構造に記録(key,value)を挿入する.キャッシュがいっぱいになったら、アクセス頻度が一番低いデータを置換します.

get(key):keyに対応するvalue値を返す.

アルゴリズムの実装戦略:LFUはアクセス頻度が最小のデータを淘汰することを考慮して、データアクセスの周波数を大きさ順に維持する適切な方法が必要です.LFUアルゴリズムは本質的にはtop K問題(K＝1)であり、周波数が最小の要素を選ぶと考えられていますので、周波数が最小の要素を二項の積層で選択できると考えられています.最終的には、小さいトップ・ヒープ＋ハッシュ・テーブルが実現される.