LRU Cache

Q: Bisakah kamu membuat cache LRU dengan dictionary terurut?

Ya. Map yang mempertahankan urutan penyisipan, seperti OrderedDict dari Python atau LinkedHashMap dari Java, dapat menggantikan list: pindahkan key ke bagian akhir setiap kali digunakan dan keluarkan dari bagian depan, tetap dalam O(1). Pewawancara biasanya menginginkan list yang dibuat secara manual.

SedangHashing Linked list

+10

Buat cache yang menampung paling banyak capacity kunci. get key mengembalikan nilai kunci tersebut, atau -1 jika kunci itu tidak ada di cache. put key value menyimpan nilai tersebut dan menggantikan nilai sebelumnya; jika kuncinya baru dan cache penuh, cache akan menghapus kunci yang paling lama tidak digunakan terlebih dahulu. Get yang menemukan kuncinya dan setiap put dihitung sebagai penggunaan.

Operasi i adalah ops[i] ("get" atau "put") pada kunci keys[i], dengan nilai values[i] (0 untuk get). Jalankan operasi secara berurutan pada cache kosong dan kembalikan satu string untuk setiap operasi: "null" untuk put, nilai atau "-1" untuk get.

Fungsi

lruCacheOps(capacity: integer, ops: string-array, keys: integer-array, values: integer-array) → string-array

capacityinteger: jumlah maksimum key yang dapat ditampung cache sekaligus
opsstring-array: operasi-operasi, sesuai urutan eksekusinya
keysinteger-array: kunci yang digunakan setiap operasi
valuesinteger-array: nilai untuk setiap put, 0 untuk setiap get
Mengembalikanstring-array: satu jawaban per operasi, dalam bentuk teks

Batasan

1 ≤ capacity ≤ 3000
1 ≤ ops.length ≤ 3000
keys.length == values.length == ops.length
Setiap ops[i] adalah get atau put.
0 ≤ keys[i] ≤ 10⁹
0 ≤ values[i] ≤ 10⁹ untuk operasi put, dan values[i] == 0 untuk operasi get.

Contoh

Input: capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
Output: ["null", "null", "10", "null", "-1", "30"]
Penjelasan: get menjadikan key 1 sebagai yang paling baru digunakan, sehingga put 3 mengeluarkan key 2: get 2 menghasilkan "-1" dan get 3 menghasilkan "30".

Input: capacity = 2ops = ["put", "put", "put", "put", "get", "get", "get"]keys = [5, 6, 5, 7, 5, 6, 7]values = [1, 2, 3, 4, 0, 0, 0]
Output: ["null", "null", "null", "null", "3", "-1", "4"]
Penjelasan: Pembaruan ketiga mengubah key 5, yang sudah tersimpan di cache: tidak ada yang dikeluarkan dan key 5 menjadi yang paling baru digunakan. Jadi, put 7 mengeluarkan key 6, bukan key 5.

Input: capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
Output: ["-1", "null", "0", "null", "-1", "8"]
Penjelasan: Dengan kapasitas satu key, setiap key baru mengusir key sebelumnya. Pemanggilan get pertama menghasilkan cache miss karena cache kosong. Setelah itu, key 0 menyimpan nilai 0 yang sebenarnya sampai put 8 mengusirnya.

Pertanyaan lanjutan

Bagaimana kamu akan mengubah cache agar menghapus key yang paling jarang digunakan, dengan memecahkan seri berdasarkan penggunaan yang paling lama, tetap dalam O(1) untuk setiap operasi?

Solusi

Operasi get harus menemukan key dengan cepat, dan operasi eviction harus menemukan key yang paling lama tidak digunakan dengan cepat. Hash map melakukan yang pertama, sedangkan list yang diurutkan berdasarkan penggunaan melakukan yang kedua. Gunakan keduanya: petakan setiap key ke node-nya dalam doubly linked list yang diurutkan berdasarkan penggunaan.

Pindai tabel entri beserta waktu terakhir digunakan

Intuisi

Simpan hingga capacity entri dalam array: key, value, dan stempel penggunaan terakhir dari pencacah yang bertambah pada setiap operasi. Key baru pada cache penuh akan menimpa entri dengan stempel terkecil, yaitu key yang paling lama tidak digunakan. Pada contoh pertama, saat put 3, key 1 memiliki stempel 3 dan key 2 memiliki stempel 2, jadi key 2 yang akan dihapus.

Setiap operasi memindai hingga capacity entri: O(n × capacity) untuk n operasi, jutaan perbandingan untuk 3.000 operasi pada cache dengan 1.500 key.

Algoritma

Pertahankan array keys, values dan used, jumlah isian, serta jam yang dimulai dari 0.
Setiap operasi menambahkan 1 ke jam dan memindai entri yang terisi untuk mencari kuncinya.
get: jika tidak ditemukan, kembalikan -1; jika ditemukan, atur used ke nilai jam dan kembalikan nilainya.
put: jika ditemukan, simpan nilai dan nilai jam. Jika tidak ditemukan, tulis kunci, nilai, dan nilai jam ke entri kosong, atau ke entri dengan used terkecil.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        # Entry i holds keys[i] -> values[i] and was last used at time used[i].
        self.keys = [0] * capacity
        self.values = [0] * capacity
        self.used = [0] * capacity
        self.size = 0
        self.time = 0

    def _find(self, key):
        for i in range(self.size):
            if self.keys[i] == key:
                return i
        return -1

    def get(self, key):
        self.time += 1
        i = self._find(key)
        if i == -1:
            return -1
        self.used[i] = self.time
        return self.values[i]

    def put(self, key, value):
        self.time += 1
        i = self._find(key)
        if i == -1:
            if self.size < self.capacity:
                i = self.size
                self.size += 1
            else:
                # Full: scan for the entry used longest ago and take its place.
                i = 0
                for j in range(1, self.capacity):
                    if self.used[j] < self.used[i]:
                        i = j
            self.keys[i] = key
        self.values[i] = value
        self.used[i] = self.time

def lruCacheOps(capacity, ops, keys, values):
    cache = LRUCache(capacity)
    result = []
    for op, key, value in zip(ops, keys, values):
        if op == "put":
            cache.put(key, value)
            result.append("null")
        else:
            result.append(str(cache.get(key)))
    return result

Hash map ditambah list tertaut ganda

Intuisi

Setiap node list terhubung ke kedua tetangganya, jadi saat memegang node tersebut, kamu bisa melepaskannya atau menyisipkannya di bagian depan dengan mengubah empat tautan. Map memberikan node tersebut kepadamu, jadi tidak ada operasi yang menelusuri list.

Get yang berhasil, atau put untuk key yang sudah di-cache, memindahkan node ke bagian depan. Key baru saat cache penuh menghapus node bagian belakang dan menghapus key-nya dari map, itulah sebabnya setiap node menyimpan key-nya sendiri. Node sentinel head dan tail tetap berada di ujung, jadi pelepasan dan penyisipan tidak pernah memeriksa apakah tetangganya tidak ada. Setiap operasi terdiri dari satu pencarian ditambah beberapa perubahan tautan: O(1).

Algoritma

Hubungkan sentinel head dan tail; mulai dengan map kosong dari key ke node.
get key: kembalikan -1 jika key tidak ada di map; jika tidak, pindahkan node-nya ke setelah head dan kembalikan nilainya.
put untuk key yang tersimpan di cache: simpan nilainya dan pindahkan node ke setelah head.
put untuk key baru: jika map menyimpan capacity key, lepaskan node sebelum tail dan hapus key-nya dari map. Sisipkan node baru setelah head dan petakan key ke node tersebut.

class ListNode:
    __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):
        self.capacity = capacity
        self.nodes = {}            # key -> its node in the list
        # Sentinels: head.next is the most recently used node,
        # tail.prev the least recently used one.
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

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

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

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

    def put(self, key, value):
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
        else:
            if len(self.nodes) == self.capacity:
                # Full: drop the least recently used node.
                oldest = self.tail.prev
                self._unlink(oldest)
                del self.nodes[oldest.key]
            node = ListNode(key, value)
            self.nodes[key] = node
        self._push_front(node)

def lruCacheOps(capacity, ops, keys, values):
    cache = LRUCache(capacity)
    result = []
    for op, key, value in zip(ops, keys, values):
        if op == "put":
            cache.put(key, value)
            result.append("null")
        else:
            result.append(str(cache.get(key)))
    return result

Jebakan dan kasus tepi

Tidak memindahkan key ke depan saat get menemukan cache. Pada contoh pertama, put 3 kemudian akan mengeluarkan key 1, bukan key 2.
Mengeluarkan item sebelum memeriksa apakah key ada di cache. Dengan kapasitas 2, put 1, put 2, put 2 akan mengeluarkan key 1.
Melepas tautan node tetapi membiarkan key-nya tetap ada di map, atau sebaliknya. Map kemudian mengembalikan node yang sudah terlepas, dan memindahkannya merusak tautan tetangga lamanya.
Menganggap 0 yang tersimpan sebagai cache miss. Pada contoh ketiga, get 0 harus mengembalikan "0".

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu cache LRU?

Dengan hash map dan linked list ganda, get dan put berjalan dalam O(1): satu pencarian ditambah beberapa perubahan tautan. Penggunaan ruangnya O(capacity), satu node dan satu entri map untuk setiap key.

Mengapa cache LRU menggunakan doubly linked list?

Cache memindahkan key dari posisi mana pun dalam urutan ke bagian depan dan membuang key di bagian belakang. Doubly linked list melakukan keduanya dengan beberapa perubahan tautan karena setiap node mengetahui node sebelumnya. Singly linked list perlu menelusuri dari head untuk menemukan node tersebut, yang membutuhkan O(capacity).

Bisakah kamu membuat cache LRU dengan dictionary terurut?

Ya. Map yang mempertahankan urutan penyisipan, seperti OrderedDict dari Python atau LinkedHashMap dari Java, dapat menggantikan list: pindahkan key ke bagian akhir setiap kali digunakan dan keluarkan dari bagian depan, tetap dalam O(1). Pewawancara biasanya menginginkan list yang dibuat secara manual.

def lruCacheOps(capacity, ops, keys, values):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

capacity = 2
ops = ["put", "put", "get", "put", "get", "get"]
keys = [1, 2, 1, 3, 2, 3]
values = [10, 20, 0, 30, 0, 0]

Output yang diharapkan

["null", "null", "10", "null", "-1", "30"]