LRU algorithm implemented in Python.

LRU.py

from datetime import datetime


class LRUCacheItem(object):
    """Data structure of items stored in cache"""
    def __init__(self, key, item):
        self.key = key
        self.item = item
        self.timestamp = datetime.now()


class LRUCache(object):
    """A sample class that implements LRU algorithm"""

    def __init__(self, length, delta=None):
        self.length = length
        self.delta = delta
        self.hash = {}
        self.item_list = []

    def insertItem(self, item):
        """Insert new items to cache"""

        if item.key in self.hash:
            # Move the existing item to the head of item_list.
            item_index = self.item_list.index(item)
            self.item_list[:] = self.item_list[:item_index] + self.item_list[item_index+1:]
            self.item_list.insert(0, item)
        else:
            # Remove the last item if the length of cache exceeds the upper bound.
            if len(self.item_list) > self.length:
                self.removeItem(self.item_list[-1])

            # If this is a new item, just append it to
            # the front of item_list.
            self.hash[item.key] = item
            self.item_list.insert(0, item)

    def removeItem(self, item):
        """Remove those invalid items"""

        del self.hash[item.key]
        del self.item_list[self.item_list.index(item)]

    def validateItem(self):
        """Check if the items are still valid."""

        def _outdated_items():
            now = datetime.now()
            for item in self.item_list:
                time_delta = now - item.timestamp
                if time_delta.seconds > self.delta:
                    yield item
        map(lambda x: self.removeItem(x), _outdated_items())

test_LRU.py

from lru import *
from time import sleep


def print_cache(cache):
    for i, item in enumerate(cache.item_list):
        print ("index: {0} "
               "key: {1} "
               "item: {2} "
               "timestamp: {3}".format(i,
                                       item.key,
                                       item.item,
                                       item.timestamp))

one = LRUCacheItem(1, 'one')
two = LRUCacheItem(2, 'two')
three = LRUCacheItem(3, 'three')

print "Initial cache items."
cache = LRUCache(length=3, delta=5)
cache.insertItem(one)
cache.insertItem(two)
cache.insertItem(three)
print_cache(cache)
print "#" * 20

print "Insert a existing item: {0}.".format(one.key)
cache.insertItem(one)
print_cache(cache)
print "#" * 20

print "Insert another existing item: {0}.".format(two.key)
cache.insertItem(two)
print_cache(cache)
print "#" * 20

print "Validate items after a period of time"
sleep(6)
cache.validateItem()
print_cache(cache)
print "#" * 20

I got a question relating to this implementation because the list is not doubly linked list ?

Thanks

@jackytu256 A doubly linked list based queue will perform better, since self.item_list.index(item) does a linear scanning of self.item_list. You can store the pointer to the node in the queue and remove the node directly on removeItem().

Thank you for the great code!
Can I ask you what is the role of 'delta' in this code?

Thanks

@juyoung228 I think the role of the delta variable is the valid time in the lru cache
After delta time, item is deleted in cache.

Thanx! Very useful

Great implementation!
However, in the hash (dictionary), you could rather store the index of the node in the list

Your code has bug

one = LRUCacheItem(1, 'one')
one2 = LRUCacheItem(1, 'one2')
cache = LRUCache(length=3, delta=5)
cache.insertItem(one)
cache.insertItem(one2)

Stacktrace

Traceback (most recent call last):
  File "main.py", line 74, in <module>
    cache.insertItem(one2)
  File "main.py", line 26, in insertItem
    item_index = self.item_list.index(item)
ValueError: <__main__.LRUCacheItem object at 0x7f9ec425dfa0> is not in list