Rumah  >  Artikel  >  Java  >  Algoritma caching: Penjelasan terperinci tentang algoritma LRU, LFU dan FIFO dalam teknologi caching Java

Algoritma caching: Penjelasan terperinci tentang algoritma LRU, LFU dan FIFO dalam teknologi caching Java

王林
王林asal
2023-06-20 21:39:041552semak imbas

Dalam pembangunan Java, caching adalah konsep yang sangat penting. Caching boleh meningkatkan kecekapan membaca dan menulis data, dengan itu meningkatkan prestasi keseluruhan aplikasi. Terdapat banyak algoritma caching, yang biasa termasuk LRU, LFU dan FIFO. Berikut ialah pengenalan terperinci kepada ketiga-tiga algoritma caching ini dan senario aplikasinya.

1. Algoritma LRU

Algoritma LRU paling kurang digunakan baru-baru ini. Algoritma ini bermakna jika sekeping data tidak digunakan dalam tempoh baru-baru ini, kebarangkalian ia digunakan dalam tempoh masa hadapan adalah sangat kecil. Oleh itu, apabila ruang cache tidak mencukupi, data yang paling kurang digunakan baru-baru ini harus dipadamkan untuk mengosongkan ruang. Teras algoritma LRU adalah untuk mengekalkan jadual masa penggunaan, yang boleh dilaksanakan menggunakan senarai terpaut atau tatasusunan.

Berikut ialah pelaksanaan kod mudah menggunakan algoritma LRU dalam Java:

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int CACHE_SIZE;
    public LRUCache(int cacheSize) {
        super((int)Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true);
        CACHE_SIZE = cacheSize;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > CACHE_SIZE;
    }
}

2. Algoritma LFU

Algoritma LFU adalah yang paling kurang kerap digunakan. LFU menentukan data yang harus dicache berdasarkan kekerapan capaian sejarah data. Dalam algoritma LFU, setiap data mempunyai pembilang untuk merekodkan bilangan kali ia telah diakses. Apabila ruang cache tidak mencukupi, data dengan kekerapan akses terendah harus dipadamkan untuk mengosongkan ruang. Teras algoritma LFU adalah untuk mengekalkan jadual kaunter yang merekodkan bilangan akses kepada setiap data.

Berikut ialah pelaksanaan kod mudah menggunakan algoritma LFU dalam Java:

public class LFUCache<K, V> extends LinkedHashMap<K, V> {
    private final int CACHE_SIZE;
    private Map<K, Integer> countMap;
    public LFUCache(int cacheSize) {
        super((int)Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true);
        CACHE_SIZE = cacheSize;
        countMap = new HashMap<>();
    }
    @Override
    public V put(K key, V value) {
        V oldValue = super.put(key, value);
        if (size() > CACHE_SIZE) {
            K leastUsedKey = getLeastUsedKey();
            super.remove(leastUsedKey);
            countMap.remove(leastUsedKey);
        }
        countMap.put(key, countMap.getOrDefault(key, 0) + 1);
        return oldValue;
    }
    private K getLeastUsedKey() {
        K leastUsedKey = null;
        int leastUsedCount = Integer.MAX_VALUE;
        for (Map.Entry<K, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() < leastUsedCount) {
                leastUsedCount = entry.getValue();
                leastUsedKey = entry.getKey();
            }
        }
        return leastUsedKey;
    }
}

3 Algoritma FIFO

Algoritma FIFO adalah pertama masuk, keluar dahulu. Algoritma ini bermakna bahawa data yang diletakkan dahulu dalam cache dipadamkan terlebih dahulu. Apabila ruang cache tidak mencukupi, data yang mula-mula dimasukkan ke dalam cache hendaklah dipadamkan dan data yang baru tiba hendaklah diletakkan pada penghujungnya. Teras algoritma FIFO adalah untuk mengekalkan baris gilir, yang merekodkan masa sisipan setiap data.

Berikut ialah pelaksanaan kod mudah menggunakan algoritma FIFO dalam Java:

public class FIFOCache<K, V> extends LinkedHashMap<K, V> {
    private final int CACHE_SIZE;
    public FIFOCache(int cacheSize) {
        super((int)Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true);
        CACHE_SIZE = cacheSize;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > CACHE_SIZE;
    }
}

Tiga algoritma caching di atas mempunyai kelebihan dan kekurangan mereka sendiri. Kelemahan algoritma LRU ialah jika sekeping data diakses sekali sahaja dalam jangka masa yang panjang, ia juga akan dicache. Kelemahan algoritma LFU ialah ia memerlukan penyelenggaraan jadual kaunter, yang menambah overhed tambahan. Kelemahan algoritma FIFO ialah data dalam cache tidak semestinya yang paling biasa digunakan.

Dalam aplikasi praktikal, algoritma yang sesuai harus dipilih mengikut senario tertentu. Sebagai contoh, untuk beberapa data yang kerap diakses, anda boleh menggunakan algoritma LRU untuk data yang diakses kurang kerap, anda boleh menggunakan algoritma LFU untuk senario aplikasi di mana kecekapan cache adalah lebih penting, anda boleh menggunakan algoritma FIFO;

Atas ialah kandungan terperinci Algoritma caching: Penjelasan terperinci tentang algoritma LRU, LFU dan FIFO dalam teknologi caching Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn