caching - تحديد حجم قاموس python




dictionary lru (7)

أود أن أعمل مع dict في python ، ولكن قلل عدد أزواج المفاتيح / القيم إلى X. وبعبارة أخرى ، إذا كان dict يقوم حاليًا بتخزين أزواج X مفتاح / قيمة وأقوم بإجراء إدخال ، أود الحصول على الأزواج الموجودة ليتم إسقاطها. سيكون من اللطيف إذا كان هذا هو أقل مفتاح تم إدخاله / دخوله مؤخرًا ولكن هذا ليس ضروريًا تمامًا.

إذا كان هذا موجودًا في المكتبة القياسية ، فالرجاء حفظ بعض الوقت والإشارة إليه!


Answers

هنا ، حل Python 2.6+ بسيط ، لا LRU (في بايثون أقدم يمكنك القيام بشيء مماثل مع UserDict.DictMixin ، ولكن في 2.6 وأفضل أن لا ينصح بذلك ، وأبجديات من 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 هو لسوء الحظ bilerplatey لكنه يضمن أن كل طريقة أخرى يتم توفيرها بشكل صحيح من قبل collections.MutableDict .MutableDict.


كانت هناك العديد من الإجابات الجيدة ، لكني أريد أن أشير إلى تنفيذ بسيط ، pythonic لـ LRU cache. إنها مشابهة لإجابة أليكس مارتيللي.

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)

يمكنك إنشاء فئة قاموس مخصص عن طريق subclassing dict. في حالتك ، يجب عليك تجاوز __setitem__ للتحقق من __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'

بيثون 2.7 و 3.1 ديك OrderedDict وهناك تطبيقات بيثون نقية OrderedDict سابق.

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)

يجب أيضًا تجاوز الطرق الأخرى التي يمكنها إدراج عناصر ، مثل التحديث. الاستخدام الأساسي لـ OrderedDict هو حتى تتمكن من التحكم في ما يمكن أن ينفجر بسهولة ، وإلا ستعمل الطريقة المعتادة.


هنا هو مخبأ LRU بسيطة وفعالة مكتوبة مع رمز Python بسيط التراب الذي يعمل على أي إصدار بيثون 1.5.2 أو في وقت لاحق:

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))

سوف توفر لك cachetools تنفيذ لطيفة من رسم الخرائط Hashes أن يفعل هذا (ويعمل على الثعبان 2 و 3).

مقتطفات من الوثائق:

لغرض هذه الوحدة ، تعد ذاكرة التخزين المؤقت عبارة عن خريطة قابلة لتغيير حجم أقصى ثابت. عندما تكون ذاكرة التخزين المؤقت ممتلئة ، أي عن طريق إضافة عنصر آخر ، ستتجاوز ذاكرة التخزين المؤقت الحد الأقصى للحجم ، يجب أن تختار ذاكرة التخزين المؤقت أي عنصر (عناصر) يتم التخلص منه بناءً على خوارزمية ذاكرة التخزين المؤقت المناسبة.


في حالتك ، ما يمكنك القيام به هو:

z = dict(x, **y)

سيقوم هذا ، كما تريد ، بوضع الأمر الأخير في z ، وجعل قيمة المفتاح b يتم تجاوزها بشكل صحيح بواسطة قيمة dict الثانية ( y ):

>>> timeit.Timer("dict(x, **y)", "x = dict(zip(range(1000), range(1000)))\ny=dict(zip(range(1000,2000), range(1000,2000)))").timeit(100000)
15.52571702003479
>>> timeit.Timer("temp = x.copy()\ntemp.update(y)", "x = dict(zip(range(1000), range(1000)))\ny=dict(zip(range(1000,2000), range(1000,2000)))").timeit(100000)
15.694622993469238
>>> timeit.Timer("dict(x.items() + y.items())", "x = dict(zip(range(1000), range(1000)))\ny=dict(zip(range(1000,2000), range(1000,2000)))").timeit(100000)
41.484580039978027

إذا كنت تستخدم Python 3 ، فستكون أكثر تعقيدًا. لإنشاء z :

z1 = dict(x.items() + y.items())
z2 = dict(x, **y)




python caching dictionary lru