2012-07-10 30 views
7

मैं शुद्ध एसटीएल (मैं बूस्ट का उपयोग नहीं करना चाहता!) का उपयोग कर एलएफयू (कम बार-बार उपयोग किया जाता है) कैश को लागू करने की कोशिश कर रहा हूं।एसटीएल का उपयोग कर एलएफयू कैश को कैसे कार्यान्वित करें?

आवश्यकताओं हैं: किसी भी तत्व को

  • साहचर्य पहुँच std::map के साथ एक Key की तरह इस्तेमाल करते हैं।
  • सबसे कम प्राथमिकता आइटम को रिलीज़ करने की क्षमता (UsesCount विशेषता का उपयोग करके)।
  • किसी भी आइटम की प्राथमिकता (UsesCount) को अपडेट करने की क्षमता।

समस्याएं हैं:

  • अगर मैं साहचर्य का उपयोग और std::make_heap, std::push_heap और std::pop_heap के लिए वेक्टर के लिए iterators के एक कंटेनर के रूप में वस्तुओं के कंटेनर (Key, Value, UsesCount), std::map रूप std::vector का उपयोग वेक्टर के भीतर प्राथमिकता कतार कार्यान्वयन के रूप में, मानचित्र में itertors ढेर परिचालन के बाद मान्य नहीं हैं।
  • अगर मैं पिछले विन्यास में std::list (या std::map) के बजाय std::vector उपयोग करते हैं, std::make_heap आदि उनके iterators क्योंकि संकलित नहीं किया जा सकता aritmetic समर्थन नहीं करता।
  • यदि मैं std::priority_queue का उपयोग करना चाहता हूं, तो मेरे पास आइटम प्राथमिकता अपडेट करने की क्षमता नहीं है।

प्रश्न हैं:

  • मैं कुछ स्पष्ट कर इस समस्या को हल किया जा सकता लापता हूँ?
  • क्या आप मुझे उदाहरण के रूप में पिछले आवश्यकताओं को एलएफयू कैश की बैठक के कुछ शुद्ध सी ++/एसटीएल कार्यान्वयन के लिए इंगित कर सकते हैं?

आपकी अंतर्दृष्टि के लिए धन्यवाद।

+3

"मानचित्र में उपरोक्त ढेर संचालन के बाद मान्य नहीं हैं" - इसे अन्य तरीकों से करने के द्वारा ठीक करें - डेटा को 'मानचित्र' में रखें, जहां अन्य तत्व डाले जाने पर भी इसे स्थानांतरित नहीं किया जाएगा/मिट। फिर अपने वेक्टर में मैप इटरेटर्स डालें और इससे एक ढेर बनाएं। आप शायद किसी आइटम की प्राथमिकता को कुशलता से अपडेट करने की क्षमता खो देंगे, हालांकि, यह कोई जवाब नहीं है। –

+0

एक और विचार के लिए धन्यवाद जो मेरे दिमाग को पार नहीं करता है। लेकिन अगर मेरे पास 'std :: map' iterators का 'std :: vector' होगा, तो मैं उनके तुलना ऑपरेटर को कैसे परिभाषित कर सकता हूं, जो' UsesCount' विशेषता 'पर पॉइंट ऑब्जेक्ट के अंदर दिखाई देगा, ताकि' आइटम प्रविष्टि या 'UsesCount' अपडेट के बाद std :: make_heap'? – Blackhex

+3

तुलनात्मक मिक्सर का उपयोग करके: 'बूल ऑपरेटर() (मैपइटर ए, मैपइटरबी) {एक ए-> दूसरा। यूसेउंट < b-> सेकेंड। यूसेउंट; } ' – Useless

उत्तर

2

*_heap फ़ंक्शंस और वेक्टर का उपयोग करके आपका मेक कार्यान्वयन एक अच्छा फिट प्रतीत होता है। हालांकि इसके परिणामस्वरूप धीमे अपडेट होंगे। अंतर्निहित डेटा संरचना के रूप में वेक्टर का उपयोग करके प्रत्येक कंटेनर के लिए आपके द्वारा सामना किए जाने वाले इटरेटर अमान्यता के बारे में समस्या सामान्य है। यह दृष्टिकोण boost::heap::priority_queue द्वारा भी लिया गया है, लेकिन यह उपर्युक्त कारण के लिए एक परिवर्तनीय इंटरफ़ेस प्रदान नहीं करता है। अन्य boost::heap data-structures ढेर को अद्यतन करने की क्षमता प्रदान करते हैं।

कुछ ऐसा जो थोड़ा अजीब लगता है: भले ही आप std::priority_queue का उपयोग करने में सक्षम होंगे, फिर भी आपको इटरेटर अमान्यता समस्या का सामना करना पड़ेगा।

सीधे अपने प्रश्नों का उत्तर देने के लिए: आप कुछ स्पष्ट नहीं खो रहे हैं। std::priority_queue उतना उपयोगी नहीं है जितना होना चाहिए। सबसे अच्छा तरीका अपने ही ढेर कार्यान्वयन को लिखना है जो अपडेट का समर्थन करता है। इसे पूरी तरह से एसटीएल संगत बनाने के लिए (विशेष रूप से आवंटक जागरूक) बल्कि मुश्किल है और एक आसान काम नहीं है। इसके ऊपर, एलएफयू कैश को लागू करें।

पहले चरण के लिए, प्रयास के विचार को प्राप्त करने के लिए बूस्ट कार्यान्वयन को देखें। मैं दूसरे के लिए किसी भी संदर्भ कार्यान्वयन से अवगत नहीं हूँ।

इटरेटर अमान्यता के आसपास काम करने के लिए आप हमेशा एक और कंटेनर में संकेतक चुन सकते हैं, हालांकि आपको इसे टालने का प्रयास करना चाहिए क्योंकि यह अतिरिक्त लागत बनाता है और काफी गन्दा हो सकता है।

+0

आप '* _heap' के साथ प्राथमिकता कैसे अपडेट करते हैं? मुझे लगता है कि यह सिर्फ 'प्राथमिकता_क्यू' नहीं है जो यहां नौकरी नहीं कर सकता: मानक ढेर कार्य नहीं कर सकते हैं। तो प्रश्नकर्ता को एक अलग ढेर कार्यान्वयन की जरूरत है। मुझसे गलती भी हो सकती है। –

+1

@SteveJessop शायद मैं यहां गलत हूं, लेकिन प्राथमिकता कॉलिंग के अपडेट के बाद 'make_heap' को फिर से ढेर को ठीक करना चाहिए। हालांकि, यह शायद इष्टतम से दूर है। – pmr

+0

सहमत हुए। वह ढेर invariant बहाल करेगा, लेकिन यह 'ओ (एन) 'है। अन्य ढेर कार्यान्वयन 'ओ (लॉग एन) में वृद्धि/कमी/अद्यतन कर सकते हैं। –

1

एक दो डाटा संरचनाओं रखने की तुलना में कुछ सरल तरीका:

  • सिर्फ एक नक्शा है, जो उनके मूल्य/उपयोग गिनती जोड़ी के लिए अपनी चाबी नक्शे रहते हैं।
  • जब कैश भरा हुआ है:
    • नक्शा तत्वों (O(n))
    • उपयोग std::nth_element सबसे खराब 10% को खोजने के लिए करने के लिए iterators का एक वेक्टर बनाने (O(n))
    • मानचित्र से सभी को हटाएं (O(n log n))

तो, कैश करने के लिए एक नया तत्व जोड़ सामान्य मामले O(log n), सबसे ज्यादा मामले O(n log n) है, और O(log n) परिशोधित।

एलएफयू कैश में सबसे खराब 10% को कम करना मुश्किल हो सकता है, क्योंकि नई प्रविष्टियों को शीर्ष 9 0% बनाना है या वे कटौती कर रहे हैं। फिर फिर, यदि आप केवल एक तत्व को हटाते हैं तो नई प्रविष्टियों को अभी भी अगली नई प्रविष्टि से पहले नीचे उतरने की आवश्यकता है, या वे कट गए हैं, और उनके पास ऐसा करने में कम समय है। तो इस बात पर निर्भर करता है कि एलएफयू आपके लिए सही कैशिंग रणनीति क्यों है, इसमें मेरा परिवर्तन गलत रणनीति हो सकता है, या यह अभी भी ठीक हो सकता है।

+0

आप हैश मानचित्र वाले उन ओपों में से कई के लिए ओ (1) प्राप्त कर सकते हैं। – Puppy

+0

@DeadMG: अच्छा बिंदु, और प्रश्नकर्ता एसटीएल निर्दिष्ट करता है, इसलिए निश्चित रूप से एक उपलब्ध है। सी ++ 03 में नहीं है (बूस्ट या टीआर 1 के बिना) –

संबंधित मुद्दे