Data StructuresMenengahFase D–FE1E5
LRU CACHE
LRU Cache adalah penyimpanan cepat berukuran terbatas yang membuang item paling lama tidak dipakai ketika ruangnya penuh. Tiap kali sebuah item diakses, ia ditandai sebagai yang paling baru dipakai, sehingga item yang menganggur paling lama berada di urutan buang berikutnya. Visualisasi menampilkan daftar item yang urutannya berubah tiap akses dan item terlama yang tersingkir saat item baru masuk.
Example use case
Alasan HP dengan RAM kecil menutup sendiri aplikasi yang lama tidak kamu buka saat kamu membuka game berat.
Syllabus
Simpan item terbatas di memori cepat, lalu buang yang paling lama tak dipakai saat penuh.
Objectives
- ·Memahami kenapa memori cepat harus dibatasi dan dikelola
- ·Menjelaskan aturan buang item yang paling lama tidak dipakai (LRU)
- ·Menerapkan pembaruan urutan pakai setiap kali item diakses
How It Works
- ·Sediakan tempat penyimpanan cepat dengan kapasitas terbatas.
- ·Tiap kali sebuah item dipakai, tandai ia sebagai yang paling baru.
- ·Item yang paling lama tidak disentuh menempati urutan buang berikutnya.
- ·Saat penuh dan ada item baru, singkirkan item paling lama tak dipakai untuk memberi ruang.
Prerequisites
- ·List atau antrian
- ·Konsep memori terbatas
Real-World Uses
- ·HP RAM kecil yang menutup aplikasi lama saat membuka game berat.
- ·Cache browser yang menyimpan halaman sering dibuka agar cepat.
- ·Riwayat aplikasi terakhir yang tersingkir saat memori menipis.
Complexity O(1) per akses