Created
August 3, 2022 14:58
-
-
Save ardeshireshghi/c244c26a8a39a444d6d8e31c175b9b51 to your computer and use it in GitHub Desktop.
LRU cache
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
'''Cache class for LRU''' | |
KEY_NOT_EXIST_VALUE = 'key-not-exist' | |
class LRUCache: | |
''' | |
Least recently used cache | |
''' | |
def __init__(self, size=10): | |
self._store = {} | |
self._size = size | |
def put(self, key, value): | |
'''Sets a key value in the cache''' | |
if self._is_cache_full(): | |
self._delete_least_used() | |
self.store[key] = value | |
return True | |
def get(self, key): | |
'''Get a key value in the cache''' | |
try: | |
value = self.store.get(key, KEY_NOT_EXIST_VALUE) | |
if value == KEY_NOT_EXIST_VALUE: | |
return None | |
except KeyError: | |
return None | |
self.store.pop(key, None) | |
self.store[key] = value | |
return value | |
def _is_cache_full(self): | |
return len(self.store.keys()) == self.size | |
def _cache_key_exists(self, cache_key): | |
for key in self.store: | |
if cache_key == key: | |
return True | |
return False | |
def _delete_least_used(self): | |
least_used_key = list(self.store.keys())[0] | |
self.store.pop(least_used_key) | |
@property | |
def size(self): | |
'''Size property getter''' | |
return self._size | |
@property | |
def store(self): | |
'Store property getter' | |
return self._store |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
'''Runs the cache implemetation ''' | |
from cache.cache import LRUCache | |
def main(): | |
'''Tests the cache logic''' | |
print('Cache of size 3 is created') | |
cache = LRUCache(3) | |
print('Put a=>1, b=>2, c=>3 and d=>4') | |
cache.put('a', 1) | |
cache.put('b', 2) | |
cache.put('c', 3) | |
cache.put('d', 4) | |
# Query non-existing | |
print('Query non-existing a') | |
print(cache.get('a'), end="\n\n") | |
# Query existing | |
print('Query existing b and c') | |
print(cache.get('b')) | |
print(cache.get('c'), end="\n\n") | |
# Put new value | |
print('Put new value e => 5') | |
cache.put('e', 5) | |
# Least used cache which is 'd' should be removed | |
# None is returned | |
print('Query d and should get None because it was LRU cache and removed') | |
print(cache.get('d')) | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment