LRU
Good explanation at LRU Cache Implementation
From Data Algo class:
"""
Implement an LRU cache
The trick here is to use an OrderdDict. When adding a value delete
it from the dict if it exists, then put it on so it is at the end
of the dict. If over capacity then remove the first value and
add the new value, thus removing the least used.
"""
from collections import OrderedDict
class LRU_Cache(object):
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
# Attemt to get a value. If this value is not in the
# cache, add it. If this value is in the cache, pop it
# (which gets the value and removed it from the dict)
# and add it back to the dict, placing it last. This
# will allow up to effectively know which is the last used.
def get(self, key):
""" Retrieve item from provided key. Return -1 if nonexistent. """
#Try to remove it and then put it back on
try:
value = self.cache.pop(key)
self.cache[key] = value
return value
except KeyError:
# Exception thrown if not in cache
return -1
def set(self, key, value):
""" Set the value if the key is not present in the cache.
If the cache is at capacity remove the oldest item.
"""
# Check to see if the value exists. If not, add it .
# and also check the capacity
if self.get(key) == -1:
# Check to see if adding this item will overflow the capacity
# If os, remove the least recently used
if len(self.cache) == self.capacity:
self.cache.popitem(last=False)
# Now add or replace the value for the key
self.cache[key] = value
def __str__(self):
string = ""
for value in self.cache.values():
string += str(value) + ","
return string[:-1] # remove last comma
def test(cache, value, expected_answer):
if len(cache.cache) == 0:
print("Testing seaching for value in empty cache")
else:
print("Testing value %d in %s" % (value, str(cache)))
#print("Answer should be %d" % expected_answer)
answer = our_cache.get(value)
if answer != expected_answer:
print("Error: our_cache.get(%d) should = %d, got %d" %(value, expected_answer, answer))
# Test 1, test simple get
our_cache = LRU_Cache(5)
our_cache.set(1, 1);
our_cache.set(2, 2);
our_cache.set(3, 3);
our_cache.set(4, 4);
test(our_cache, 1, 1)
# Test 2
our_cache = LRU_Cache(1)
our_cache.set(1, 1);
test(our_cache, 1, 1)
# Test 3, value not in cache
test(our_cache, 9, -1) # Not in cache
# Test edge case: cache capacity only 1, but more than one added
our_cache = LRU_Cache(1)
our_cache.set(1, 1);
our_cache.set(2, 2);
our_cache.set(3, 3);
our_cache.set(4, 4);
test(our_cache, 4, 4)
# Test edge case: capacity 3, first added value should not exist
our_cache = LRU_Cache(3)
our_cache.set(1, 1);
our_cache.set(2, 2);
our_cache.set(3, 3);
our_cache.set(4, 4);
test(our_cache, 1, -1)
# Edge case: empty cache
our_cache = LRU_Cache(3)
test(our_cache, 1, -1)