Least Recently Used Cache Daily Coding Practice

I have the following challenge problem for which I was able to get a solution working, but not in $$\O(1)\$$ time as the problem asks for. Could someone point me in the right direction to optimize this? I am also open to other criticisms of my coding style.

QUESTION:

Implement an LRU (Least Recently Used) cache. It should be able to be initialized with a cache size n, and contain the following methods:

• set(key, value): sets key to value. If there are already n items in the cache and we are adding a new item, then it should also remove the least recently used item.

• get(key): gets the value at key. If no such key exists, return null.

Each operation should run in $$\O(1)\$$ time.

CODE:

class LRUcache():

def __init__(self,n):
self.vals = dict()
self.max_size = n

def set(self,key,value):
if key in self.vals:
del self.vals[key]
self.vals[key] = value
else:
if(len(self.vals) < self.max_size):
self.vals[key] = value
else:
del self.vals[list(self.vals)]
self.vals[key] = value

def get(self,key):
if key in self.vals:
tempval = self.vals[key]
del self.vals[key]
self.vals[key] = tempval
return self.vals[key]
return None
• I think that the CS textbooks simplify things, when they claim that hash tables are O(1) containers. The never are. The real hash tables are always O(n), but with a very small C (the implicit mutiplier in the Big O notation). In other words, I do not think you can improve this. Aug 8 '19 at 23:44

At first look, it seems like it should be O(1), except for the list(self.vals()). Try iterating over the keys instead:

def set(self,key,value):
if key in self.vals:
del self.vals[key]
self.vals[key] = value
else:
if(len(self.vals) < self.max_size):
self.vals[key] = value
else:
del self.vals[next(iter(self.vals))]    #### changed
self.vals[key] = value
• This is just what I was missing, thank you!
– Hoog
Aug 9 '19 at 12:11

Your code reads very much like you have written some Java and are trying to translate it to Python. You need to "drink the Kool-Aid" and start embracing idiomatic Python, instead.

First, start by noting that storing None as a value is a legitimate thing to do in Python. So the idea of returning None to mean "no key found" is weak. A better approach would be to raise an exception -- probably a KeyError.

However, since it's part of your problem statement, we can ignore that issue (except to note that your problem statement likely came from Java or C++ or someplace like that).

def set(self,key,value):
if key in self.vals:
del self.vals[key]
self.vals[key] = value
else:
if(len(self.vals) < self.max_size):
self.vals[key] = value
else:
del self.vals[list(self.vals)]
self.vals[key] = value

You can overwrite items in a dictionary directly. Just assign to them:

if key in self.vals:
self.vals[key] = value

And your missing-key code is redundant. You assign value in both branches of the if/else statement. Just refactor the assignment down:

if len(self.vals) >= self.max_size:
del self.vals[list(self.vals)]

self.vals[key] = value

Once you do that, you realize that the assignment is also present in the upper (key-found) condition, and you can refactor it again:

def set(self, key, value):
vals = self.vals
if key in vals and len(vals) >= self.max_size:
del vals[list(vals)]
vals[key] = value