2

dict限られた数の MRU エントリのみを含むを作成しようとしています (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__and for ... in(ここでは、呼び出してから呼び出していると思います)__iter__の両方__getitem__が、最初の項目を MRU として最後に移動させますが、それ以上進めることができないためです。最後の要素を指しているため、イテレータの「次の」項目はありません。しかし、状況を修正するために何ができるかわかりません。再実装する必要があり__iter__ますか?

__getitem__ユーザーの呼び出しと内部呼び出しを区別する方法がわかりません。もちろん、回避策はユーザーにfind()移動から終了までを行うメソッドを使用させることですが、通常の構文を使用できるようにしたいと思っていますd[k]。

これを修正する方法についてアドバイスをお願いします。ありがとう！

4

1 に答える 1

2

OrderedDictこのような動作の複雑な変更については、ソース コードを調べる価値があります。

実際のメソッドは、アイテムの順序を維持する二重リンク リストである内部構造を直接__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()OrderedDictcollections.abc.MutableMapping.items()collections.abc.ItemsView()collections.abc

その動作を置き換える必要があります。

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()ます。

于 2014-05-17T11:42:45.517 に答える