Skip to main content
 首页 » 编程设计

Python:尝试创建一个包含有限 MRU 条目的字典

2025年05月04日8xing901022

我正在尝试创建一个仅包含有限数量的 MRU 条目的 dict(用于帮助缓存我通过 ctypes 调用的昂贵 C 函数的输出)。这是代码:

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]。

请指教如何解决这个问题。谢谢!

请您参考如下方法:

对于像这样复杂的行为变化,研究 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() 方法执行相同的操作。