पायथन में तत्वों की संख्या पर एक सीमा के साथ एक कैश को लागू करना - समाधान: सरल और अधिक जटिल

कार्य विवरण

मान लीजिए कि हमें एक निश्चित सेवा करने की आवश्यकता है जो अनुरोध पर हमें कोई भी जानकारी देगी और जितनी जल्दी हो सके इसे दे देगी। कोई भी सामान्य व्यक्ति इसके लिए क्या करता है? यह सबसे अधिक बार अनुरोधित डेटा को कैश करता है। वहीं, अगर आप भविष्य के बारे में थोड़ा भी सोचते हैं, तो कैश का आकार सीमित होना चाहिए।
कार्यान्वयन में आसानी के लिए, पायथन के मामले में, हम कैश में तत्वों की संख्या पर प्रतिबंध लगाते हैं ( यहाँ यह माना जाता है कि डेटा आकार में कम या ज्यादा समान है, और यह भी निर्दिष्ट करता है कि किसी पायथन ऑब्जेक्ट द्वारा वास्तव में कब्जा की गई मेमोरी की मात्रा निर्धारित करना एक बहुत ही गैर-तुच्छ कार्य है, जो रुचि रखते हैं। उसे यहां आने दें ), और कैश का उपयोग जितनी बार संभव हो जानकारी रखने के लिए - हम इसे कम से कम हाल ही में उपयोग किए जाने के सिद्धांत पर बनाएंगे, अर्थात्। जितना अधिक समय पहले उन्होंने जानकारी के एक टुकड़े का अनुरोध किया, उतने अधिक मौके उनके पास कैश के "उड़ने" के थे।

मैं इस लेख में दो समाधानों (सरल और अधिक जटिल) के बारे में बात करूंगा।

दार्शनिक वापसी

मैंने देखा कि अक्सर पायथन में लिखे गए कोड मेमोरी खपत या गति के संदर्भ में अनुकूलन नहीं दिखाते हैं ( यहां आप पासिंग में देख सकते हैं कि यह केवल प्रोग्रामर की गलती नहीं है जो भाषा का उपयोग करते हैं, बस कोई अच्छा टूलकिट नहीं है, या कम से कम इसके बारे में पता नहीं है ( हां, मैं cProfile से अवगत हूं, लेकिन यह हमेशा मदद नहीं करता है, उदाहरण के लिए, इसमें अटैच-डिटैच नहीं होता है; मेमोरी लीक देखने के लिए आमतौर पर दिल के बेहोश होने की स्थिति नहीं होती है, अगर पिंपल खत्म हो गया है ...), अगर कोई मुझसे कहता है, तो मैं आभारी रहूंगा। )। मूल रूप से, यह और भी सही है, क्योंकि आमतौर पर पायथन का उपयोग तब किया जाता है जब प्रोग्राम का निष्पादन समय या मेमोरी की खपत महत्वपूर्ण नहीं होती है, लेकिन कोड को लिखने में लगने वाला समय और इसके आगे के समर्थन की सादगी महत्वपूर्ण होती है, इसलिए एक स्पष्ट, यद्यपि कम किफायती, समाधान अधिक सुविधाजनक होगा।
हालांकि उपरोक्त का मतलब यह नहीं है कि किसी भी पायथन कोड को "किसी भी तरह" लिखा जाना चाहिए। इसके अलावा, कभी-कभी प्रदर्शन और मेमोरी खपत महत्वपूर्ण हो सकती है, भले ही कोड एक अच्छे प्रोसेसर और मेमोरी के साथ सर्वर मशीन पर चलता हो।
बस इस तरह के एक मामले (सीपीयू समय की कमी) और मुझे इस मुद्दे का अध्ययन करने के लिए और एक कैशिंग वर्ग को दूसरे के साथ बदलने के लिए।

सरल उपाय

यह अक्सर कहा जाता है - "एक सरल समाधान सही है", हालांकि प्रोग्रामिंग के मामले में यह हमेशा के मामले से बहुत दूर है, क्या यह है? हालांकि, अगर कोई कैश प्रदान करने का कार्य है, लेकिन गति के लिए कोई विशेष आवश्यकताएं नहीं हैं (उदाहरण के लिए, जो इस कैश का उपयोग करता है वह अपने आप में बहुत धीमा है, और यह जटिल कार्यान्वयन में निवेश करने का कोई मतलब नहीं है), तो आप तुच्छ समाधान के साथ प्राप्त कर सकते हैं।

कार्यान्वयन

तो, एक अपेक्षाकृत सरल समाधान:

import weakref class SimpleCache: def __init__(self, cacheSize): self.cache = weakref.WeakValueDictionary() self.cache_LRU = [] self.cacheSize = cacheSize def __getitem__(self, key): # no exception catching - let calling code handle them if any value = self.cache[key] return self.touchCache(key, value) def __setitem__(self, key, value): self.touchCache(key, value) def touchCache(self, key, value): self.cache[key] = value if value in self.cache_LRU: self.cache_LRU.remove(value) self.cache_LRU = self.cache_LRU[-(self.cacheSize-1):] + [ value ] return value 

के उपयोग

आप सृजन के बाद इस तरह के कैश के साथ काम कर सकते हैं, जैसा कि एक नियमित रूप से किया जाता है, लेकिन जब एक तत्व को पढ़ना / लिखना यह कतार के अंत में रखा जाएगा, और WeakValueDictionary () और एक सूची के संयोजन के कारण जो कोई और अधिक तत्व संग्रहीत नहीं करता है, तो हमें संख्या पर एक सीमा मिलती है। सहेजा गया डेटा।
इसलिए कोड के एक टुकड़े को निष्पादित करने के बाद

 cache = SimpleCache(2) cache[1] = 'a' cache[2] = 'b' cache[3] = 'c' 

केवल प्रविष्टियाँ 'b' और 'c' कैश में रहेंगी ('a', जैसा कि सबसे पुराना है, पहले से लिखा होगा)।

फायदे और नुकसान

लाभ सापेक्ष सादगी है (लगभग 20 पंक्तियों की कोड, WeakValueDictionary पर प्रलेखन पढ़ने के बाद, ऑपरेशन का सिद्धांत स्पष्ट हो जाता है)।
नुकसान काम की गति है, क्योंकि हर बार जब आप कैश को "टच" करते हैं, तो आपको पूरी सूची को फिर से बनाना होगा, एक तत्व को उसके मनमाने स्थान से हटाना होगा (वास्तव में, सूची के साथ काम करने पर लंबे ऑपरेशन का एक पूरा गुच्छा होता है, उदाहरण के लिए, "यदि self.cache_LRU में मूल्य - सूची में एक रेखीय खोज है, तो) .remove () - एक बार फिर एक रेखीय खोज, फिर एक और टुकड़ा लिया जाता है - यानी सूची की लगभग पूरी प्रतिलिपि बनाई जाती है)। एक शब्द में, अपेक्षाकृत लंबा।

कठिन निर्णय

अब आइए विचार करें - ऐसे वर्ग को कैसे त्वरित किया जा सकता है? जाहिर है, हमारे साथ मुख्य समस्या यह है कि कैश_RU को अद्यतित रखा जा रहा है - जैसा कि मैंने कहा, इसके लिए खोज करना, फिर एक आइटम को हटाना और इसे फिर से बनाना महंगा ऑपरेशन है। यहाँ, एक द्विदिश लिंक्ड सूची जैसी चीज़ हमारी सहायता के लिए आएगी - यह हमें "अंतिम उपयोग - अंत में" समर्थन प्रदान करेगी, लेकिन ठीक है, WeakValueDictionary () इस सूची पर त्वरित खोज के साथ मदद करेगी (शब्दकोष खोज रैखिक तालमेल की तुलना में बहुत तेज़ है, चूंकि पायथन के अंदर से है। शब्दकोश कुंजी हैश द्वारा द्विआधारी पेड़ों की तरह कुछ को लागू करते हैं (यहां ओस्टाप का सामना करना पड़ा - मैं ईमानदारी से कह सकता हूं कि मैं स्रोत को नहीं देखता हूं, इसलिए मैं केवल अनुमान लगाता हूं कि शब्दकोश खोज कैसे काम करता है)

कार्यान्वयन

सबसे पहले, एक वर्ग बनाएं - एक सूची आइटम, जिसमें हम संग्रहीत डेटा को लपेटेंगे:

  class Element(object): __slots__ = ['prev', 'next', 'value', '__init__', '__weakref__'] def __init__(self, value): self.prev, self.next, self.value = None, None, value 

यहां इसे __slots__ के रूप में ऐसी चीज़ के उपयोग पर ध्यान दिया जाना चाहिए, जो एक ही वर्ग कार्यान्वयन की तुलना में स्मृति और थोड़ा - बहुत प्रदर्शन को बचाने की अनुमति देता है, लेकिन इस विशेषता के बिना ( आधिकारिक दस्तावेज में इसे क्या खाया जाता है)।
अब एक कैश क्लास बनाएं (हम "बचने के लिए" के अंदर तत्व वर्ग को चिपकाएँगे):

 import weakref class FastCache: class Element(object): __slots__ = ['prev', 'next', 'value', '__init__', '__weakref__'] def __init__(self, value): self.prev, self.next, self.value = None, None, value def __init__(self, maxCount): self.dict = weakref.WeakValueDictionary() self.head = None self.tail = None self.count = 0 self.maxCount = maxCount def _removeElement(self, element): prev, next = element.prev, element.next if prev: assert prev.next == element prev.next = next elif self.head == element: self.head = next if next: assert next.prev == element next.prev = prev elif self.tail == element: self.tail = prev element.prev, element.next = None, None assert self.count >= 1 self.count -= 1 def _appendElement(self, element): if element is None: return element.prev, element.next = self.tail, None if self.head is None: self.head = element if self.tail is not None: self.tail.next = element self.tail = element self.count += 1 def get(self, key, *arg): element = self.dict.get(key, None) if element: self._removeElement(element) self._appendElement(element) return element.value elif len(*arg): return arg[0] else: raise KeyError("'%s' is not found in the dictionary", str(key)) def __len__(self): return len(self.dict) def __getitem__(self, key): element = self.dict[key] # At this point the element is not None self._removeElement(element) self._appendElement(element) return element.value def __setitem__(self, key, value): try: element = self.dict[key] self._removeElement(element) except KeyError: if self.count == self.maxCount: self._removeElement(self.head) element = FastCache.Element(value) self._appendElement(element) self.dict[key] = element def __del__(self): while self.head: self._removeElement(self.head) 

यहां आप निम्नलिखित महत्वपूर्ण / दिलचस्प बिंदुओं पर ध्यान दे सकते हैं:

• प्राप्त () विधि का कार्यान्वयन शब्दकोशों के लिए मानक से थोड़ा अलग है, जैसा कि यदि डिफ़ॉल्ट मान सेट नहीं है, और कुंजी गायब है, तो एक अपवाद फेंकता है (कैश [कुंजी] के समान काम करता है), और यदि कोई डिफ़ॉल्ट मान है, तो उसे लौटाता है
• __del__ विधि आवश्यक है, अन्यथा हम पूरे कैश का एक रिसाव प्राप्त करते हैं (या हम प्राप्त कर सकते हैं) - आखिरकार, सूची के सभी तत्व एक-दूसरे को संदर्भित करते हैं, जिसका अर्थ है कि उनके लिंक काउंटर बिना सहायता के कभी भी रीसेट नहीं होंगे; वैसे, जैसा कि यह निकला, बिल्ट-इन (कम से कम 2.6) कचरा संग्रहकर्ता, हालांकि यह सबसे सरल लिंक चक्र एकत्र करने के लिए लगता है, इस सूची का सामना नहीं करता है
• यदि आप चाहें, तो आप हत्यारों को फेंककर प्रदर्शन को थोड़ा बढ़ा सकते हैं

के उपयोग

यह पिछले कार्यान्वयन के लिए पूरी तरह से अनुरूप है (और अंदर तर्क समान है, यह न केवल पायथन में निर्मित सूची प्रकार का उपयोग करता है, बल्कि शतरंज और कवियों के साथ इसकी द्विदिश सूची को लागू करता है)।

अच्छे प्रदर्शन के साथ एक और सरल समाधान।

धन्यवाद टिप के लिए seriyPS !
एक और समाधान सामने आया है जो पहले की तरह ही सरल है (यदि सरल भी नहीं है) और एक ही समय में लगभग उतनी ही तेजी से जटिल काम करता है। इसलिए कार्यान्वयन:

 from collections import OrderedDict class ODCache(OrderedDict): def __init__(self, cacheSize): self.cacheSize = cacheSize OrderedDict.__init__(self) def __getitem__(self, key): value = OrderedDict.__getitem__(self, key) return self._touchCache(key, value) def __setitem__(self, key, value): self._touchCache(key, value) def _touchCache(self, key, value): try: OrderedDict.__delitem__(self, key) except KeyError: pass OrderedDict.__setitem__(self, key, value) toDel = len(self) - self.cacheSize if toDel > 0: for k in OrderedDict.keys(self)[:toDel]: OrderedDict.__delitem__(self, k) return value 

एक और समाधान अच्छा प्रदर्शन है।

टिप्पणियों से समाधान (मेरे द्वारा उपयोग किए गए परीक्षणों के अनुसार गति में अग्रणी है), धन्यवाद tbd :

 class ListDictBasedCache(object): __slots__ = ['__key2value', '__maxCount', '__weights'] def __init__(self, maxCount): self.__maxCount = maxCount self.__key2value = {}# key->value self.__weights = []# keys ordered in LRU def __updateWeight(self, key): try: self.__weights.remove(key) except ValueError: pass self.__weights.append(key)# add key to end if len(self.__weights) > self.__maxCount: _key = self.__weights.pop(0)# remove first key self.__key2value.pop(_key) def __getitem__(self, key): try: value = self.__key2value[key] self.__updateWeight(key) return value except KeyError: raise KeyError("key %s not found" % key) def __setitem__(self, key, value): self.__key2value[key] = value self.__updateWeight(key) def __str__(self): return str(self.__key2value) 

तुलना

आरोप एक बात है, और निष्पक्ष आंकड़े दूसरे हैं। इसलिए, मैं इसके लिए अपने शब्द लेने के लिए नहीं कहता, इसके विपरीत - हम इन वर्गों को मापेंगे!
यहां पाइथन में बनाया गया टाइमटाइम मॉड्यूल हमारी सहायता के लिए आता है:

 class StubClass: def __init__(self, something): self.something = something def testCache(cacheClass, cacheSize, repeat): d = cacheClass(cacheSize) for i in xrange(repeat * cacheSize): d[i] = StubClass(i) import random class testCacheReadGen: def __init__(self, cacheClass, cacheSize): d = cacheClass(cacheSize) for i in xrange(cacheSize): d[i] = StubClass(i) self.d = d self.s = cacheSize def __call__(self, repeat): cacheSize, d = self.s, self.d for i in xrange(cacheSize * repeat): tmp = d[random.randint(0, cacheSize-1)] def minMaxAvg(lst): return min(lst), max(lst), 1.0 * sum(lst) / len(lst) import timeit def testAllCaches(classes, cacheSize, repeats): templ = '%s: min %.5f, max %.5f, avg %.5f' genmsg = lambda cls, res: templ % ((cls.__name__.ljust(20),) + tuple(minMaxAvg(res))) for cls in classes: t = timeit.Timer(lambda: testCache(cls, cacheSize, repeats[0])) print genmsg(cls, t.repeat(*repeats[1:])) def testAllCachesRead(classes, cacheSize, repeats): templ = '%s: min %.5f, max %.5f, avg %.5f' genmsg = lambda cls, res: templ % ((cls.__name__.ljust(20),) + tuple(minMaxAvg(res))) for cls in classes: tst = testCacheReadGen(cls, cacheSize) t = timeit.Timer(lambda: tst(repeats[0])) print genmsg(cls, t.repeat(*repeats[1:])) if __name__ == '__main__': print 'write' testAllCaches((SimpleCache, FastCache, ODCache, ListDictBasedCache), 100, (100, 3, 3)) print 'read' testAllCachesRead((SimpleCache, FastCache, ODCache, ListDictBasedCache), 100, (100, 3, 3)) 

मेरी मशीन पर लॉन्च के परिणाम (Intel Core i5 2540M 2.6GHz, Win7 64-bit, ActivePython 2.7.2 x64-bit):

  लिखने
 सिंपलचेच: न्यूनतम 9.36119, अधिकतम 9.49077, औसत 9.42536
 FastCache: न्यूनतम 0.39449, अधिकतम 0.41835, औसत 0.40880
 ODCache: न्यूनतम 0.79536, अधिकतम 0.82727, औसत 0.81482
 ListDictBasedCache: न्यूनतम 0.25135, अधिकतम 0.27334, औसत 0.26000
 पढ़ना
 सिंपल कैचे: न्यूनतम 9.61617, अधिकतम 9.73143, 9.66337
 FastCache: न्यूनतम 0.19294, अधिकतम 0.21941, 0.20552 औसत
 ODCache: न्यूनतम 0.22270, अधिकतम 0.25816, औसत 0.23911
 ListDictBasedCache: न्यूनतम 0.16475, अधिकतम 0.17725, औसत 0.16911 

सरल और जटिल समाधानों के बीच का अंतर काफी ध्यान देने योग्य है - लगभग 20 बार! ऑर्डरडीडिक्ट पर निर्णय प्रदर्शन के मामले में पिछड़ जाता है, लेकिन केवल थोड़ा ही। आगे के निष्कर्षों के लिए, अधिक जटिल माप करना आवश्यक है जो कैश कार्य की ख़ासियत को दर्शाते हैं - सूचना के मनमाने टुकड़ों तक त्वरित पहुंच, और कुछ रैखिक एक नहीं, जैसा कि ऊपर इस्तेमाल किया गया है।

स्मृति की खपत के लिए - पिछली स्क्रिप्ट को किसी अन्य मुख्य अनुभाग के साथ चलाएं और कार्य प्रबंधक के माध्यम से पायथन इंटरप्रेटर की स्मृति उपयोग देखें:

 if __name__ == '__main__': import time print 'measure me - no cache' try: while True: time.sleep(10) except: # let user interrupt this with Ctrl-C pass testCache(FastCache, 1000, 1) print 'measure me - cached' while True: time.sleep(10) exit() 

माप परिणाम तालिका में हैं:

कैश क्लास	कैश बनाने से पहले	कैश बनाने के बाद	कैश की खपत
SimpleCache	4228K	4768K	540K
FastCache	4232K	4636K	404K
ODCache	4496K	4936K	440K
ListDictBasedCache	4500K	4880K	380K

जैसा कि आप देख सकते हैं, एक जटिल समाधान न केवल तेजी से (~ 20 गुना) तत्वों को जोड़ता है, बल्कि एक साधारण की तुलना में थोड़ी कम मेमोरी भी खपत करता है।

उस विशिष्ट कार्य में, जो मैंने इस तरह के कैश को बनाकर हल किया था, इसके स्थान पर मुझे प्रतिक्रिया समय को 90 सेकंड से घटाकर लगभग 70 (अधिक सघन प्रोफाइलिंग और पुनर्लेखन लगभग सभी प्रतिक्रिया जनरेशन लॉजिक की अनुमति दी गई), फिर प्रतिक्रिया समय को 30 सेकंड तक लाने में मदद की, लेकिन यह पहले से ही था एक और कहानी)।