LRU cache: cara kerja, kode Python, dan kompleksitasnya

Masalah apa yang diselesaikan LRU cache

Cache menyimpan hasil operasi yang lambat, seperti query database, request web, atau komputasi mahal, sehingga permintaan berulang dijawab dengan cepat. Memori terbatas, jadi cache harus memutuskan apa yang dibuang saat penuh. LRU bertaruh bahwa data yang baru dipakai akan segera dipakai lagi, dan data yang lama tidak disentuh kemungkinan besar tidak. Taruhan ini berhasil untuk banyak beban kerja nyata, itulah sebabnya LRU dan pendekatannya muncul di CPU cache, page cache sistem operasi, database, web server, dan CDN.

Ide dasarnya: dua struktur bekerja bersama

Kita butuh dua hal yang cepat: menemukan sebuah key, dan mengetahui key mana yang paling lama tidak dipakai. Hash map saja tidak punya urutan. List saja lambat untuk dicari. Bersama-sama, keduanya bisa melakukan keduanya:

Pada get(key), cari node di map, pindahkan ke depan, dan kembalikan nilainya. Pada put(key, value), perbarui atau buat node di depan; jika cache kini melebihi kapasitas, hapus node di belakang dan hapus key-nya dari map.

Contoh langkah demi langkah dengan kapasitas 2

Implementasi Python dari nol

Node sentinel di head dan tail menghilangkan kasus khusus untuk list kosong: setiap node asli selalu punya node sebelum dan sesudahnya.

class Node:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head, self.tail = Node(), Node()   # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return None
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value):
        if key in self.map:
            self._unlink(self.map[key])
        node = self.map[key] = Node(key, value)
        self._push_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]

cache = LRUCache(2)
cache.put(1, "a")
cache.put(2, "b")
print(cache.get(1))   # a
cache.put(3, "c")     # evicts key 2
print(cache.get(2))   # None
cache.put(1, "A")
cache.put(4, "d")     # evicts key 3
print(cache.get(3), cache.get(1), cache.get(4))  # None A d

Versi singkat dengan OrderedDict

collections.OrderedDict sendiri adalah hash map yang digabung dengan doubly linked list, dan move_to_end serta popitem(last=False) bersifat O(1). Itu menjadikannya pilihan idiomatis di Python ketika Anda butuh LRU cache sebagai sebuah objek.

from collections import OrderedDict

class LRU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)          # mark as most recent
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # drop least recent

c = LRU(2)
c.put("x", 1)
c.put("y", 2)
c.get("x")
c.put("z", 3)
print(list(c.data))  # ['x', 'z']

Meng-cache hasil fungsi dengan functools.lru_cache

Untuk meng-cache nilai kembalian sebuah fungsi, gunakan dekorator functools.lru_cache. Argumen harus hashable, karena menjadi key dictionary. cache_info() menampilkan jumlah hit, miss, dan ukuran saat ini.

from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(80))           # 23416728348467685
print(fib.cache_info())
# CacheInfo(hits=78, misses=81, maxsize=128, currsize=81)

maxsize=None memberi cache tanpa batas, yang dilakukan functools.cache (Python 3.9 ke atas). Panggil fib.cache_clear() untuk mengosongkannya.

Kompleksitas waktu dan ruang

Varian, kesalahan, dan kapan memakai LRU

• LFU (least frequently used) membuang item dengan akses paling sedikit; ia melindungi item populer dari scan sekali jalan tetapi lebih kompleks.
• LRU aproksimasi: sistem seperti Redis mengambil sampel beberapa key dan membuang yang tertua di antaranya, alih-alih menjaga list yang tepat, sehingga menghemat memori.
• TTL cache menghapus entri setelah waktu tertentu, sering dikombinasikan dengan batas ukuran.
• Lupa memindahkan entri ke depan pada get, atau pada put untuk key yang sudah ada, mengubah LRU menjadi FIFO.
• Lupa menghapus key yang di-evict dari hash map meninggalkan entri menggantung dan membocorkan memori.
• Berbagi LRU cache antar thread membutuhkan lock di sekitar setiap operasi; functools.lru_cache aman dipanggil dari beberapa thread.

LRU adalah default yang baik ketika pemakaian terbaru memprediksi pemakaian mendatang. Ia buruk ketika scan besar sekali jalan mendorong keluar data yang sering dipakai; beban kerja seperti itu lebih cocok memakai LFU atau kebijakan yang tahan scan. Merancang LRU cache dengan operasi O(1) juga salah satu soal wawancara coding yang paling umum, karena menguji hash map dan linked list sekaligus.