c++ - उनल - विश्व का मानचित्र




क्या छोटी सी कुंजी के मामले में unordered_map पर मानचित्र का उपयोग करने का कोई फायदा है? (7)

सी ++ में unordered_map बारे में एक हालिया बात ने मुझे एहसास दिलाया, कि मुझे लुकअप की कार्यक्षमता ( एमओआरटीएड ओ (1) बनाम ओ (लॉग एन) की वजह से पहले map इस्तेमाल किया गया था, जहां मैंने पहले map इस्तेमाल किया था। ज्यादातर बार मैं एक मानचित्र का उपयोग करता हूं, मैं या तो int या std::strings को चाबियों के रूप में उपयोग करता हूं, इसलिए मुझे हैश फ़ंक्शन की परिभाषा में कोई समस्या नहीं है। जितना मैंने सोचा, उतना ही मुझे एहसास हुआ कि मुझे एक unordered_map पर सरल प्रकार के मामले में std::map का उपयोग करने का कोई कारण नहीं मिला - मैंने इंटरफेस पर एक नज़र unordered_map , और नहीं मेरे कोड को प्रभावित करने वाले किसी भी महत्वपूर्ण अंतर को ढूंढें।

इसलिए सवाल - क्या int और std::string जैसे साधारण प्रकारों के मामले में unordered map पर std::map का उपयोग करने का कोई वास्तविक कारण है?

मैं कड़ाई से प्रोग्रामिंग दृष्टिकोण से पूछ रहा हूं - मुझे पता है कि यह पूरी तरह से मानक नहीं माना जाता है, और यह पोर्टिंग के साथ समस्याएं पैदा कर सकता है।

इसके अलावा मुझे उम्मीद है कि एक छोटे से ओवरहेड (क्या यह सच है?) के कारण सही उत्तरों में से एक "डेटा के छोटे सेट के लिए अधिक कुशल" हो सकता है - इसलिए मैं प्रश्नों को उन मामलों में प्रतिबंधित करना चाहता हूं जहां कुंजी की मात्रा गैर-तुच्छ (> 1 024) है।

संपादित करें: दोह, मैं स्पष्ट भूल गया (धन्यवाद जीएमएन!) - हाँ, नक्शा का आदेश दिया जाता है - मुझे पता है, और मैं अन्य कारणों की तलाश में हूं।


महत्वपूर्ण अंतर जो वास्तव में यहां पर्याप्त रूप से उल्लेख नहीं किए गए हैं:

  • map इटेटर को सभी तत्वों को स्थिर रखता है, सी ++ 17 में आप तत्वों को अमान्य करने वाले अमान्य लोगों को अमान्य किए बिना तत्वों को दूसरे स्थान पर ले जा सकते हैं (और अगर किसी संभावित आवंटन के बिना उचित रूप से कार्यान्वित किया जाता है)।
  • सिंगल ऑपरेशंस के लिए map समय आम तौर पर अधिक सुसंगत होते हैं, क्योंकि उन्हें कभी भी बड़े आवंटन की आवश्यकता नहीं होती है।
  • libstdc ++ में लागू किए गए std::hash का उपयोग करके unordered_map अविश्वसनीय इनपुट के साथ खिलाया गया है तो यह DoS के लिए कमजोर है (यह लगातार बीज के साथ MurmurHash2 का उपयोग करता है - नहीं कि बीजिंग वास्तव में मदद करेगा, https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/ )।
  • आदेश दिया जा रहा है कुशल रेंज खोजों को सक्षम बनाता है, उदाहरण के साथ सभी तत्वों पर पुन: सक्रिय करें> = 42।

अन्य उत्तरों में कारण दिए गए हैं; यहाँ एक और है।

std :: नक्शा (संतुलित बाइनरी पेड़) संचालन एम (लॉग एन) और सबसे खराब मामला ओ (लॉग एन) amortized हैं। std :: unordered_map (हैश टेबल) संचालन एम (1) और सबसे खराब मामला ओ (एन) amortized हैं।

यह अभ्यास में कैसे खेलता है यह है कि हैश टेबल "ओक (एन) ऑपरेशन के साथ हर बार" हिचकी "करता है, जो आपका एप्लिकेशन बर्दाश्त कर सकता है या नहीं हो सकता है। यदि यह इसे बर्दाश्त नहीं कर सकता है, तो आप std :: unordered_map पर std :: map पसंद करेंगे।


मैं बस यह इंगित करता हूं कि ... कई तरह के unordered_map एस हैं।

हैश मानचित्र पर विकिपीडिया आलेख देखें । किस कार्यान्वयन का उपयोग किया गया था, इस पर निर्भर करते हुए, लुक-अप, सम्मिलन और हटाने की अवधि में विशेषताओं में काफी भिन्नता हो सकती है।

और यह मुझे सबसे ज्यादा चिंता करता है जो एसटीएल के लिए unordered_map के अतिरिक्त है: उन्हें एक विशेष कार्यान्वयन चुनना होगा क्योंकि मुझे संदेह है कि वे Policy रोड पर जाएंगे, और इसलिए हम औसत उपयोग के लिए कार्यान्वयन के साथ फंस जाएंगे और अन्य मामलों के लिए कुछ नहीं ...

उदाहरण के लिए कुछ हैश मानचित्रों में रैखिक रीहैशिंग होती है, जहां एक ही समय में पूरे हैश मानचित्र को फिर से चलाने की बजाय, प्रत्येक प्रविष्टि पर एक भाग दोहराया जाता है, जो लागत को कम करने में मदद करता है।

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

तो फिलहाल मैं std::map या शायद loki::AssocVector (जमे हुए डेटा सेट के लिए) पसंद करते हैं।

मुझे गलत मत समझो, मैं std::unordered_map का उपयोग करना चाहता हूं और भविष्य में मैं कर सकता हूं, लेकिन जब आप इसे लागू करने के सभी तरीकों के बारे में सोचते हैं तो इस तरह के कंटेनर की पोर्टेबिलिटी को "भरोसा" करना मुश्किल होता है और इसके परिणामस्वरूप विभिन्न प्रदर्शन।


मैं मोटे तौर पर उसी बिंदु को गूंजता हूं: उपयोग के प्रकार के आधार पर, std::map std::tr1::unordered_map (VS 2008 SP1 में शामिल कार्यान्वयन का उपयोग करके) से तेज़ (और अक्सर होता है) हो सकता है।

ध्यान में रखने के लिए कुछ जटिल कारक हैं। उदाहरण के लिए, std::map , आप कुंजी की तुलना कर रहे हैं, जिसका अर्थ है कि आप पेड़ की दाएं और बाएं उप-शाखाओं के बीच अंतर करने के लिए केवल एक कुंजी की शुरुआत की पर्याप्त मात्रा को देखते हैं। मेरे अनुभव में, लगभग एकमात्र बार जब आप पूरी कुंजी देखते हैं तो यह है कि यदि आप int की तरह कुछ उपयोग कर रहे हैं तो आप एक ही निर्देश में तुलना कर सकते हैं। Std :: स्ट्रिंग जैसे अधिक सामान्य कुंजी प्रकार के साथ, आप अक्सर केवल कुछ वर्णों की तुलना करते हैं।

इसके विपरीत, एक सभ्य हैश फ़ंक्शन हमेशा पूरी कुंजी को देखता है। IOW, भले ही टेबल लुकअप निरंतर जटिलता है, हैश के पास लगभग रैखिक जटिलता है (हालांकि कुंजी की लंबाई पर, वस्तुओं की संख्या नहीं)। कुंजी के रूप में लंबे तारों के साथ, एक std::map एक unordered_map से पहले एक खोज समाप्त कर सकता है इससे पहले कि वह अपनी खोज शुरू कर दे।

दूसरा, जबकि हैश टेबल का आकार बदलने के कई तरीके हैं, उनमें से अधिकतर धीमे हैं - इस बिंदु पर कि जब तक लुकअप सम्मिलन और हटाने से काफी अधिक न हो, तो std::unordered_map से अधिक तेज़ होगा।

बेशक, जैसा कि मैंने आपके पिछले प्रश्न पर टिप्पणी में उल्लेख किया है, आप पेड़ों की एक तालिका का भी उपयोग कर सकते हैं। इसमें फायदे और नुकसान दोनों हैं। एक ओर, यह एक पेड़ के सबसे बुरे मामले को सीमित करता है। यह तेजी से सम्मिलन और हटाने की भी अनुमति देता है, क्योंकि (कम से कम जब मैंने इसे किया है) मैंने टेबल के एक निश्चित आकार का उपयोग किया है। सभी टेबल आकार बदलने से आप अपनी हैश टेबल को बहुत सरल और आमतौर पर तेज़ी से रखने की अनुमति देते हैं।

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


यदि आप अपने std :: map और std :: unordered_map कार्यान्वयन की गति की तुलना करना चाहते हैं, तो आप Google के sparsehash प्रोजेक्ट का उपयोग कर सकते हैं जिसमें समय_शैश_मैप प्रोग्राम है। उदाहरण के लिए, x86_64 लिनक्स सिस्टम पर जीसीसी 4.4.2 के साथ

$ ./time_hash_map
TR1 UNORDERED_MAP (4 byte objects, 10000000 iterations):
map_grow              126.1 ns  (27427396 hashes, 40000000 copies)  290.9 MB
map_predict/grow       67.4 ns  (10000000 hashes, 40000000 copies)  232.8 MB
map_replace            22.3 ns  (37427396 hashes, 40000000 copies)
map_fetch              16.3 ns  (37427396 hashes, 40000000 copies)
map_fetch_empty         9.8 ns  (10000000 hashes,        0 copies)
map_remove             49.1 ns  (37427396 hashes, 40000000 copies)
map_toggle             86.1 ns  (20000000 hashes, 40000000 copies)

STANDARD MAP (4 byte objects, 10000000 iterations):
map_grow              225.3 ns  (       0 hashes, 20000000 copies)  462.4 MB
map_predict/grow      225.1 ns  (       0 hashes, 20000000 copies)  462.6 MB
map_replace           151.2 ns  (       0 hashes, 20000000 copies)
map_fetch             156.0 ns  (       0 hashes, 20000000 copies)
map_fetch_empty         1.4 ns  (       0 hashes,        0 copies)
map_remove            141.0 ns  (       0 hashes, 20000000 copies)
map_toggle             67.3 ns  (       0 hashes, 20000000 copies)

से: http://www.cplusplus.com/reference/map/map/

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

नक्शा कंटेनर आम तौर पर अनियंत्रित_मैप कंटेनर से अलग होते हैं ताकि व्यक्तिगत तत्वों को उनकी कुंजी से एक्सेस किया जा सके, लेकिन वे अपने आदेश के आधार पर सबसेट पर प्रत्यक्ष पुनरावृत्ति की अनुमति देते हैं। "


map उनके तत्वों का आदेश रखने के लिए मत भूलना। यदि आप इसे छोड़ नहीं सकते हैं, तो जाहिर है कि आप एक unordered_map उपयोग नहीं कर सकते हैं।

ध्यान में रखने के लिए कुछ और यह है कि unordered_map आमतौर पर अधिक स्मृति का उपयोग करता है। एक map बस कुछ घर-रखरखाव पॉइंटर्स होते हैं तो प्रत्येक ऑब्जेक्ट के लिए स्मृति। असल में, unordered_map की एक बड़ी सरणी है (ये कुछ कार्यान्वयन में काफी बड़ी हो सकती है) और फिर प्रत्येक ऑब्जेक्ट के लिए अतिरिक्त मेमोरी। यदि आपको स्मृति-जागरूक होने की आवश्यकता है, तो map बेहतर साबित होना चाहिए, क्योंकि इसमें बड़ी सरणी नहीं है।

इसलिए, यदि आपको शुद्ध लुकअप-पुनर्प्राप्ति की आवश्यकता है, तो मैं कहूंगा कि एक unordered_map जाने का तरीका है। लेकिन हमेशा व्यापार-बंद होते हैं, और यदि आप उन्हें बर्दाश्त नहीं कर सकते हैं, तो आप इसका उपयोग नहीं कर सकते हैं।

व्यक्तिगत अनुभव से, मुझे मुख्य इकाई लुक-अप तालिका में map बजाय एक unordered_map का उपयोग करते समय प्रदर्शन (मापित, निश्चित रूप से) में एक बड़ा सुधार मिला।

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





unordered-map