的Python：試圖創建一個包含有限的MRU的字典項

Question

我想創建一個dict僅包含MRU條目的數量有限（幫助在緩存昂貴的C函數我通過打電話的ctypes的輸出）。下面是代碼：

from collections import OrderedDict 

class MRUDict(OrderedDict): 

    def __init__(self, capacity = 64): 
     super().__init__() 
     self.__checkAndSetCapacity(capacity) 

    def capacity(self): 
     return self.__capacity 

    def setCapacity(self, capacity): 
     self.__checkAndSetCapacity(capacity) 
     for i in range(len(self) - capacity): 
      self.__evict() # will execute only if len > capacity 

    def __getitem__(self, key): 
     value = super().__getitem__(key) 
     # if above raises IndexError, next line won't execute 
     print("Moving key {} to last i.e. MRU position".format(key)) 
     super().move_to_end(key) 
     return value 

    def __setitem__(self, key, value): 
     if key in self: 
      super().move_to_end(key) 
     else: # new key 
      if len(self) == self.__capacity: 
       self.__evict() 
     super().__setitem__(key, value) 

    def __evict(self): 
     key, value = self.popitem(last = False) # pop first i.e. oldest item 
     print("Capacity exceeded. Evicting ({}, {})".format(key, value)) 

    def __checkAndSetCapacity(self, capacity): 
     if not isinstance(capacity, int): 
      raise TypeError("Capacity should be an int.") 
     if capacity == 0: 
      raise ValueError("Capacity should not be zero.") 
     self.__capacity = capacity 

...這裏是測試代碼：

def printkeys(d): 
    print("Current keys in order:", tuple(d)) # here d means d.keys() 
    print() 

from mrudict import MRUDict 
print("Creating MRUDict with capacity 5.") 
d = MRUDict(5) 
print("Adding keys 0 to 7 with values:") 
for i in range(8): d[i] = i + 0.1 
printkeys(d) 

print("Calling str on object:") 
print(d) # test of default __repr__ (since probably __str__ is the same here) 
printkeys(d) 

print("Accessing existing key 4:") 
print(4, d[4]) # test of __getitem__ 
printkeys(d) 

try: 
    print("Accessing non-existing key 20:") 
    print(20, d[20]) # test of __getitem__ 
except: 
    print("Caught exception: key does not exist.") 
printkeys(d) 

print("Updating value of existing key 6:") 
d[6] = 6.6 # test of __setitem__ with existing key 
printkeys(d) 

print("Adding new key, value pair:") 
d[10] = 10.1 # test of __setitem__ with non-existing key 
printkeys(d) 

print("Testing for presence of key 3:") 
print(3 in d) 
printkeys(d) 

print("Trying to loop over the items:") 
for k in d: print(k, d[k]) 
printkeys(d) 

print("Trying to loop over the items:") 
for k, v in d.items(): print(k, v) 
printkeys(d) 

從現在看來，我是那種天真在實施__getitem__功能，因爲這兩個__repr__和輸出for ... in（其中，我猜在這裏，叫__iter__然後__getitem__）導致的第一個項目將被移動到最後的MRU，但無法繼續進行，因爲對於迭代器沒有「下」項目，因爲它現在指向最後的元素。但我不確定我能做些什麼來解決這個問題。我應該重新執行__iter__嗎？

我不知道如何將用戶的呼叫__getitem__和同一內部通話區分。當然，一種解決方法是讓用戶使用find()方法來完成移動到終端的事情，但我真的希望能夠使用常規語法d[k]。

請就如何解決這一問題提出建議。謝謝！

Answer 1

像這些行爲的複雜變化，是值得研究OrderedDict source code。

實際__iter__方法循環直接在內部結構，維護項目順序的雙向鏈表。它永遠不會直接使用__getitem__，而只是從鏈接列表中返回鍵。

，您有實際的問題是，你是直接訪問項目而循環：

for k in d: print(k, d[k]) 

書中有一個d[k]; 即訪問從開始到結束移動項目5。這會更新鏈接列表，因此當詢問下一個項目時，curr.next參考現在是根並且迭代停止。

工作，各地將這樣做。添加一個專門的方法來訪問項目而不觸發MRU更新。或者你可以重複使用dict.get()例如：

>>> for k in d: print(k, d.get(k)) 
... 
5 5.1 
7 7.1 
4 4.1 
6 6.6 
10 10.1 

您將有與.items()方法的問題; OrderedDict重用collections.abc.MutableMapping的.items()方法，該方法返回collections.abc.ItemsView()實例;請參閱collections.abc source code。

你必須更換行爲：

from collections.abc import ItemsView 


class MRUDictItemsView(ItemsView): 
    def __contains__(self, item): 
     key, value = item 
     v = self._mapping.get(key, object()) 
     return v == value 

    def __iter__(self): 
     for key in self._mapping: 
      yield (key, self._mapping.get(key)) 


class MRUDict(OrderedDict): 
    # ... 

    def items(self): 
     return MRUDictItemsView(self) 

你不得不爲.keys()和.values()方法做同樣的。