Skip to content

Instantly share code, notes, and snippets.

@reterVision
Last active March 1, 2023 02:32
Show Gist options
  • Save reterVision/5018901 to your computer and use it in GitHub Desktop.
Save reterVision/5018901 to your computer and use it in GitHub Desktop.
LRU algorithm implemented in Python.
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())
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
@jackytu256
Copy link

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

Thanks

@hyunwoona
Copy link

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

@juyoung228
Copy link

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

Thanks

@5minho
Copy link

5minho commented May 29, 2018

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

@vipseixas
Copy link

Thanx! Very useful

@saikrishna3281
Copy link

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

@toshchev95
Copy link

toshchev95 commented Oct 7, 2020

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment