Melaksanakan LRU Cache dengan Get dan Put O(1)

Kehendak Soalan dan Konteks Berkenaan

Laksanakan LRUCache(capacity) untuk integer positif capacity. Kunci dan nilai ialah integer bukan negatif. get(key) mengembalikan nilai yang disimpan atau -1 apabila kunci tiada. put(key, value) memasukkan atau mengemas kini kunci. get yang berjaya dan setiap put menjadikan kunci tersebut paling terkini digunakan. Memasukkan kunci baharu apabila cache penuh akan menyingkirkan tepat satu kunci yang paling lama tidak digunakan. Kedua-dua operasi awam mesti mengambil jangkaan masa O(1).

Ini merupakan soalan pengekodan struktur data, bukan reka bentuk cache teragih. Pelaksanaannya adalah proses tunggal dan bebenang tunggal (single-threaded); ia tidak merangkumi TTL, ketahanan (persistence), pemberat berasaskan saiz, atau akses serentak. “Jangkaan O(1)” bergantung pada andaian prestasi purata biasa untuk operasi jadual hash. Perubahan penuding dalam senarai berpaut ialah kes terburuk (worst-case) O(1).

Hasil yang penting bukanlah sekadar frasa “hash map ditambah doubly linked list.” Jawapan yang lengkap menerbitkan sebab kedua-dua struktur diperlukan, menyatakan batas tak varian (invariant) map–list, mengendalikan kemas kini kunci sedia ada tanpa penyingkiran tidak sengaja, dan mengesahkan susunan selepas setiap operasi.

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah menterjemahkan keperluan kepada operasi. Kunci mesti dicari tanpa pengimbasan, yang memerlukan hash map. Kekinian (recency) mesti menyokong pemindahan mana-mana padanan ke bahagian paling terkini dan membuang bahagian paling lama tidak digunakan. Doubly linked list boleh melakukan kedua-duanya dalam kerja penuding malar apabila map sudah menyediakan nod tersebut.

Isyarat kedua ialah sama ada kedua-dua struktur membentuk satu keadaan (state). Map tidak boleh menyimpan nilai sahaja; ia mesti memetakan setiap kunci kepada nod senarainya. Setiap nod senarai sebenar mesti mempunyai tepat satu entri map, dan setiap entri map mesti menuding kepada tepat satu nod sebenar dalam senarai. Oleh itu, penyingkiran membuang kunci yang sama daripada kedua-dua struktur.

Isyarat ketiga ialah disiplin penuding. Nod dami kepala dan ekor (dummy head and tail) menjadikan semua nod sebenar sebagai nod dalaman. Pemisahan (detach) dan penyisipan tidak memerlukan kes khas untuk entri pertama, terakhir, atau satu-satunya entri. Calon sepatutnya boleh menyatakan bahagian mana yang paling terkini sebelum mengekod dan mengekalkan konvensi tersebut tanpa perubahan.

Akhir sekali, penemu duga mencari ujian yang mendedahkan susunan, bukan hanya nilai yang dikembalikan. Mengemas kini kunci sedia ada pada kapasiti penuh, membaca satu kunci berulang kali, menggunakan kapasiti satu, dan memasukkan selepas kegagalan carian (miss) akan mendedahkan pepijat yang terlepas daripada satu contoh laluan mudah (happy-path).

Soalan untuk Dijelaskan Sebelum Menjawab

• Adakah get mengemas kini kekinian? Dalam kontrak ini, ya. peek baca sahaja akan menjadi operasi yang berbeza dan tidak akan memindahkan nod.
• Adakah mengemas kini kunci sedia ada menggunakan kapasiti? Tidak. put menukar nilai dan kekinian entri yang sama; ia tidak boleh menyingkirkan kunci lain.
• Apakah yang dikembalikan oleh kegagalan carian (miss)? Masalah ini menggunakan -1, jadi nilai harus dikekang sewajarnya atau API harus mengembalikan nilai pilihan. Di sini nilai adalah integer bukan negatif dan -1 dikhaskan untuk kegagalan carian.
• Adakah kapasiti sifar sah? Pelaksanaan ini menolak kapasiti bukan positif. Menyokong sifar memerlukan setiap penyisipan hilang serta-merta dan mengubah kontrak pembina (constructor).
• Adakah jaminan mestilah kes terburuk ketat O(1)? Jadual hash biasanya memberikan jangkaan masa malar. Jaminan kes terburuk yang ketat memerlukan struktur carian yang berbeza atau andaian yang lebih kuat.
• Bolehkah ordered map standard digunakan? Ia mungkin boleh diterima dalam pengeluaran atau latihan ringkas, tetapi penemu duga masih boleh meminta pelaksanaan senarai berpaut dasar dan batas tak variannya.
• Adakah keselamatan bebenang (thread safety) diperlukan? Tidak. Jika ia ditambah, ingat bahawa get mengubah kekinian, jadi ia adalah operasi tulis untuk tujuan penyegerakan.

Rangka Jawapan 30 Saat

“Saya memerlukan carian jangkaan masa malar dan kemas kini kekinian, jadi saya akan memetakan setiap kunci kepada nod dalam doubly linked list. Bahagian kepala adalah paling terkini dan bahagian ekor paling lama tidak digunakan; nod sentri (sentinels) menjadikan pemisahan dan penyisipan seragam. Padanan atau kemas kini memindahkan nodnya ke hadapan. Penyisipan baharu melebihi kapasiti akan membuang tail.prev daripada kedua-dua struktur. Oleh kerana map dan senarai mengandungi nod sebenar yang sama, get dan put adalah jangkaan O(1), dengan ruang O(capacity).”

Jawapan Mendalam Langkah demi Langkah

Senarai sahaja mengekalkan kekinian, tetapi mencari kunci atau membuang entri sembarangan menelan kos O(n). Map sahaja mencari nilai dengan pantas, tetapi ia tidak dapat mengenal pasti kunci yang paling lama tidak digunakan tanpa mengimbas atau menyimpan struktur susunan kedua. Tatasusunan (array) ditambah map masih mempunyai anjakan O(n) atau penemuan nod sebelumnya. Kedua-dua keperluan tersebut memaksa penggunaan indeks carian dan susunan boleh ubah.

Gunakan orientasi ini sepanjang jawapan:

head <-> most recent <-> ... <-> least recent <-> tail

Nod sentri tidak pernah dimasukkan ke dalam map dan tidak pernah dikira dalam kapasiti. Setiap nod sebenar menyimpan key, value, prev, dan next; penyimpanan kunci adalah perlu kerana penyingkiran bermula dari tail.prev dan mesti memadamkan entri map yang sepadan tanpa pengimbasan terbalik.

Empat batas tak varian (invariants) menjadikan pelaksanaan ini mudah disemak:

1. head.next ialah nod sebenar yang paling terkini digunakan, dan tail.prev ialah nod sebenar yang paling lama tidak digunakan apabila cache tidak kosong.
2. Kunci map dan nod senarai sebenar menerangkan set entri yang sama, satu-dengan-satu.
3. Untuk setiap pasangan bersebelahan, left.next is right dan right.prev is left.
4. Selepas setiap operasi awam, 0 <= len(nodes) <= capacity.

Pelaksanaan ini mengekalkan manipulasi penuding dalam dua fungsi pembantu kerana kedua-dua get dan put menggunakannya semula secara langsung:

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

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


class LRUCache:
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("capacity must be positive")

        self.capacity = capacity
        self.nodes = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _detach(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _attach_after_head(self, node: Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _mark_recent(self, node: Node) -> None:
        self._detach(node)
        self._attach_after_head(node)

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1

        self._mark_recent(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._mark_recent(node)
            return

        node = Node(key, value)
        self.nodes[key] = node
        self._attach_after_head(node)

        if len(self.nodes) > self.capacity:
            victim = self.tail.prev
            self._detach(victim)
            del self.nodes[victim.key]

Susunan penetapan penuding dalam _attach_after_head adalah penting. Nod baharu terlebih dahulu menangkap nod pertama lama, kemudian nod lama tersebut menunjuk kembali ke nod baharu, dan hanya selepas itu head.next berubah. Menulis ganti head.next terlalu awal boleh kehilangan jiran yang masih memerlukan prev dikemas kini.

Ketepatan dicapai secara induksi ke atas operasi. Permulaan (initialization) memenuhi keempat-empat batas tak varian. Kegagalan carian tidak mengubah apa-apa. Padanan carian atau kemas kini kunci sedia ada memisahkan satu nod yang dipetakan dan memasukkan semula nod yang sama di hadapan, jadi keahlian dan saiz tidak berubah. Penyisipan baharu menambah nod pada kedua-dua struktur; jika saiz menjadi capacity + 1, membuang tail.prev daripada senarai dan kuncinya daripada map akan memulihkan set satu-dengan-satu dan had kapasiti. Kapasiti positif memastikan mangsa penyingkiran ialah nod sebenar.

Dengan kapasiti dua, surihan put(1,10), put(2,20), get(1), put(3,30), put(1,15) menghasilkan susunan kekinian [1], [2,1], [1,2], [3,1], [1,3]. Kunci 2 disingkirkan, manakala mengemas kini kunci 1 menukar nilainya tanpa menyingkirkan kunci 3.

Di bawah prestasi purata jadual hash, setiap kaedah awam melakukan satu carian ditambah bilangan tetap operasi penuding dan map, jadi jangkaan masa ialah O(1). Map dan senarai mengandungi paling banyak capacity nod sebenar, jadi ruang ialah O(capacity). Ini bukan jaminan jadual hash kes terburuk yang ketat.

Pengesahan harus menggabungkan surihan contoh dengan semakan batas tak varian. Uji kegagalan carian cache kosong, kapasiti sifar yang ditolak, kapasiti satu, nilai berulang di bawah kunci berbeza, kemas kini pada kapasiti penuh, padanan berulang, penyingkiran berselang-seli, dan aliran operasi rawak yang panjang. Untuk ujian rawak, bandingkan hasil dan susunan dengan model rujukan O(n) yang mudah dan selepas setiap operasi lakukan penegasan (assert) pada penuding salingan, tiada nod pendua, kesamarataan map–senarai, dan had kapasiti.

Access-ordered map boleh menyatakan dasar yang sama dengan lebih padat apabila penggunaan pustaka dibenarkan. LinkedHashMap Java menyokong access order dan cangkuk penyingkiran entri tertua (eldest-entry). Itu adalah pilihan pengeluaran yang berguna, tetapi ia tidak menggantikan pembuktian temu duga. Asingkan juga LRU dalam proses yang tepat daripada penyingkiran pengeluaran: pelayan mungkin menggunakan LRU anggaran berasaskan sampel untuk mengurangkan metadata global dan pertikaian (contention).

Contoh Jawapan Berkualiti Tinggi

“Saya akan menetapkan kontrak terlebih dahulu: kapasiti positif, get mengembalikan -1 apabila gagal ditemui, dan setiap padanan atau put mengemas kini kekinian. Mengemas kini kunci sedia ada tidak menambah saiz. Sasarannya ialah jangkaan O(1), berdasarkan carian jadual hash purata.

Hash map menyelesaikan carian kunci tetapi bukan susunan penyingkiran. Doubly linked list menyelesaikan susunan dan membolehkan saya menyisih nod sembarangan dalam kerja penuding malar, dengan syarat saya sudah mempunyai nod tersebut. Oleh itu, saya menyimpan key -> node dalam map dan menyusun nod daripada paling terkini selepas dummy head kepada paling lama tidak digunakan sebelum dummy tail. Nod menyimpan kuncinya supaya penyingkiran pada ekor juga boleh memadamkan entri map.

Batas tak varian utama ialah map dan nod senarai sebenar adalah set yang sama. Apabila padanan berlaku, saya memisahkan nod tersebut dan memasukkannya selepas kepala. Semasa kemas kini, saya menukar nilainya dan melakukan langkah pemindahan yang sama. Pada put baharu, saya menambahkannya pada kedua-dua struktur; jika saiz melebihi kapasiti, saya membuang tail.prev daripada kedua-duanya. Nod sentri menjadikan operasi ini serupa untuk entri pertama, terakhir, dan satu-satunya entri.

Saya akan menguji kapasiti satu, kemas kini semasa penuh, get berulang yang menukar mangsa penyingkiran, dan kegagalan carian yang tidak boleh mengubah susunan. Saya juga akan menyusuri senarai selepas setiap operasi rawak dan membandingkannya dengan model rujukan yang perlahan. Kerumitan akhir ialah jangkaan O(1) bagi setiap operasi dan ruang O(capacity).”

Kesilapan Biasa

• Menyimpan nilai sahaja dalam map → padanan masih perlu mencari struktur susunan → petakan setiap kunci terus kepada nod senarainya.
• Menggunakan singly linked list → map menyediakan nod tetapi bukan nod sebelumnya (predecessor), jadi penyingkiran sembarangan mungkin memerlukan pengimbasan → simpan kedua-dua prev dan next.
• Terlupa kunci di dalam setiap nod → penyingkiran ekor tidak dapat membuang entri map tanpa carian terbalik → simpan kedua-dua kunci dan nilai dalam nod.
• Menganggap susunan penyisipan sebagai kekinian → get yang berjaya kemudiannya gagal menukar mangsa penyingkiran masa hadapan → pindahkan setiap padanan ke bahagian paling terkini.
• Menyingkirkan entri semasa mengemas kini kunci sedia ada → saiz tidak bertambah, jadi entri lain yang tidak berkaitan hilang → kendalikan kemas kini dan kembali sebelum semakan kapasiti entri baharu.
• Membuang mangsa daripada satu struktur sahaja → entri map lapuk atau nod senarai hantu merosakkan operasi seterusnya → lakukan penyingkiran secara simetri dan uji kesamarataan map–senarai.
• Menulis cabang berasingan untuk kepala, ekor, dan entri tunggal → kes penuding berganda dan salah satu sempadan akhirnya akan menyimpang → gunakan dua nod sentri kekal.
• Mendakwa O(1) kes terburuk yang ketat → jadual hash secara amnya memberikan had jangkaan dan prestasinya boleh merosot di bawah perlanggaran (collisions) → nyatakan andaian fungsi hashing.
• Menguji nilai pulangan sahaja → nilai yang betul boleh menyembunyikan susunan yang rosak sehinggalah penyingkiran berlaku kemudian → tegaskan (assert) jujukan kekinian penuh dan batas tak varian penuding.

Soalan Susulan dan Maklum Balas

Susulan 1: Bagaimanakah anda menjadikannya selamat untuk bebenang (thread-safe)?

get ialah operasi tulis kerana ia mengubah senarai. Sambungan betul yang paling mudah adalah dengan meletakkan satu mutex di sekeliling keseluruhan get atau put, memastikan kemas kini map dan senarai adalah atomik. Penguncian baca–tulis (read–write locking) tidak menjadikan padanan carian biasa sebagai pembaca. Pembahagian (sharding) mengurangkan pertikaian, tetapi setiap bahagian kemudiannya mempunyai susunan LRU tersendiri; ia tidak lagi melaksanakan satu LRU global yang tepat melainkan mekanisme susunan dikongsi diperkenalkan semula.

Susulan 2: Bagaimanakah anda menambah tamat tempoh TTL?

TTL dan kekinian ialah peraturan penyingkiran yang berasingan. Padanan carian mesti terlebih dahulu menolak entri yang telah tamat tempoh, manakala put mungkin perlu membuang entri tamat tempoh sebelum menggunakan dasar kapasiti. Min-heap untuk masa tamat tempoh menyokong pembersihan malas (lazy cleanup) tetapi menambah penyelenggaraan O(log n) dan rekod heap yang lapuk; timing wheel mengubah kejituan dan pelaksanaan. Jangan terus mendakwa kedua-dua operasi adalah O(1) tanpa mentakrifkan semula mekanisme tamat tempoh dan had batasnya.

Susulan 3: Bolehkah anda menyediakan O(1) kes terburuk yang ketat?

Bahagian senarai berpaut sudah mempunyai bilangan operasi penuding malar yang ketat. Bahagian carian bergantung pada jaminan jadual hash. Mencapai carian malar kes terburuk yang ketat memerlukan model kamus yang lebih kukuh, semesta kunci terhad dengan pengalamatan terus, atau andaian hashing khusus. Dalam hash map bahasa pengaturcaraan biasa, terangkan hasilnya sebagai jangkaan atau terpelunasan (amortized) O(1) mengikut kontrak pelaksanaan tersebut.

Susulan 4: Mengapa tidak menggunakan LinkedHashMap atau OrderedDict?

Gunakan pustaka apabila semantik susunan akses dan penyingkirannya sepadan dengan produk dan kod penuding manual tidak membawa nilai tambah. Dalam temu duga, terangkan batas tak varian map dan senarai susunan terlebih dahulu, kemudian tawarkan alternatif pustaka. Sahkan sama ada pengemaskinian, pembacaan, lelaran, dan penyingkiran entri tertua dikira sebagai akses; map tersusun dengan nama yang serupa tidak semuanya berkongsi semantik kekinian yang serupa.

Susulan 5: Adakah anda akan menggunakan LRU tepat dalam pelayan cache yang besar?

Tidak secara automatik. Mengekalkan satu susunan akses global yang tepat menambah penulisan metadata dan titik pertikaian pada setiap padanan carian. Cache pengeluaran mungkin membahagikan susunan (shard), mengambil sampel kunci calon, atau memilih LFU apabila kekerapan meramalkan penggunaan semula dengan lebih baik. Pilihan tersebut menukar ketepatan pemilihan mangsa demi memori dan daya pemprosesan (throughput). Objek temu duga ini kekal berguna kerana ia menjadikan dasar tepat dan batas tak variannya boleh diuji.