[2] | 1 | """ |
---|
| 2 | Kanwei Li, 03/2010 |
---|
| 3 | |
---|
| 4 | Simple LRU cache that uses a dictionary to store a specified number of objects |
---|
| 5 | at a time. |
---|
| 6 | """ |
---|
| 7 | |
---|
| 8 | class LRUCache: |
---|
| 9 | def clear(self): |
---|
| 10 | ''' Clears/initiates storage variables''' |
---|
| 11 | self.key_ary = [] |
---|
| 12 | self.obj_cache = {} |
---|
| 13 | |
---|
| 14 | def __init__(self, num_elements): |
---|
| 15 | self.num_elements = num_elements |
---|
| 16 | self.clear() |
---|
| 17 | |
---|
| 18 | def __getitem__(self, key): |
---|
| 19 | ''' Return value of key, or None if key is not in cache ''' |
---|
| 20 | try: |
---|
| 21 | index = self.key_ary.index(key) |
---|
| 22 | except ValueError: |
---|
| 23 | return None |
---|
| 24 | # Move this key to the end |
---|
| 25 | self.key_ary.remove(key) |
---|
| 26 | self.key_ary.append(key) |
---|
| 27 | return self.obj_cache[key] |
---|
| 28 | |
---|
| 29 | def __setitem__(self, key, value): |
---|
| 30 | ''' Sets a new value to a key ''' |
---|
| 31 | if key not in self.obj_cache: |
---|
| 32 | if len(self.key_ary) >= self.num_elements: |
---|
| 33 | deleted_key = self.key_ary.pop(0) # Remove first element |
---|
| 34 | del self.obj_cache[deleted_key] |
---|
| 35 | self.key_ary.append(key) |
---|
| 36 | self.obj_cache[key] = value |
---|
| 37 | return value |
---|
| 38 | |
---|
| 39 | if __name__ == "__main__": |
---|
| 40 | import unittest |
---|
| 41 | |
---|
| 42 | class TestLRUCache(unittest.TestCase): |
---|
| 43 | def test_lru(self): |
---|
| 44 | lru = LRUCache(2) |
---|
| 45 | for i in range(0, 4): # Insert 4 numbers |
---|
| 46 | lru[i] = i |
---|
| 47 | self.assertEqual( lru[0], None ) |
---|
| 48 | self.assertEqual( lru[1], None ) |
---|
| 49 | self.assertEqual( lru[2], 2 ) |
---|
| 50 | self.assertEqual( lru[3], 3 ) |
---|
| 51 | |
---|
| 52 | self.assertEqual( lru.__setitem__("hello", "world"), "world") |
---|
| 53 | self.assertEqual( lru[2], None ) |
---|
| 54 | |
---|
| 55 | lru.clear() |
---|
| 56 | self.assertEqual( lru["hello"], None ) |
---|
| 57 | self.assertEqual( lru[3], None ) |
---|
| 58 | |
---|
| 59 | # Test if recently used item is kept |
---|
| 60 | lru[0] = 0 |
---|
| 61 | lru[1] = 1 |
---|
| 62 | # Now saturated |
---|
| 63 | ping = lru[0] |
---|
| 64 | lru[2] = 2 |
---|
| 65 | # Should keep 0, delete 1 |
---|
| 66 | self.assertEqual( lru[0], 0 ) |
---|
| 67 | self.assertEqual( lru[1], None ) |
---|
| 68 | self.assertEqual( lru[2], 2 ) |
---|
| 69 | |
---|
| 70 | unittest.main() |
---|
| 71 | |
---|
| 72 | |
---|