101
में मेरे पास hash_map और map सी ++ में एक प्रश्न है। मैं समझता हूं कि map एसटीएल में है, लेकिन hash_map मानक नहीं है। दोनों के बीच क्या अंतर है?मानचित्र बनाम हैश_मैप सी ++
A
उत्तर
119
वे बहुत अलग तरीकों से लागू किए गए हैं।
hash_map (unordered_map TR1 और बूस्ट में; उन लोगों का उपयोग करें) एक हैश तालिका का उपयोग करें जहां कुंजी तालिका में एक स्लॉट पर है और मूल्य उस कुंजी से जुड़ी सूची में संग्रहीत किया जाता है।
map एक संतुलित बाइनरी खोज पेड़ (आमतौर पर एक लाल/काला पेड़) के रूप में लागू किया जाता है।
एक unordered_map संग्रह के ज्ञात तत्वों तक पहुंचने के लिए थोड़ा बेहतर प्रदर्शन देना चाहिए, लेकिन map में अतिरिक्त उपयोगी विशेषताएं होंगी (उदाहरण के लिए यह क्रमबद्ध क्रम में संग्रहीत है, जो ट्रैवर्सल को शुरू होने से शुरू करने की अनुमति देता है)। unordered_mapmap से डालने और हटाने पर तेज़ होगा।
4
सी ++ स्पेक बिल्कुल नहीं कहता कि आपको एसटीएल कंटेनर के लिए वास्तव में क्या एल्गोरिदम का उपयोग करना चाहिए। हालांकि, यह उनके प्रदर्शन पर कुछ बाधा डालता है, जो map और अन्य सहयोगी कंटेनर के लिए हैश टेबल के उपयोग को नियंत्रित करता है। (वे सबसे अधिक लाल/काले पेड़ के साथ लागू होते हैं।) इन बाधाओं के लिए इन कंटेनरों के लिए बेहतर खराब-केस प्रदर्शन की आवश्यकता होती है, हैश टेबल वितरित कर सकते हैं।
कई लोग वास्तव में हैश टेबल चाहते हैं, हालांकि, हैश-आधारित एसटीएल सहयोगी कंटेनर वर्षों से एक आम विस्तार रहे हैं। नतीजतन, उन्होंने unordered_map और सी ++ मानक के बाद के संस्करणों को जोड़ा।
+0
यह वास्तव में TR1 (std :: tr1 :: unordered_map) में जोड़ा गया था, सी ++ 0x –
+0
इसे ठीक करने के लिए संपादित नहीं किया गया था। –
+0
मैंने सोचा कि कारण 'नक्शा' आमतौर पर एक संतुलित btree था 'ऑपरेटर <() 'स्थान निर्धारित करने के साधन के रूप में उपयोग करने के कारण। – KitsuneYMG
33
hash_map कई लाइब्रेरी कार्यान्वयन द्वारा प्रदान किया गया एक आम एक्सटेंशन था। यही कारण है कि इसका नाम बदलकर unordered_map कर दिया गया था जब इसे टीआर 1 के हिस्से के रूप में सी ++ मानक में जोड़ा गया था। नक्शा आम तौर पर एक संतुलित बाइनरी पेड़ के साथ लागू किया जाता है जैसे लाल-काले पेड़ (कार्यान्वयन निश्चित रूप से भिन्न होते हैं)। hash_map और unordered_map आमतौर पर हैश टेबल के साथ लागू किए जाते हैं। इस प्रकार आदेश बनाए रखा नहीं है। unordered_map डालें/हटाएं/क्वेरी ओ (1) (निरंतर समय) होगी जहां नक्शा ओ (लॉग एन) होगा जहां एन डेटा संरचना में वस्तुओं की संख्या होगी। तो unordered_map तेज है, और यदि आपको आइटम के आदेश की परवाह नहीं है तो map पर प्राथमिकता दी जानी चाहिए। कभी-कभी आप ऑर्डर बनाए रखना चाहते हैं (कुंजी द्वारा ऑर्डर किया गया है) और उस map के लिए विकल्प होगा।
+9
मैं इंगित करता हूं कि हैशपैप में ओ (एन) का सबसे खराब मामला उपयोग होता है जब टकराव की संभावना होती है (खराब हैश एफसीएन, लोडिंग कारक बहुत अधिक, आदि) – KitsuneYMG
+0
एक अच्छा हैशप की ओ (1) की अपेक्षित लागत है, यह नहीं है ऐसा होने की गारंटी है। खराब हैशैप्स की अपेक्षित लागत हो सकती है जो ओ (1) नहीं है। – Clearer
12
कुछ महत्वपूर्ण अंतर जटिलता आवश्यकताओं में हैं।
मानचित्र के लिए आवेषण और खोज के लिए ओ (लॉग (एन)) समय की आवश्यकता होती है।
एक unordered_map के लिए ओ (1) के 'औसत' समय की आवश्यकता होती है और पाता है लेकिन उसे ओ (एन) का सबसे खराब केस समय होने की अनुमति है।
तो, आमतौर पर, unordered_map तेज़ होगा, लेकिन आपके द्वारा स्टोर की जाने वाली चाबियों और हैश फ़ंक्शन के आधार पर, बहुत खराब हो सकता है।
0
मुझे नहीं पता कि क्या देता है, लेकिन, हैश_मैप को साफ़ करने के लिए 20 सेकंड से अधिक समय लगता है() 150K हस्ताक्षरित पूर्णांक कुंजी और फ्लोट मान। मैं बस किसी और के कोड को चला रहा हूं और पढ़ रहा हूं।
इस प्रकार हैश_मैप शामिल है।
#include "StdAfx.h"
#include <hash_map>
मैं इस यहाँ https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap
पढ़ कह रही है कि स्पष्ट() हे (एन) के आदेश है। यह मेरे लिए, बहुत अजीब है, लेकिन, वही तरीका है।
मैं प्रदर्शन के संबंध में आपसे पूरी तरह से सहमत नहीं हूं। प्रदर्शन कई मानकों से प्रभावित है और मैं केवल 10 प्रविष्टियों के लिए एक unordered_map का उपयोग कर किसी भी प्रोग्रामर को डांट दूंगा क्योंकि "यह तेज़ है"। पहले इंटरफ़ेस/कार्यक्षमता के बारे में चिंता करें, प्रदर्शन बाद में। –
अच्छा, हाँ, अगर आप अपनी समस्या को समझते हैं तो यह मदद करता है। परिमाण के कुछ आदेशों तक यह शायद धोने का प्रदर्शन होता है, लेकिन दोनों कंटेनरों की प्रदर्शन विशेषताओं को समझना महत्वपूर्ण है क्योंकि वे अलग-अलग तरीकों से विचलित होते हैं क्योंकि डेटा वॉल्यूम बड़ा हो जाता है। – Joe
दिलचस्प बात यह है कि मैंने एक एसडीडी :: मैप को एक बूस्ट :: unordered_map के साथ एक एप्लिकेशन में बदल दिया जिसमें मैं बहुत सारे यादृच्छिक लुकअप करता हूं, लेकिन मानचित्र में सभी चाबियों पर भी पुनरावृत्ति करता हूं। मैंने लुकअप में बड़ी मात्रा में बचाया, लेकिन इसे पुनरावृत्तियों के माध्यम से वापस प्राप्त किया, इसलिए मैंने मानचित्र पर वापस स्विच किया और एप्लिकेशन प्रदर्शन में सुधार के अन्य तरीकों की तलाश में हूं। –