LRU, कैश एक्सट्रूज़न विधि

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

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

यही है, गणना के परिणाम संग्रहीत किए जाते हैं, जिनके फिर से अनुरोध किए जाने की संभावना है।
इन "लोकप्रिय" प्रश्नों की पहचान कैसे करें? सबसे अच्छा ज्ञात विधि LRU, जो मैं इस लेख में चर्चा करेंगे है।

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

इस पद्धति को लागू करने के लिए, हम दो डाटा संरचनाओं की जरूरत है:

1. Hashtable हैश तालिका, जो सीधे कैश की गई मूल्यों के लिए संग्रहीत किया जाएगा।
2. प्राथमिकता कतार समयक्षेत्र । एक संरचना जो निम्नलिखित कार्यों का समर्थन करती है:
   • महत्व और प्राथमिकता timeQueue.Add (वैल, प्राथमिकता) की एक जोड़ी जोड़ें।
   • निम्नतम प्राथमिकता timeQueue.extractMinValue () के साथ मान निकालें (हटाएं और वापस लौटें ) ।

प्राथमिकता कतार के बारे में यहाँ पढ़ें ।

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

तो यह calculateWithCache के एल्गोरिथ्म तरह दिखेगा:

calculateWithCache(key) { curTime = getCurrentTime(); //         if (key in hashTable) { //       key timeQueue.set(key, curTime); return hashTable[key]; } //    result = calculate(key); //     N ,     if (hashTable.length == N) { minKey = timeQueue.extractMinValue(); hashTable.remove(minKey); } //   ,    hashTable.add(key, result); timeQueue.add(key, curTime); return result; } 

वह सब है। अब, कैश फ्लश करने के बजाय, उपयोगकर्ता को कैश आकार सेट करने की आवश्यकता है। एक ही समय में काम के लिए एक उचित डिफ़ॉल्ट मान का स्वागत किया।

यदि आप प्राथमिकता कतार के प्रभावी कार्यान्वयन का उपयोग करते हैं, तो ओवरहेड को LRU की आवश्यकता होती है O (लॉग एन) ।

मानक पुस्तकालयों में, एक प्राथमिकता कतार को लागू किया जा सकता है, उदाहरण के लिए, C ++ में। लेकिन भले ही इसे लागू नहीं किया गया है, लेकिन आलसी को पढ़ें, आप अनुमान लगा सकते हैं कि एक समान जटिलता के साथ प्राथमिकताओं के साथ कतार को लागू करने के लिए एक संतुलित पेड़ का उपयोग कैसे किया जा सकता है, हालांकि थोड़ा अधिक गुणांक के साथ।

उन लोगों के लिए एक सवाल जो थोड़ा सोचना चाहते हैं। हैश टेबल ऑपरेशन की जटिलता स्थिर है, यह देखते हुए एक निरंतर उपरि कैसे प्राप्त करें?
संकेत: आपको प्राथमिकता कतार को हटाने और नियमित कतार का उपयोग करने की आवश्यकता है :)

आप अधिक जटिल अनुमान लगा सकते हैं जो किसी दिए गए कुंजी कुंजी , या परिणाम की मात्रा, या कुछ और के लिए गणना के समय को ध्यान में रखते हैं।
लेकिन अधिकांश कार्यों में, LRU सबसे अधिक "लोकप्रिय" प्रश्नों को पर्याप्त रूप से परिभाषित करता है।

नोट 1 : आप संग्रहीत मूल्यों की संख्या के बजाय, प्रति कैश मेमोरी की मात्रा को सीमित कर सकते हैं। एल्गोरिथ्म व्यावहारिक रूप से नहीं बदलेगा, केवल लंबाई के बजाय नए मूल्य को संग्रहीत करने के लिए मेमोरी + मेमोरी पर कब्जा कर लिया जाएगा।
नोट 2 : विशेष रूप से बहुस्तरीय मुद्दों से बचा जाता है, क्योंकि यह इस लेख का विषय नहीं है।

अपडेट (टिप्पणी के लिए धन्यवाद ToSHiC22) उन लोगों के लिए, जो थोड़ा और अधिक उन्नत 2Q कार्यान्वयन के लिए एक लिंक है