사전의 크기를 제한하는 방법

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

---

파이썬에서 사전으로 작업하고 싶지만 키/값 쌍의 수를 X로 제한합니다. 즉, 사전이 현재 X 키/값 쌍을 저장하고 있고 삽입을 수행하는 경우 다음 중 하나를 원합니다. 삭제할 기존 쌍. 가장 최근에 삽입/접근하는 키라면 좋겠지만 완전히 필요한 것은 아닙니다.

이것이 표준 라이브러리에 있다면 시간을 절약하고 지적해 주십시오!

---

Python 2.7 및 3.1에는 OrderedDict 가 있으며 이전 Python에 대한 순수 Python 구현이 있습니다.

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것입니다. 그렇지 않으면 일반 이 작동합니다.

---

cachetools 는 이를 수행하는 Mapping Hashes의 멋진 구현을 제공합니다(파이썬 2 및 3에서 작동함).

문서 발췌:

이 모듈의 목적을 위해 캐시는 고정된 최대 크기의 변경 가능한 매핑입니다. 캐시가 가득 차면, 즉 다른 항목을 추가하여 캐시가 최대 크기를 초과할 때 캐시는 적절한 캐시 알고리즘에 따라 폐기할 항목을 선택해야 합니다.

---

다음은 LRU가 없는 간단한 Python 2.6+ 솔루션입니다(이전 Python 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))

에 명시 적으로 위임 - 다른 답변이 언급 한 바와 같이, 당신은 아마 서브 클래스 딕셔너리에 원하지 않는 self.d불행하게도 boilerplatey이지만 않습니다 보장을 다른 모든 방법이 제대로에 의해 공급된다 collections.MutableMapping.

---

다음은 Python 버전 1.5.2 이상에서 실행되는 간단한 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))

---

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.
• 사전은 순서가 지정되지 않기 때문에 가장 최근에 추가된 키가 무엇인지 알지 못합니다.
  • 2.7에서는 가 도입 collections.OrderedDict되지만 지금은 키를 별도로 순서대로 유지하면 잘 작동합니다( collections.deque대기열로 사용).
  • 가장 오래된 것을 얻는 것이 그다지 중요하지 않다면 이 popitem방법을 사용하여 임의의 항목 하나를 삭제할 수 있습니다 .
• 나는 가장 오래된 것을 첫 번째 삽입을 의미하는 것으로 해석했습니다. LRU 항목을 제거하려면 약간 다른 작업을 수행해야 합니다. 가장 확실한 효율적인 전략은 (실제 값과 함께) dict 값으로 저장된 노드 자체에 대한 참조가 있는 이중 연결 키 목록을 유지하는 것입니다. 이것은 더 복잡해지고 순수한 Python으로 구현하면 많은 오버헤드가 발생합니다.

---

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'

---

좋은 답변이 많이 있었지만 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)

ReferenceURL : https://stackoverflow.com/questions/2437617/how-to-limit-the-size-of-a-dictionary