LRU Cache

Q: Sıralı bir sözlükle LRU önbelleği oluşturabilir misin?

Evet. Python'daki OrderedDict veya Java'daki LinkedHashMap gibi ekleme sırasını koruyan bir harita listenin yerini alabilir: her kullanımda bir anahtarı sona taşıyın ve baştan çıkarın; işlem yine O(1) olur. Mülakat yapanlar genellikle listenin elle oluşturulmasını ister.

OrtaHashing Bağlı liste

+10

En fazla capacity anahtar tutan bir önbellek oluştur. get key anahtarın değerini, önbelleğe alınmamışsa -1 değerini döndürür. put key value değeri kaydeder ve varsa eski değerin üzerine yazar; anahtar yeniyse ve önbellek doluysa önce en uzun süredir kullanılmayan anahtarı çıkarır. Anahtarını bulan bir get işlemi ve her put işlemi kullanım sayılır.

i işlemi, keys[i] anahtarı üzerinde ops[i] ("get" veya "put") işlemidir; değeri values[i] olur (get işlemi için 0). İşlemleri boş bir önbellekte sırasıyla çalıştır ve her işlem için bir dizge döndür: put için "null", get için değer veya "-1".

Fonksiyon

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

capacityinteger: önbelleğin aynı anda tutabileceği en fazla anahtar sayısı
opsstring-array: işlemler, çalıştırıldıkları sırayla
keysinteger-array: her işlemin üzerinde çalıştığı anahtar
valuesinteger-array: her put için değer, her get için 0
Döndürürstring-array: işlem başına metin olarak bir yanıt

Kısıtlar

1 ≤ capacity ≤ 3000
1 ≤ ops.length ≤ 3000
keys.length == values.length == ops.length
Her ops[i] ya get ya da put değeridir.
0 ≤ keys[i] ≤ 10⁹
0 ≤ values[i] ≤ 10⁹ bir put işlemi için ve values[i] == 0 bir get işlemi için.

Örnekler

Girdi: capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
Çıktı: ["null", "null", "10", "null", "-1", "30"]
Açıklama: get, key 1'i en son kullanılan yapar; bu yüzden put 3, key 2'yi çıkarır: get 2, "-1" döndürür ve get 3, "30" döndürür.

Girdi: 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]
Çıktı: ["null", "null", "null", "null", "3", "-1", "4"]
Açıklama: Üçüncü put işlemi, zaten önbelleğe alınmış olan 5 anahtarını günceller: hiçbir şey önbellekten çıkarılmaz ve 5 anahtarı en son kullanılan olur. Bu yüzden put 7, 5 anahtarını değil 6 anahtarını önbellekten çıkarır.

Girdi: capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
Çıktı: ["-1", "null", "0", "null", "-1", "8"]
Açıklama: Tek bir anahtar için yer olduğundan, eklenen her yeni anahtar öncekinin yerini alır. Önbellek boşken ilk get başarısız olur; ardından anahtar 0, put 8 onu önbellekten çıkarana kadar gerçek değer 0'ı tutar.

Ek soru

Önbelleği, eşitlikleri en son kullanım zamanına göre bozarak en az kullanılan anahtarı çıkaracak şekilde ve her işlem başına yine O(1) sürede nasıl değiştirirdin?

Çözüm

Bir get işlemi anahtarı hızlıca bulmalı, çıkarma işlemi de en uzun süredir kullanılmamış anahtarı hızlıca bulmalıdır. İlkini bir hash haritası, ikincisini kullanım sırasına göre tutulan bir liste yapar. İkisini de kullan: her anahtarı, kullanım sırasına göre düzenlenmiş çift bağlı listedeki düğümüyle eşle.

Son kullanma zamanlarına sahip girişlerden oluşan bir tabloyu tara

Sezgi

Dizilerde en fazla capacity kayıt tut: anahtar, değer ve her işlemde artan bir sayaçtan alınan son kullanım damgası. Dolu bir önbelleğe yeni bir anahtar eklendiğinde, damgası en küçük olan, yani en uzun süredir kullanılmamış kayıt üzerine yazılır. İlk örnekte, put 3 sırasında 1. anahtarın damgası 3, 2. anahtarın damgası 2 olduğundan 2. anahtar çıkar.

Her işlem en fazla capacity kaydı tarar: n işlem için O(n × capacity); 1.500 anahtarlı bir önbellekte 3.000 işlemde milyonlarca karşılaştırma yapılır.

Algoritma

keys, values ve used dizilerini, bir doluluk sayısını ve 0 değerinde bir saati tutun.
Her işlem saate 1 ekler ve anahtarını bulmak için dolu girdileri tarar.
get: eşleşme yoksa -1 döndürün; eşleşme varsa used değerini saate ayarlayın ve değeri döndürün.
put: eşleşme varsa değeri ve saati kaydedin. Eşleşme yoksa anahtarı, değeri ve saati boş bir girdiye ya da used değeri en küçük olan girdiye yazın.

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 ve çift bağlı liste

Sezgi

Her liste düğümü iki komşusuna da bağlıdır; bu nedenle düğümü elinizde tuttuğunuzda dört bağlantıyı değiştirerek onu listeden çıkarabilir veya başa ekleyebilirsiniz. Harita size düğümü verir, bu yüzden hiçbir işlem liste boyunca ilerlemez.

Bir get isabeti veya önbelleğe alınmış bir anahtara yapılan put, düğümü başa taşır. Önbellek doluyken yeni bir anahtar eklemek, sondaki düğümü kaldırır ve anahtarını haritadan siler; her düğümün kendi anahtarını saklamasının nedeni budur. head ve tail bekçi düğümleri uçlarda kalır, böylece listeden çıkarma ve ekleme işlemleri eksik bir komşuyu kontrol etmez. Her işlem bir arama ve birkaç bağlantı değişikliğinden oluşur: O(1).

Algoritma

head ve tail nöbetçilerini birbirine bağla; anahtardan düğüme giden boş bir eşleme başlat.
get key: Anahtar eşlemede yoksa -1 döndür; aksi takdirde düğümünü head'den sonra taşı ve değerini döndür.
Önbelleğe alınmış bir anahtar için put: değeri kaydet ve düğümü head'den sonra taşı.
Yeni bir anahtar için put: Eşleme capacity sayıda anahtar içeriyorsa tail'den önceki düğümün bağlantısını kaldır ve anahtarını eşlemeden sil. head'den sonra yeni bir düğüm ekle ve anahtarı bu düğümle eşle.

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

Tuzaklar ve uç durumlar

Bir get isabetinde anahtarı öne taşımamak. İlk örnekte put 3, 2. anahtar yerine 1. anahtarı çıkarır.
Anahtarın önbellekte olup olmadığını kontrol etmeden önce çıkarma işlemi yapmak. Kapasite 2 iken put 1, put 2, put 2 sırasıyla 1. anahtar çıkarılır.
Bir düğümün bağlantısını kaldırıp anahtarını eşlemede bırakmak ya da bunun tersini yapmak. Bu durumda eşleme, bağlantısı kopmuş bir düğüm döndürür ve onu taşımak eski komşularının bağlantılarını bozar.
Saklanan 0 değerini önbellekte yok olarak değerlendirmek. Üçüncü örnekte get 0, "0" döndürmelidir.

Sıkça sorulan sorular3

LRU önbelleğinin zaman karmaşıklığı nedir?

Bir karma haritası ve çift bağlı listeyle, get ve put işlemlerinin ikisi de O(1) sürede çalışır: bir arama ve birkaç bağlantı değişikliği. Alan kullanımı O(capacity) kadardır; her anahtar için bir düğüm ve bir harita girdisi bulunur.

Bir LRU önbelleği neden çift yönlü bağlı liste kullanır?

Önbellek, anahtarları sıralamadaki herhangi bir yerden başa taşır ve sondaki anahtarı çıkarır. Çift bağlı liste, her düğüm kendisinden önceki düğümü bildiği için birkaç bağlantı değişikliğiyle her ikisini de yapar. Tek bağlı listede bu düğümü bulmak için baştan itibaren ilerlemek gerekir; bu da O(capacity) sürer.

Sıralı bir sözlükle LRU önbelleği oluşturabilir misin?

Evet. Python'daki OrderedDict veya Java'daki LinkedHashMap gibi ekleme sırasını koruyan bir harita listenin yerini alabilir: her kullanımda bir anahtarı sona taşıyın ve baştan çıkarın; işlem yine O(1) olur. Mülakat yapanlar genellikle listenin elle oluşturulmasını ister.

def lruCacheOps(capacity, ops, keys, values):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı

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