LRUアルゴリズム——python実装
LeetCodeでこんな問題を見ました.
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:
get(key):keyに対応するvalueを取得し、keyがcacheにない場合は-1を返します(valueは常に正数です).
set(key,value):keyがcacheにある場合、そのvalueを更新します.不在の場合は挿入し、cacheがいっぱいの場合は最近最も使用した項目を削除してから挿入します.
getの場合、keyがcacheにある場合、そのget(key)はkeyへのアクセスを表す.set(key,value)は常にkeyへのアクセスを表す.
1つのlistを使用してアクセスの順序を記録し、最初にアクセスしたものはlistの前に、最後にアクセスしたものはlistの後ろに配置するので、cacheがいっぱいになった場合、list[0]を削除し、新しい項目を挿入します.
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:
get
and set
. get(key)
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value)
- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. LRU cacheを設計し、2つの機能を実現します:(cacheにキー値ペアが格納されています)get(key):keyに対応するvalueを取得し、keyがcacheにない場合は-1を返します(valueは常に正数です).
set(key,value):keyがcacheにある場合、そのvalueを更新します.不在の場合は挿入し、cacheがいっぱいの場合は最近最も使用した項目を削除してから挿入します.
getの場合、keyがcacheにある場合、そのget(key)はkeyへのアクセスを表す.set(key,value)は常にkeyへのアクセスを表す.
1つのlistを使用してアクセスの順序を記録し、最初にアクセスしたものはlistの前に、最後にアクセスしたものはlistの後ろに配置するので、cacheがいっぱいになった場合、list[0]を削除し、新しい項目を挿入します.
class LRUCache:
# @param capacity, an integer
def __init__(self, capacity):
self.cache = {}
self.used_list = []
self.capacity = capacity
# @return an integer
def get(self, key):
if key in self.cache:
if key != self.used_list[-1]:
self.used_list.remove(key)
self.used_list.append(key)
return self.cache[key]
else:
return -1
# @param key, an integer
# @param value, an integer
# @return nothing
def set(self, key, value):
if key in self.cache:
self.used_list.remove(key)
elif len(self.cache) == self.capacity:
self.cache.pop(self.used_list.pop(0))
self.used_list.append(key)
self.cache[key] = value