std :: सूची बनाम std :: वेक्टर पुनरावृत्ति

Question

ऐसा कहा जाता है कि एक वेक्टर (जैसा कि इसके सभी तत्वों को पढ़ना है) के माध्यम से अनुकूलित करना कैश की वजह से एक सूची के माध्यम से तेज़ होने से तेज़ है।

क्या वेब पर कोई रिसोर्स है जो यह दर्शाता है कि यह प्रदर्शन को कितना प्रभावित करता है?

साथ ही, क्या एक कस्टम लिंक्ड सूची का उपयोग करना बेहतर होगा, जिनके तत्वों को प्रीलाइक्टेड किया जाएगा ताकि वे स्मृति में लगातार हों?

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

क्या तथ्य यह है कि तत्व लगातार लगातार कैश में प्रभाव डालते हैं, या क्योंकि मैं ++list_element के बजाय list_element->next पर कॉल करूंगा, इससे कुछ भी सुधार नहीं होता है?

Answer 1

डेटा संरचनाओं के कॉम्पैक्ट प्रतिनिधित्व के कारण कैश कोहेरेंसी से दक्षता लाभ नाटकीय हो सकता है।सूचियों की तुलना में वैक्टरों के मामले में, कॉम्पैक्ट प्रतिनिधित्व केवल पढ़ने के लिए बेहतर नहीं हो सकता है, लेकिन कुछ विशेष आर्किटेक्चर के लिए 500 के तत्वों के क्रम तक तत्वों के सम्मिलन (वेक्टर में स्थानांतरित करने) के लिए भी बेहतर हो सकता है जैसा कि इस आलेख के चित्रा 3 में बजेर्न द्वारा प्रदर्शित किया गया है Stroustrup:

http://www2.research.att.com/~bs/Computer-Jan12.pdf

(प्रकाशक साइट: http://www.computer.org/portal/web/csdl/doi/10.1109/MC.2011.353)

मुझे लगता है कि अगर यह अपने कार्यक्रम के लिए एक महत्वपूर्ण कारक है, आप इसे अपने वास्तुकला पर प्रोफ़ाइल चाहिए।

Answer 2

सुनिश्चित नहीं हैं कि अगर मैं समझा सकता है यह सही है लेकिन यहाँ मेरी (i, :) नीचे अनुवादित मशीन अनुदेश की तर्ज पर सोच रहा हूँ

वेक्टर इटरेटर (सन्निहित स्मृति) दृश्य है: जब आप एक वेक्टर इटरेटर को बढ़ा , इटेटरेटर मान को ऑब्जेक्ट का आकार जोड़ा जाता है (संकलन समय पर जाना जाता है) अगली ऑब्जेक्ट को इंगित करने के लिए। अधिकांश CPUs में यह सबसे अधिक से एक से तीन निर्देशों में से कुछ है।

सूची इटरेटर (लिंक्ड सूची http://www.sgi.com/tech/stl/List.html): जब आप कोई सूची इटरेटर को बढ़ा (उठाई वस्तु), आगे लिंक के स्थान वस्तु के आधार पर कुछ नंबर जोड़कर स्थित है ओर इशारा किया और उसके बाद के रूप में भरी हुई इटरेटर का नया मूल्य। इसके लिए एक से अधिक स्मृति पहुंच है और वेक्टर पुनरावृत्ति ऑपरेशन की तुलना में धीमी है।

Answer 3

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

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

सूची के साथ, चूंकि तत्व हर जगह स्पैस हैं, "अगले पर जा रहे हैं" का अर्थ उस पते का संदर्भ लें जो पिछले के समान स्मृति पृष्ठ में नहीं हो सकता है, और इसलिए, कैश को प्रत्येक पर अपडेट किया जाना चाहिए पुनरावृत्ति चरण, प्रत्येक पुनरावृत्ति पर धीमी रैम तक पहुंच।

प्रदर्शन अंतर बहुत प्रोसेसर पर और दोनों मुख्य रैम और कैश के लिए इस्तेमाल किया स्मृति के प्रकार पर निर्भर करता है, और जिस तरह std::allocator (और अंततः operator new और malloc) लागू किया जाता है पर, तो एक सामान्य संख्या असंभव है दिया जाना। (नोट: महान अंतर का मतलब कैश के लिए खराब रैम का सम्मान है, लेकिन इसका मतलब है सूची में खराब कार्यान्वयन)