टिप 23. सॉर्ट किए गए वैक्टर के साथ सहयोगी कंटेनरों को बदलने पर विचार करें।

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

शुरुआत के लिए थोड़ा सिद्धांत, (जो लोग जानते हैं कि वेक्टर और मानचित्र को पढ़ने की आवश्यकता नहीं है)। एसटीएल में मानचित्र कुंजी-मूल्य जोड़े के भंडारण के लिए एक सहयोगी कंटेनर है। इसमें डेटा को सॉर्ट किए गए रूप में संग्रहीत किया जाता है, हालांकि C ++ मानक कार्यान्वयन को निर्दिष्ट नहीं करता है, अक्सर मानचित्र को लाल-काले पेड़ के रूप में लागू किया जाता है, जिसमें प्रत्येक तत्व दो बच्चों को इंगित करता है। एसटीएल में वेक्टर सिर्फ तत्वों का एक कंटेनर है जो यह सुनिश्चित करता है कि इसमें संग्रहीत डेटा खंडित नहीं है। इसमें एक प्रभावी खोज को सॉर्टिंग और आगे बाइनरी खोज द्वारा आयोजित किया जा सकता है। जैसा कि पहले मामले में, खोज की जटिलता हे (ln (n)) है। दूसरे मामले में बेहतर कैशिंग के कारण गति में अंतर अलग-अलग होगा (डेटा स्थानीय रूप से स्थित है, और भंडारण के लिए कम मेमोरी की आवश्यकता है)।

सम्मिलन और खोज की गति की तुलना करने के लिए, एक परीक्षण कार्यक्रम लिखा गया था जो दो प्रकार के माप लेता है - कंटेनरों में यादृच्छिक मूल्यों (यादृच्छिक (3)) को रिकॉर्ड करते हुए, समय को मापते हुए (गेटाइमोफ़डे का उपयोग करते हुए), और एक निश्चित समय के लिए कंटेनर में यादृच्छिक मूल्यों की खोज करना ( 10 एस)। इस प्रकार, कंटेनर में डेटा डालने का समय और कंटेनर में एक समय अंतराल पर खोजों की संख्या को मापा जाता है।

इंस्ट्रुमेंटेशन:
हार्डवेयर: स्वैप प्रोसेसर (इंटेल Xeon E5420) सर्वर स्वैप फाइल के बिना।
सॉफ्टवेयर: कर्नेल के साथ Ubuntu सर्वर 2.6.28, gcc 4.3.3।
कुंजियों के साथ एक परियोजना को संकलित करना: -O3 -फेलिड-कंस्ट्रक्टर्स -fno- अपवाद -fno-rtti -funroll-loops -ffast-math -fomit-फ़्रेम-पॉइंटर-मॉर्च = core2
प्रत्येक परीक्षण कई बार (एन = 10) चलाया गया था, जबकि एक निश्चित पैरामीटर के न्यूनतम, अधिकतम और औसत मूल्य दर्ज किए गए थे। परीक्षणों के दौरान, प्राप्त मूल्यों में अंतर कम से कम हो गया था (सर्वर पर लोड को कम करना, सीपीयू आत्मीयता स्थापित करना)।

कंटेनर में आइटम सम्मिलित करते समय प्राप्त डेटा



पहला ग्राफ तत्वों की संख्या के आधार पर कंटेनरों के लिए सम्मिलन और छँटाई के समय की निर्भरता को दर्शाता है। दोनों तराजू लॉगरिदमिक हैं, इसलिए स्पष्टता के लिए, एक और वक्र का निर्माण किया गया था जो वेक्टर के लिए सम्मिलन और छँटाई के समय को दर्शाता है - यह एक धराशायी रेखा के साथ दिखाया गया है। क्षैतिज काली रेखाएं प्रत्येक प्रयोग के लिए त्रुटि दिखाती हैं - अधिकतम और न्यूनतम मान। जैसा कि आप देख सकते हैं, 1 मिलियन रिकॉर्ड के लिए, सदिश डालने और छांटने का समय मानचित्र (1.1 s) की तुलना में लगभग 10 गुना कम (0.11 s) है।

कंटेनरों में वस्तुओं की खोज करते समय प्राप्त डेटा



दूसरा ग्राफ कंटेनर में तत्वों की संख्या पर प्रति यूनिट समय (10 सेकंड) की संख्या की निर्भरता को दर्शाता है। आप देख सकते हैं कि वेक्टर में खोज की गति अधिक है, जैसा कि ऊपर की उम्मीद है, और 1 मिलियन रिकॉर्ड द्वारा वेक्टर में खोजों की संख्या मानचित्र की तुलना में लगभग 3.9 गुना अधिक है।

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