4
\$\begingroup\$

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)[0]]
                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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Ilkhd Aug 8 at 23:44
2
\$\begingroup\$

At first look, it seems like it should be O(1), except for the list(self.vals())[0]. 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
\$\endgroup\$
  • \$\begingroup\$ This is just what I was missing, thank you! \$\endgroup\$ – Hoog Aug 9 at 12:11
3
\$\begingroup\$

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).

In your set() method:

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)[0]]
            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)[0]]

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)[0]]
    vals[key] = value

In your get() method:

You are doing things pretty much spot-on, here, but you are depending on dictionaries to preserve insertion order. That is a somewhat new feature in python (added as an implementation detail in 3.6, and guaranteed in 3.7) that won't work in 3.5. You should at least comment this, and probably should add code at the top of your module to verify the version of python.

On the other hand: there is a collections.OrderedDict in the standard library that has been around for a while, and which even includes an example of building an LRU cache in the documentation. Just sayin'. ;-)

\$\endgroup\$
  • 1
    \$\begingroup\$ I thing you are wrong. Deleting and adding a key-value pair is not going to work the same way as assigning a value by a key. The whole point of doing the way OP did is to alter the internal order of the map. In your case, I think, it won' happen. \$\endgroup\$ – Ilkhd Aug 8 at 23:39
  • \$\begingroup\$ thanks for the tips! My code looks much nicer now! \$\endgroup\$ – Hoog Aug 9 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.