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

Question

我正在尝试创建一个仅包含有限数量的 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]。

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

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() 方法执行相同的操作。