사전의 크기를 제한하는 방법은 무엇입니까?

Question

파이썬에서 DITT를 사용하고 싶지만 키/값 쌍의 수를 X로 제한하고 있습니다. 즉, DICT가 현재 X 키/값 쌍을 저장하고 삽입을 수행하는 경우 중 하나를 원합니다. 기존 쌍이 삭제됩니다. 가장 최근에 삽입/액세스 키 인 경우 좋을 것입니다. 그러나 완전히 필요하지 않습니다.

이것이 표준 라이브러리에 존재한다면 시간을 절약하고 지적하십시오!

Answer 1

Python 2.7 및 3.1이 있습니다 순서대로 그리고 초기 파이썬에 대한 순수한 파이썬 구현이 있습니다.

from collections import OrderedDict

class LimitedSizeDict(OrderedDict):
    def __init__(self, *args, **kwds):
        self.size_limit = kwds.pop("size_limit", None)
        OrderedDict.__init__(self, *args, **kwds)
        self._check_size_limit()

    def __setitem__(self, key, value):
        OrderedDict.__setitem__(self, key, value)
        self._check_size_limit()

    def _check_size_limit(self):
        if self.size_limit is not None:
            while len(self) > self.size_limit:
                self.popitem(last=False)

또한 항목을 삽입 할 수있는 다른 방법을 무시해야합니다. update. 기본 사용 OrderedDict 쉽게 튀어 나오는 것을 제어 할 수 있습니다. 그렇지 않으면 정상 dict 작동 할 것이다.

Answer 2

캐시 툴 이 작업을 수행하는 매핑 해시의 멋진 구현을 제공합니다 (및 Python 2 및 3에서 작동 함).

문서 발췌 :

이 모듈의 목적을 위해 캐시는 고정 최대 크기의 변이 가능한 매핑입니다. 캐시가 가득 차면, 즉 캐시가 최대 크기를 초과하는 다른 항목을 추가하여 캐시는 적절한 캐시 알고리즘을 기반으로 버릴 항목을 선택해야합니다.

Answer 3

간단한 No-LRU Python 2.6+ 솔루션은 다음과 같습니다 (오래된 파이썬에서는 비슷한 일을 할 수 있습니다. UserDict.DictMixin, 그러나 2.6 이상은 권장되지 않는 것이 좋습니다. ABC는 collections 어쨌든 바람직하다 ...) :

import collections

class MyDict(collections.MutableMapping):
    def __init__(self, maxlen, *a, **k):
        self.maxlen = maxlen
        self.d = dict(*a, **k)
        while len(self) > maxlen:
            self.popitem()
    def __iter__(self):
        return iter(self.d)
    def __len__(self):
        return len(self.d)
    def __getitem__(self, k):
        return self.d[k]
    def __delitem__(self, k):
        del self.d[k]
    def __setitem__(self, k, v):
        if k not in self and len(self) == self.maxlen:
            self.popitem()
        self.d[k] = v

d = MyDict(5)
for i in range(10):
    d[i] = i
    print(sorted(d))

다른 답변에 언급했듯이, 당신은 아마도 서브 클래스 dict를 원하지 않을 것입니다 - 명백한 대표단은 self.d 불행히도 보일러 플레이트이지만 그렇습니다 보장하다 다른 모든 방법은 올바르게 제공됩니다 collections.MutableMapping.

Answer 4

다음은 Python 버전 1.5.2 이상에서 실행되는 Dirt Simple Python 코드로 작성된 간단하고 효율적인 LRU 캐시입니다.

class LRU_Cache:

    def __init__(self, original_function, maxsize=1000):
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = {}

        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3         # link fields
        self.head = [None, None, None, None]        # oldest
        self.tail = [self.head, None, None, None]   # newest
        self.head[NEXT] = self.tail

    def __call__(self, *key):
        PREV, NEXT = 0, 1
        mapping, head, tail = self.mapping, self.head, self.tail

        link = mapping.get(key, head)
        if link is head:
            value = self.original_function(*key)
            if len(mapping) >= self.maxsize:
                old_prev, old_next, old_key, old_value = head[NEXT]
                head[NEXT] = old_next
                old_next[PREV] = head
                del mapping[old_key]
            last = tail[PREV]
            link = [last, tail, key, value]
            mapping[key] = last[NEXT] = tail[PREV] = link
        else:
            link_prev, link_next, key, value = link
            link_prev[NEXT] = link_next
            link_next[PREV] = link_prev
            last = tail[PREV]
            last[NEXT] = tail[PREV] = link
            link[PREV] = last
            link[NEXT] = tail
        return value

if __name__ == '__main__':
    p = LRU_Cache(pow, maxsize=3)
    for i in [1,2,3,4,5,3,1,5,1,1]:
        print(i, p(i, 2))

Answer 5

DICT에는 이러한 행동이 없습니다. 당신은 이것을하는 것과 같은 자신의 수업을 만들 수 있습니다.

class MaxSizeDict(object):
    def __init__(self, max_size):
        self.max_size = max_size
        self.dict = {}
    def __setitem__(self, key, value):
        if key in self.dict:
            self.dict[key] = value    
            return

        if len(self.dict) >= self.max_size:
      ...

이것에 대한 몇 가지 메모

• 일부는 서브 클래스를 유혹 할 것입니다 dict 여기. 기술적 으로이 작업을 수행 할 수 있지만 방법이 서로 의존하지 않기 때문에 버그가 발생합니다. 당신이 사용할 수있는 UserDict.DictMixin 모든 방법을 정의해야합니다. 서브 클래스를 사용하면 재사용 할 수있는 방법은 거의 없습니다. dict.
• DICT는 방향이 변하지 않기 때문에 DICT는 최근에 가장 최근에 추가 된 키가 무엇인지 알지 못합니다.
  • 2.7 도입됩니다 collections.OrderedDict, 그러나 지금은 열쇠를 별도로 정리하게 유지해야합니다. collections.deque 대기열로).
  • 가장 오래된 것을 얻는 것이 그다지 중요하지 않다면, 당신은 popitem 메소드 임의 항목 하나를 삭제하는 방법.
• 나는 가장 나이가 많은 것을 첫 번째 삽입을 의미하는 것으로 해석했다. LRU 항목을 제거하기 위해 약간 다른 일을해야합니다. 가장 명백한 효율적인 전략은 DICT 값 (실제 값과 함께)으로 저장된 노드 자체에 대한 참조가있는 이중 연결 키 목록을 유지하는 것입니다. 이것은 더 복잡해지고 순수한 파이썬으로 구현하면 많은 오버 헤드가 제공됩니다.

Answer 6

서브 클래싱 DICT를 통해 사용자 정의 사전 클래스를 만들 수 있습니다. 귀하의 경우, 당신은 무시해야합니다 __setitem__ 자신의 길이를 점검하고 한계가 다시되면 무언가를 삭제하십시오. 다음 예제는 모든 삽입 후 현재 렌트를 인쇄합니다.

class mydict(dict):
    def __setitem__(self, k, v):
        dict.__setitem__(self, k, v)
        print len(self)

d = mydict()
d['foo'] = 'bar'
d['bar'] = 'baz'

Answer 7

좋은 답변이 많았지 만 LRU 캐시에 대한 간단하고 피해자 구현을 지적하고 싶습니다. Alex Martelli의 대답과 비슷합니다.

from collections import OrderedDict, MutableMapping

class Cache(MutableMapping):
    def __init__(self, maxlen, items=None):
        self._maxlen = maxlen
        self.d = OrderedDict()
        if items:
            for k, v in items:
                self[k] = v

    @property
    def maxlen(self):
        return self._maxlen

    def __getitem__(self, key):
        self.d.move_to_end(key)
        return self.d[key]

    def __setitem__(self, key, value):
        if key in self.d:
            self.d.move_to_end(key)
        elif len(self.d) == self.maxlen:
            self.d.popitem(last=False)
        self.d[key] = value

    def __delitem__(self, key):
        del self.d[key]

    def __iter__(self):
        return self.d.__iter__()

    def __len__(self):
        return len(self.d)