Python算法题集_LRU 缓存-3. 代码展开

1) 标准求解【队列+字典】

队列控制使用次序，字典保存键值对

勉强通关，超过05%

import CheckFuncPerf as cfp

class LRUCache_base:
def __init__(self, capacity):
   self.queue, self.dict, self.capacity, self.queuelen = [], {}, capacity, 0
def get(self, key):
   if key in self.queue:
       self.queue.remove(key)
       self.queue.append(key)
       return self.dict[key]
   else:
       return -1
def put(self, key, value):
   if key in self.queue:
       self.queue.remove(key)
   else:
       if self.queuelen == self.capacity:
           self.dict.pop(self.queue.pop(0))
       else:
           self.queuelen += 1
   self.queue.append(key)
   self.dict[key] = valu

tmpLRUCache = LRUCache_base(5)
result = cfp.getTimeMemoryStr(testLRUCache, tmpLRUCache, actions)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 运行结果
函数 testLRUCache 的运行时间为 561.12 ms；内存使用量为 4.00 KB 执行结果 = 99

2) 改进版一【有序字典】

采用有序字典【Python3.6之后支持】，同时支持使用顺序和保存键值对

性能卓越，超越93%

import CheckFuncPerf as cfp

class LRUCache_ext1:
 def __init__(self, capacity):
     self.data = dict()
     self.capacity = capacity
 def get(self, key):
     keyval = self.data.get(key, -1)
     if keyval != -1:
         self.data.pop(key)
         self.data[key] = keyval
     return keyval
 def put(self, key, value)
     if key in self.data:
         self.data.pop(key)
         self.data[key] = value
     else:
         if len(self.data) < self.capacity:
             self.data[key] = value
         else:
             firstpop = next(iter(self.data))
             self.data.pop(firstpop)
             self.data[key] = value

tmpLRUCache = LRUCache_ext1(5)
result = cfp.getTimeMemoryStr(testLRUCache, tmpLRUCache, actions)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 运行结果
函数 testLRUCache 的运行时间为 420.10 ms；内存使用量为 0.00 KB 执行结果 = 99

3) 改进版二【双向链表+字典】

采用双向链表维护使用顺序，字典保存键值对，要首先定义双向链表类

性能卓越，超过92%

import CheckFuncPerf as cfp

class ListNodeDouble:
 def __init__(self, key=None, value=None):
     self.key = key
     self.value = value
     self.prev = None
     self.next = None
class LRUCache_ext2:
 def __init__(self, capacity):
     self.capacity = capacity
     self.dict = {}
     self.head = ListNodeDouble()
     self.tail = ListNodeDouble()
     self.head.next = self.tail
     self.tail.prev = self.head
 def move_to_tail(self, key):
     tmpnode = self.dict[key]
     tmpnode.prev.next = tmpnode.next
     tmpnode.next.prev = tmpnode.prev
     tmpnode.prev = self.tail.prev
     tmpnode.next = self.tail
     self.tail.prev.next = tmpnode
     self.tail.prev = tmpnode
 def get(self, key: int):
     if key in self.dict:
         self.move_to_tail(key)
     result = self.dict.get(key, -1)
     if result == -1:
         return result
     else:
         return result.value
 def put(self, key, value):
     if key in self.dict:
         self.dict[key].value = value
         self.move_to_tail(key)
     else:
         if len(self.dict) == self.capacity:
             self.dict.pop(self.head.next.key)
             self.head.next = self.head.next.next
             self.head.next.prev = self.head
         newkeyval = ListNodeDouble(key, value)
         self.dict[key] = newkeyval
         newkeyval.prev = self.tail.prev
         newkeyval.next = self.tail
         self.tail.prev.next = newkeyval
         self.tail.prev = newkeyval

tmpLRUCache = LRUCache_ext2(5)
result = cfp.getTimeMemoryStr(testLRUCache, tmpLRUCache, actions)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 运行结果
函数 testLRUCache 的运行时间为 787.18 ms；内存使用量为 0.00 KB 执行结果 = 99

---