Last active
January 21, 2019 08:21
-
-
Save ausaki/6ca24773d4cb93a02b454f6a200ae0e2 to your computer and use it in GitHub Desktop.
This file contains hidden or 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
| # -*- coding: utf8 -*- | |
| """ | |
| source：https://github.com/donnemartin/system-design-primer/blob/master/solutions/object_oriented_design/lru_cache/lru_cache.ipynb | |
| """ | |
| class Node(object): | |
| def __init__(self, key, val): | |
| self.key = key | |
| self.val = val | |
| self.prev = None | |
| self.next = None | |
| class LinkedQueue(object): | |
| """ | |
| 双向链表实现的队列 | |
| """ | |
| def __init__(self): | |
| self.size = 0 | |
| self.head = None | |
| self.tail = None | |
| def _empty(self): | |
| return self.size == 0 | |
| def __str__(self): | |
| if self._empty(): | |
| return 'Queue([])' | |
| h = self.head | |
| s = [] | |
| while h: | |
| s.append('[{}:{}]'.format(h.key, h.val)) | |
| h = h.next | |
| return 'Queue({})'.format(' <-> '.join(s)) | |
| def append(self, node): | |
| if self._empty(): | |
| node.prev = node.next = None | |
| self.head = self.tail = node | |
| else: | |
| self.tail.next = node | |
| node.prev = self.tail | |
| node.next = None | |
| self.tail = node | |
| self.size += 1 | |
| def pop(self): | |
| if self._empty(): | |
| return None | |
| node = self.head | |
| next_node = node.next | |
| node.next = node.prev = None | |
| if next_node: | |
| next_node.prev = None | |
| self.head = next_node | |
| self.size -= 1 | |
| if self._empty(): | |
| self.head = self.tail = None | |
| return node | |
| def move_to_tail(self, node): | |
| if self._empty(): | |
| return | |
| if node == self.tail: | |
| # if node is head, then no need to move it. | |
| return | |
| if node == self.head: | |
| self.pop() | |
| else: | |
| node.prev.next = node.next | |
| node.next.prev = node.prev | |
| self.size -= 1 | |
| self.append(node) | |
| class LRUCache(object): | |
| """LRUCache | |
| """ | |
| def __init__(self, capacity): | |
| """ | |
| :type capacity: int | |
| """ | |
| self.capacity = capacity | |
| self.size = 0 | |
| self.cache = dict() | |
| self.queue = LinkedQueue() | |
| def full(self): | |
| return self.size == self.capacity | |
| def empty(self): | |
| return self.size == 0 | |
| def remove_old(self): | |
| old_node = self.queue.pop() | |
| self.cache.pop(old_node.key) | |
| self.size -= 1 | |
| def get(self, key): | |
| """ | |
| :type key: int | |
| :rtype: int | |
| """ | |
| node = self.cache.get(key) | |
| if node is None: | |
| return -1 | |
| val = node.val | |
| self.queue.move_to_tail(node) | |
| return val | |
| def put(self, key, value): | |
| """ | |
| :type key: int | |
| :type value: int | |
| :rtype: void | |
| """ | |
| if key in self.cache: | |
| node = self.cache[key] | |
| node.val = value | |
| self.queue.move_to_tail(node) | |
| return | |
| if self.full(): | |
| self.remove_old() | |
| node = Node(key, value) | |
| self.queue.append(node) | |
| self.cache[key] = node | |
| self.size += 1 | |
| # test case | |
| operations = ["LRUCache","put","put","get","put","put","get"] | |
| args = [[2],[2,1],[2,2],[2],[1,1],[4,1],[2]] | |
| cache = None | |
| for op, arg in zip(operations, args): | |
| print(op, arg) | |
| if op == 'LRUCache': | |
| cache = LRUCache(*arg) | |
| else: | |
| v = getattr(cache, op)(*arg) | |
| if op == 'get': | |
| print('get:', v) | |
| print('queue:', cache.queue) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment