root/galaxy-central/lib/galaxy/util/lrucache.py

リビジョン 2, 2.1 KB (コミッタ: hatakeyama, 14 年 前)

import galaxy-central

行番号 
1"""
2Kanwei Li, 03/2010
3
4Simple LRU cache that uses a dictionary to store a specified number of objects
5at a time.
6"""
7
8class 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
39if __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           
Note: リポジトリブラウザについてのヘルプは TracBrowser を参照してください。