LRU

From Data Algo class:

<code> “”“ 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) </code