नक्शा unordered_map से बहुत तेज़ क्यों होगा?

Question

मैंने एक खोज कैशिंग परिणामों को लागू किया जिसमें प्रकार की कुंजी (7 शॉर्ट्स वाली कक्षा) और सोर्स (3 युगल का वर्ग) के मूल्य शामिल हैं। Unordered_map का उपयोग मानचित्र से कम से कम 20 गुना धीमा था। क्यूं कर?

संपादित करें: इसे हटाएं! मेरे हैश फंक्शन

namespace std { 
    size_t hash<State>::operator()(State const& s) const { 
     size_t retval = hash<short>()(s.s[0]); 
     for (int i = 1; i < R; i += 2) { // 1 3 5 
      int x = (static_cast<int>(s.s[i + 1]) << 16) 
       + (static_cast<int>(s.s[i])); 
      hash_combine(retval, x); 
     } 
    } 
} 

मैं return retval करना भूल गया था, तो यह सब टकराने था! मेरी इच्छा है कि unordered_map में hash_function_quality() फ़ंक्शन था जो टकराव की औसत संख्या की रिपोर्ट करता है।

Answer 1

unordered_map की गति आपके हैशिंग फ़ंक्शन की गति के लिए सीधे आनुपातिक है। यह कभी सीधा आगे संबंध नहीं है। बिंदु में प्रकरण, यदि आप सरल हैशिंग समारोह का उपयोग करें:

std::size_t myHash(MyObjectType _object){ return 1; } 

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

आपको क्या करना है दो चीजों पर:

1. आप किस हैशिंग फ़ंक्शन का उपयोग कर रहे हैं? क्या यह प्रक्रिया करने के लिए एक हास्यास्पद समय खर्च करता है?
2. यह कितने टकराव पैदा कर रहा है? यही है, एक ही हैश मूल्य में कितने अद्वितीय तत्व मैप किए जा रहे हैं?

इनमें से कोई भी प्रदर्शन कर सकता है और प्रदर्शन को मार देगा।

Answer 2

std::unordered_map हैश फ़ंक्शन की वजह से तत्वों की एक छोटी संख्या के लिए आमतौर पर धीमा होता है। यह एक निश्चित (-श) समय लेता है, लेकिन फिर भी समय की एक महत्वपूर्ण राशि हो सकती है।

std::map दूसरी तरफ std::unordered_map से सरल है। जिस समय यह तत्व का उपयोग करता है, वहां तत्वों की गिनती पर निर्भर करता है, लेकिन कम और कम इसलिए तत्वों की संख्या बढ़ जाती है। और बड़े-ओएच कारक c एक std :: मानचित्र के लिए आमतौर पर std::unordered_map की तुलना में बहुत छोटा है।

सामान्य रूप से, std::unordered_map से अधिक का उपयोग करना पसंद करें, जब तक आपके पास std::unordered_map का उपयोग करने का कोई विशिष्ट कारण न हो। यह विशेष रूप से रखता है यदि आपके पास बड़ी संख्या में तत्व नहीं हैं।

Answer 3

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

Answer 4

लिए

काश unordered_map एक hash_function_quality() फ़ंक्शन कि रिपोर्ट टकराव की औसत संख्या थी।

मुझे लगता है कि निम्न कार्य उपयोगी हो सकता है।

unordered_map::load_factor 
    float load_factor() const; 
The member function returns the average number of elements per bucket. 

लोअर load_factor, बेहतर हैश फंक्शन है।