本文為Python算法題集之一的代碼示例
題146：LRU 緩存
1. 示例說明
-
請你設計并實現(xiàn)一個滿足 LRU (最近最少使用) 緩存 約束的數(shù)據(jù)結構。
實現(xiàn)
LRUCache類：-
LRUCache(int capacity)以 正整數(shù) 作為容量capacity初始化 LRU 緩存 -
int get(int key)如果關鍵字key存在于緩存中，則返回關鍵字的值，否則返回-1。 -
void put(int key, int value)如果關鍵字key已經(jīng)存在，則變更其數(shù)據(jù)值value；如果不存在，則向緩存中插入該組key-value。如果插入操作導致關鍵字數(shù)量超過capacity，則應該 逐出 最久未使用的關鍵字。
函數(shù)
get和put必須以O(1)的平均時間復雜度運行。示例：
輸入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 輸出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解釋 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 緩存是 {1=1} lRUCache.put(2, 2); // 緩存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 該操作會使得關鍵字 2 作廢，緩存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 該操作會使得關鍵字 1 作廢，緩存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 105- 最多調用
2 * 105次get和put
-
2. 題目解析
- 題意分解
- 本題為設計一個整形緩存類，可以指定緩存大小
- 基本的設計思路是采用隊列控制使用次序，字典進行緩存【哈希】
- 優(yōu)化思路
-
通常優(yōu)化：減少循環(huán)層次
-
通常優(yōu)化：增加分支，減少計算集
-
通常優(yōu)化：采用內(nèi)置算法來提升計算速度
-
分析題目特點，分析最優(yōu)解
-
可以考慮采用有序字典設計緩存類
-
可以考慮采用雙向鏈表設計使用隊列，緩存還是采用字典
-
- 測量工具
- 本地化測試說明：LeetCode網(wǎng)站測試運行時數(shù)據(jù)波動很大，因此需要本地化測試解決這個問題
-
CheckFuncPerf（本地化函數(shù)用時和內(nèi)存占用測試模塊）已上傳到CSDN，地址：Python算法題集_檢測函數(shù)用時和內(nèi)存占用的模塊 - 本題本地化超時測試用例自己生成，詳見【最優(yōu)算法章節(jié)】
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'], '執(zhí)行結果 = {}'.format(result['result']))
# 運行結果
函數(shù) testLRUCache 的運行時間為 561.12 ms；內(nèi)存使用量為 4.00 KB 執(zhí)行結果 = 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'], '執(zhí)行結果 = {}'.format(result['result']))
# 運行結果
函數(shù) testLRUCache 的運行時間為 420.10 ms；內(nèi)存使用量為 0.00 KB 執(zhí)行結果 = 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'], '執(zhí)行結果 = {}'.format(result['result']))
# 運行結果
函數(shù) testLRUCache 的運行時間為 787.18 ms；內(nèi)存使用量為 0.00 KB 執(zhí)行結果 = 99
4. 最優(yōu)算法
根據(jù)本地日志分析，最優(yōu)算法為第2種方式【有序字典】LRUCache_ext1
def testLRUCache(lrucache, actiions):
for act in actiions:
if len(act) > 1:
lrucache.put(act[0], act[1])
else:
lrucache.get(act[0])
return 99
import random
actions = []
iLen = 1000000
for iIdx in range(10):
actions.append([iIdx, random.randint(1, 10)])
iturn = 0
for iIdx in range(iLen):
if iturn >= 2:
actions.append([random.randint(1,10)])
else:
actions.append([random.randint(1,10), random.randint(1, 1000)])
iturn += 1
if iturn >= 3:
iturn = 0
tmpLRUCache = LRUCache_base(5)
result = cfp.getTimeMemoryStr(testLRUCache, tmpLRUCache, actions)
print(result['msg'], '執(zhí)行結果 = {}'.format(result['result']))
# 算法本地速度實測比較
函數(shù) testLRUCache 的運行時間為 561.12 ms；內(nèi)存使用量為 4.00 KB 執(zhí)行結果 = 99
函數(shù) testLRUCache 的運行時間為 420.10 ms；內(nèi)存使用量為 0.00 KB 執(zhí)行結果 = 99
函數(shù) testLRUCache 的運行時間為 787.18 ms；內(nèi)存使用量為 0.00 KB 執(zhí)行結果 = 99
一日練，一日功，一日不練十日空文章來源：http://www.zghlxwxcb.cn/news/detail-832017.html
may the odds be ever in your favor ~文章來源地址http://www.zghlxwxcb.cn/news/detail-832017.html
到了這里，關于Python算法題集_LRU 緩存的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
