LRU Cache

Q: 順序付き辞書を使ってLRUキャッシュを構築できますか？

はい。Python の OrderedDict や Java の LinkedHashMap のように挿入順を保持するマップは、リストの代わりに使えます。使用するたびにキーを末尾に移動し、先頭から削除すれば、引き続き O(1) で処理できます。面接では通常、リストを自分で実装することが求められます。

ふつうハッシュ連結リスト

+10

最大で capacity 個のキーを保持するキャッシュを作成します。get key はキーの値を返し、キャッシュされていない場合は -1 を返します。put key value は値を保存し、以前の値があれば置き換えます。キーが新しく、キャッシュがいっぱいの場合は、最も長く使われていないキーを最初に削除します。キーが見つかった get と、すべての put は使用としてカウントされます。

操作 i は、キー keys[i] に対する ops[i] ("get" または "put") で、値は values[i] です（get の場合は 0）。空のキャッシュに対して順番に実行し、それぞれ1つの文字列を返します。put の場合は "null"、get の場合は値または "-1" です。

関数

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

capacityinteger: キャッシュが一度に保持できるキーの最大数
opsstring-array: 演算を、実行される順に
keysinteger-array: 各操作が作用するキー
valuesinteger-array: put 1回ごとに値を1つ、get 1回ごとに0
戻り値string-array: 操作ごとに1つの回答をテキストとして

制約

1 ≤ capacity ≤ 3000
1 ≤ ops.length ≤ 3000
keys.length == values.length == ops.length
各ops[i]はgetまたはputです。
0 ≤ keys[i] ≤ 10⁹
0 ≤ values[i] ≤ 10⁹ は put の場合、values[i] == 0 は get の場合です。

例

入力: capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
出力: ["null", "null", "10", "null", "-1", "30"]
説明: get によってキー 1 が最も最近使用されたものになるため、put 3 はキー 2 を追い出します。get 2 は "-1" を返し、get 3 は "30" を返します。

入力: 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]
出力: ["null", "null", "null", "null", "3", "-1", "4"]
説明: 3回目のputでは、すでにキャッシュされているキー5が更新されます。何も追い出されず、キー5が最も最近使用されたものになります。したがって、put 7ではキー5ではなくキー6が追い出されます。

入力: capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
出力: ["-1", "null", "0", "null", "-1", "8"]
説明: キーを1つしか保持できないため、新しいキーが追加されるたびに、その前のキーが追い出されます。空のキャッシュで最初の get はミスし、その後、キー 0 は put 8 によって追い出されるまで、実際の値 0 を保持します。

発展問題

代わりに、最も使用頻度の低いキーを削除するようにキャッシュを変更し、同じ頻度の場合は最も長い間使用されていないキーを削除するにはどうすればよいでしょうか？操作ごとの計算量は引き続き O(1) とします。

解説

get はキーを素早く見つける必要があり、追い出しでは最も最近使われていないキーを素早く見つける必要があります。前者にはハッシュマップ、後者には使用順に並べたリストを使います。両方を使いましょう。各キーを、使用順に並んだ二重連結リスト内のノードに対応付けます。

最終使用時刻が記録されたエントリのテーブルをスキャンする

考え方

配列に最大capacity件のエントリを保存します。キー、値、そして操作のたびに増えるカウンターの最終使用時刻です。満杯のキャッシュに新しいキーを追加すると、スタンプが最小のエントリ、つまり最も長い間使われていないキーを上書きします。最初の例では、put 3の時点でキー1のスタンプは3、キー2のスタンプは2なので、キー2が削除されます。

すべての操作で最大capacity件のエントリを走査します。n回の操作に対してO(n × capacity)となり、1,500個のキーを持つキャッシュで3,000回操作すると、比較回数は数百万回になります。

アルゴリズム

配列 keys、values、used、格納数、および初期値0のカウンターを保持します。
各操作でカウンターを1増やし、そのキーを持つ格納済みエントリを検索します。
get: 見つからなければ -1 を返し、見つかった場合は used にカウンターの値を設定して、値を返します。
put: 見つかった場合は、値とカウンターの値を格納します。見つからなければ、空きエントリ、または used が最小のエントリにキー、値、カウンターの値を書き込みます。

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

ハッシュマップと双方向連結リスト

考え方

各リストノードは両隣のノードにリンクしているため、ノードを取得すれば、4つのリンクを変更するだけで、そのノードをリストから外したり、先頭に挿入したりできます。マップからノードを取得できるので、どの操作でもリストをたどる必要はありません。

get がヒットした場合、またはキャッシュ済みのキーに対して put した場合、そのノードを先頭に移動します。キャッシュが満杯のときに新しいキーを追加すると、末尾のノードを削除し、そのキーをマップから削除します。そのため、各ノードには自身のキーが格納されています。番兵ノードの head と tail は両端に配置されるため、ノードを外したり挿入したりするときに、隣接ノードが存在しないか確認する必要はありません。各操作は、1回の検索と少数のリンク変更で済みます: O(1)。

アルゴリズム

番兵ノード head と tail をリンクし、キーからノードへの空のマップを作成します。
get key: キーがマップにない場合は -1 を返します。そうでない場合は、そのノードを head の直後に移動し、その値を返します。
キャッシュ済みキーへの put: 値を格納し、そのノードを head の直後に移動します。
新しいキーへの put: マップに capacity 個のキーが格納されている場合は、tail の直前のノードをリンクから外し、そのキーをマップから削除します。新しいノードを head の直後に挿入し、そのキーをそのノードに対応付けます。

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

落とし穴と境界ケース

get がヒットしたときにキーを先頭へ移動しない。最初の例では、その場合 put 3 はキー 2 ではなくキー 1 を追い出す。
キーがキャッシュされているか確認する前に追い出す。容量が 2 の場合、put 1、put 2、put 2 を実行すると、キー 1 が追い出される。
ノードをリンク解除してもそのキーをマップに残す、またはその逆を行う。するとマップが切り離されたノードを返し、それを移動すると、以前の隣接ノードのリンクが破損する。
保存された 0 をキャッシュミスとして扱う。3 番目の例では、get 0 は "0" を返さなければならない。

よくある質問3

LRUキャッシュの時間計算量はどのくらいですか？

ハッシュマップと双方向連結リストを使うと、get と put はどちらも O(1) で実行されます。検索が1回と、リンクの変更が少しだけ必要です。空間計算量は O(capacity) で、キーごとにノードが1つ、マップのエントリが1つです。

LRUキャッシュが双方向連結リストを使うのはなぜですか？

キャッシュは、順序内のどこにあるキーでも先頭に移動し、末尾のキーを削除します。双方向連結リストなら、各ノードが直前のノードを把握しているため、リンクを少し変更するだけで両方を行えます。単方向連結リストでは、そのノードを見つけるために先頭からたどる必要があり、O(capacity)です。

順序付き辞書を使ってLRUキャッシュを構築できますか？

はい。Python の OrderedDict や Java の LinkedHashMap のように挿入順を保持するマップは、リストの代わりに使えます。使用するたびにキーを末尾に移動し、先頭から削除すれば、引き続き O(1) で処理できます。面接では通常、リストを自分で実装することが求められます。

def lruCacheOps(capacity, ops, keys, values):
    # ここにコードを書いてください

テスト #1

テスト #2

テスト #3

引数

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

期待される出力

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

LRU Cache

関数

制約

例

ヒント

解説

最終使用時刻が記録されたエントリのテーブルをスキャンする

ハッシュマップと双方向連結リスト

落とし穴と境界ケース

よくある質問3

似た問題