सबसे तेज़ कतार कंटेनर (सी ++)

Question

मैं कतार और प्राथमिकता कतारों का उपयोग कर रहा हूं, जिसके माध्यम से मैं बहुत सारे डेटा को बहुत तेज़ी से पंप करने की योजना बना रहा हूं।

इसलिए, मैं चाहता हूं कि मेरा क्यू और पीक्यू अतिरिक्त और घटाव के लिए उत्तरदायी हो।

अंतर्निहित कंटेनर के रूप में वेक्टर, सूची या डेक का उपयोग करने की सापेक्ष योग्यता क्या हैं?

अद्यतन: लेखन के समय, माइक सेमुर और स्टीव टाउनसेंड के दोनों जवाब नीचे पढ़ने योग्य हैं। धन्यवाद दोनों!

Answer 1

यह सुनिश्चित करने का एकमात्र तरीका है कि आपके प्रभाव वाले उपयोग मामलों के समान स्थिति में, विकल्प प्रभाव प्रदर्शन कैसे मापें। जैसा कि कहा गया, यहाँ कुछ टिप्पणियों हैं:

std::queue के लिए:

• std::deque आमतौर पर सबसे अच्छा विकल्प है; यह निरंतर समय में सभी आवश्यक संचालन का समर्थन करता है, और जैसे ही यह बढ़ता है, स्मृति में स्मृति आवंटित करता है।
• std::list आवश्यक संचालन का भी समर्थन करता है, लेकिन अधिक स्मृति आवंटन के कारण धीमा हो सकता है; विशेष परिस्थितियों में, आप समर्पित ऑब्जेक्ट पूल से आवंटित करके अच्छे परिणाम प्राप्त कर सकते हैं, लेकिन यह पूरी तरह से सरल नहीं है।
• std::vector का उपयोग नहीं किया जा सकता क्योंकि इसमें pop_front() ऑपरेशन नहीं है; ऐसा ऑपरेशन धीमा हो जाएगा, क्योंकि इसे सभी शेष तत्वों को स्थानांतरित करना होगा।

एक संभावित तेजी से, लेकिन कम सुविधाजनक, वैकल्पिक एक निश्चित-आकार सरणी (जैसे std::array, या एक std::vector कि आप आकार नहीं है) पर एक परिपत्र बफर लागू करने के लिए है। आपको किसी त्रुटि की रिपोर्ट करके, या एक बड़ा बफर आवंटित करने और सभी डेटा की प्रतिलिपि बनाने के मामले को भरने के मामले से निपटने की आवश्यकता होगी।

std::priority_queue के लिए:

• std::vector आमतौर पर सबसे अच्छा विकल्प है; यह तेजी से बढ़ता है (स्मृति आवंटन की संख्या को कम करता है), और यह एक साधारण डेटा संरचना है जो पहुंचने के लिए बहुत तेज़ है - एक इटरेटर को पॉइंटर के चारों ओर एक रैपर के रूप में लागू किया जा सकता है।
• std::deque धीमा हो सकता है क्योंकि यह आम तौर पर रैखिक रूप से बढ़ता है (अधिक स्मृति आवंटन की आवश्यकता होती है), और वेक्टर के साथ पहुंच अधिक जटिल होती है।
• std::list का उपयोग नहीं किया जा सकता क्योंकि यह यादृच्छिक पहुंच प्रदान नहीं करता है।

संक्षेप में - डिफ़ॉल्ट आमतौर पर सबसे अच्छा विकल्प होते हैं, लेकिन यदि गति वास्तव में महत्वपूर्ण है, तो विकल्पों को मापें।

Answer 2

मैं आपकी मूल कतार के लिए std::queue का उपयोग करूंगा जो डिफ़ॉल्ट रूप से deque पर एक रैपर (डिफ़ॉल्ट रूप से) है। कुछ और विशेष उद्देश्य करें यदि यह आपके लिए काम नहीं करता है।

std::priority_queue भी मौजूद है (डिफ़ॉल्ट रूप से vector से अधिक) लेकिन जोड़ा गया अर्थशास्त्र यह आपके संभावित पहुंच पैटर्न के लिए देखे गए परफ के आधार पर आपको अपना खुद का रोल करने की संभावना अधिक बना सकता है।

vector में भंडारण विशेषताओं हैं जो डेटासेट के सामने से हटाने के लिए बहुत ही उपयुक्त हैं। हर बार pop_front पर हर बार किया जा रहा है। एक साधारण कतार के लिए, इससे बचें। क्योंकि अनुबंध द्वारा यह समारोह आप की जरूरत नहीं है के लिए प्रस्ताव दिया

list, किसी भी उच्च मारा कतार लिए बहुत महंगा होने की संभावना है। यह प्राथमिकता कतार के रूप में उपयोग के लिए एक उम्मीदवार हो सकता है लेकिन मेरी वृत्ति हमेशा एसटीएल पर भरोसा करती है।

Answer 3

vector एक स्टैक लागू करेगा क्योंकि आपका तेज़ सम्मिलन अंत में है और तेज़ हटाने भी अंत में है। यदि आप फीफो कतार चाहते हैं, तो vector उपयोग करने के लिए गलत कार्यान्वयन होगा।

deque या list दोनों अंत में निरंतर समय सम्मिलन प्रदान करते हैं। list एलआरयू कैश के लिए अच्छा है जहां आप मध्य तेज़ से तत्वों को स्थानांतरित करना चाहते हैं और जहां आप अपने इटरेटर को वैध रहना चाहते हैं इससे कोई फर्क नहीं पड़ता कि आप उन्हें कितना स्थानांतरित करते हैं। deque आमतौर पर तब प्रयोग किया जाता है जब सम्मिलन और विलोपन अंत में होते हैं।

मुख्य संग्रह जो मुझे आपके संग्रह के बारे में पूछने की ज़रूरत है वह यह है कि क्या उन्हें एकाधिक धागे से एक्सेस किया जाता है या नहीं। मैं मानता हूं कि वे हैं, इस मामले में लॉकिंग को कम करने के लिए आपके प्राथमिक उद्देश्यों में से एक है। यह सबसे अच्छा किया जाता है यदि आपके पास कम से कम एक mult_push और multi_get सुविधा है ताकि आप बिना किसी लॉकिंग के एक समय में एक से अधिक तत्व डाल सकें।

लॉक-फ्री कंटेनर या सेमी-लॉक-फ्री कंटेनर भी हैं।

आपको शायद यह पता चलेगा कि आपकी लॉकिंग रणनीति संग्रह में किसी भी प्रदर्शन की तुलना में अधिक महत्वपूर्ण है जब तक कि आपके ऑपरेशन सभी स्थिर समय न हों।