萬盛學電腦網

 萬盛學電腦網 >> 網絡編程 >> 編程語言綜合 >> Python實現LRU算法的2種方法

Python實現LRU算法的2種方法

   這篇文章主要介紹了Python實現LRU算法的2種方法,本文分別給出了用OrderedDict實現、用dict+list實現兩種方法,需要的朋友可以參考下

  LRU:least recently used,最近最少使用算法。它的使用場景是:在有限的空間中存儲對象時,當空間滿時,會按一定的原則刪除原有的對象,常用的原則(算法)有LRU,FIFO,LFU等。在計算機的Cache硬件,以及主存到虛擬內存的頁面置換,還有Redis緩存系統中都用到了該算法。我在一次面試和一個筆試時,也遇到過這個問題。

  LRU的算法是比較簡單的,當對key進行訪問時(一般有查詢,更新,增加,在get()和set()兩個方法中實現即可)時,將該key放到隊列的最前端(或最後端)就行了,這樣就實現了對key按其最後一次訪問的時間降序(或升序)排列,當向空間中增加新對象時,如果空間滿了,刪除隊尾(或隊首)的對象。

  在Python中,可以使用collections.OrderedDict很方便的實現LRU算法,當然,如果你想不到用OrderedDict,那可以用dict+list來實現。本文主要參考了LRU CACHE IN PYTHON,寫的非常好,既實現了功能,又簡潔易讀。方法一的代碼與參考文章基本相同,方法二是我自己想出來的,比較繁瑣一些,其實OrderedDict本身也是類似的這種機制來實現的有序。

  不過,下面的實現是有問題的,這個cache的key:value鍵值對中,value只能是不可變類型。因為,如果value是可變類型,那對於同一個key,所有調用get(key)方法返回的value都是指向同一個可變對象的,當修改其中一個value時,那所有的value都會被修改了,即使你沒有調用set()方法也會這樣。這是我們不希望看到的。解決方法我想到了兩種,一是可變對象序列化後再存儲,即將可變對象轉為不可變對象;二是仍存儲可變對象,但get()時,返回一個深拷貝,這樣每個get()調用返回的對象就不會相互影響了。推薦第一種方法。另外,對於key,推薦使用str/unicode類型。

  當並發時,還會存在一個問題,因為這涉及到對公共資源的寫操作,所以必須要對set()加鎖。其實,在並發情況下,所有對公共資源的寫操作都要加鎖。如果不存在並發的情況,只有單線程,那可以不加鎖。

  方法一:用OrderedDict實現(推薦)

   代碼如下:

  from collections import OrderedDict

  class LRUCache(OrderedDict):

  '''不能存儲可變類型對象,不能並發訪問set()'''

  def __init__(self,capacity):

  self.capacity = capacity

  self.cache = OrderedDict()

  def get(self,key):

  if self.cache.has_key(key):

  value = self.cache.pop(key)

  self.cache[key] = value

  else:

  value = None

  return value

  def set(self,key,value):

  if self.cache.has_key(key):

  value = self.cache.pop(key)

  self.cache[key] = value

  else:

  if len(self.cache) == self.capacity:

  self.cache.popitem(last = False) #pop出第一個item

  self.cache[key] = value

  else:

  self.cache[key] = value

  測試代碼如下

   代碼如下:

  c = LRUCache(5)

  for i in range(5,10):

  c.set(i,10*i)

  print c.cache, c.cache.keys()

  c.get(5)

  c.get(7)

  print c.cache, c.cache.keys()

  c.set(10,100)

  print c.cache, c.cache.keys()

  c.set(9,44)

  print c.cache, c.cache.keys()

  輸出如下

   代碼如下:

  OrderedDict([(5, 50), (6, 60), (7, 70), (8, 80), (9, 90)]) [5, 6, 7, 8, 9]

  OrderedDict([(6, 60), (8, 80), (9, 90), (5, 50), (7, 70)]) [6, 8, 9, 5, 7]

  OrderedDict([(8, 80), (9, 90), (5, 50), (7, 70), (10, 100)]) [8, 9, 5, 7, 10]

  OrderedDict([(8, 80), (5, 50), (7, 70), (10, 100), (9, 90)]) [8, 5, 7, 10, 9]

  方法二:用dict+list實現(不推薦)

   代碼如下:

  class LRUCache(object):

  '''不能存儲可變類型對象,不能並發訪問set()'''

  def __init__(self,capacity):

  self.l = []

  self.d = {}

  self.capacity = capacity

  def get(self,key):

  if self.d.has_key(key):

  value = self.d[key]

  self.l.remove(key)

  self.l.insert(0,key)

  else:

  value = None

  return value

  def set(self,key,value):

  if self.d.has_key(key):

  self.l.remove(key)

  elif len(self.d) == self.capacity:

  oldest_key = self.l.pop()

  self.d.pop(oldest_key)

  self.d[key] = value

  self.l.insert(0, key)

  測試代碼如下

  代碼如下:

  c = LRUCache(5)

  for i in range(5,10):

  c.set(i,10*i)

  print c.d,c.l

  c.get(5)

  c.get(7)

  print c.d,c.l

  c.set(10,100)

  print c.d,c.l

  c.set(9,44)

  print c.d,c.l

  輸出為

   代碼如下:

  {8: 80, 9: 90, 5: 50, 6: 60, 7: 70} [9, 8, 7, 6, 5]

  {8: 80, 9: 90, 5: 50, 6: 60, 7: 70} [7, 5, 9, 8, 6]

  {5: 50, 7: 70, 8: 80, 9: 90, 10: 100} [10, 7, 5, 9, 8]

  {5: 50, 7: 70, 8: 80, 9: 44, 10: 100} [9, 10, 7, 5, 8]

copyright © 萬盛學電腦網 all rights reserved