第Python實(shí)現(xiàn)FIFO緩存置換算法本文實(shí)例為大家分享了Python實(shí)現(xiàn)FIFO緩存置換算法的具體代碼，供大家參考，具體內(nèi)容如下

在上一節(jié)中我們實(shí)現(xiàn)了雙向鏈表DoubleLinkedList類，本節(jié)我們基于雙向鏈表實(shí)現(xiàn)FIFO（先進(jìn)先出）緩存置換算法。

一、FIFO實(shí)現(xiàn)

代碼邏輯很簡(jiǎn)單，就是遵循先進(jìn)先出的原則，具體流程都寫在注釋中了。通過一個(gè)map來實(shí)現(xiàn)查找時(shí)的O(1)復(fù)雜度

classFIFOCache(object):

def__init__(self,capacity=0xffffffff):

"""

FIFO緩存置換算法

:paramcapacity:

"""

self.capacity=capacity

self.map={}

self.size=0

self.list=DoubleLinkedList(capacity)

defget(self,key):

"""

獲取元素

不存在返回None

已存在則返回緩存值

:paramkey:

:return:

"""

#當(dāng)前緩存中不存在

ifkeynotinself.map:

returnNone

#當(dāng)前緩存中存在

node=self.map.get(key)

returnnode.value

defput(self,key,value):

"""

添加元素

已存在更新值并添加至鏈表尾部

不存在判斷緩存容量大小后添加

:paramkey:

:paramvalue:

:return:已添加的節(jié)點(diǎn)

"""

#當(dāng)前緩存中已存在

ifkeyinself.map:

node=self.map.get(key)

self.list.remove(node)

node.value=value

self.list.append(node)

else:

#緩存容量達(dá)到上限刪除頭結(jié)點(diǎn)

ifself.size=self.capacity:

old_node=self.list.pop()

delself.map[old_node.key]

self.size-=1

node=Node(key,value)

self.map[key]=node

self.list.append(node)

self.size+=1

returnnode

defprint(self):

"""

打印當(dāng)前鏈表

:return:

"""

self.list.print()

#print(self.map)

二、測(cè)試邏輯

if__name__=='__main__':

fifo_cache=FIFOCache(2)

fifo_cache.put(1,1)

fifo_cache.print()

fifo_cache.put(2,2)

fifo_cache.print()

print(fifo_cache.get(2))

fifo_cache.put(3,3)

fifo_cache.print()

print(fifo_cache.get(1))