फास्ट हैश फंक्शन :: vector`

Question

मैं vector<T> से एक हैश मान प्राप्त करने के लिए इस समाधान लागू:

namespace std 
{ 
    template<typename T> 
    struct hash<vector<T>> 
    { 
     typedef vector<T> argument_type; 
     typedef std::size_t result_type; 
     result_type operator()(argument_type const& in) const 
     { 
      size_t size = in.size(); 
      size_t seed = 0; 
      for (size_t i = 0; i < size; i++) 
       //Combine the hash of the current vector with the hashes of the previous ones 
       hash_combine(seed, in[i]); 
      return seed; 
     } 
    }; 
} 

//using boost::hash_combine 
template <class T> 
inline void hash_combine(std::size_t& seed, T const& v) 
{ 
    seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 
} 

लेकिन इस समाधान बिल्कुल पैमाने पर नहीं करता है: एक 10 के vector<double> लाखों तत्वों यह है के साथ 2.5 से अधिक (वीएस के अनुसार) ले जाएगा।

करता है इस परिदृश्य के लिए एक तेजी से हैश फंक्शन मौजूद है?

सूचना है कि वेक्टर संदर्भ से एक हैश मान बनाने एक व्यवहार्य समाधान नहीं है, के बाद से संबंधित unordred_map अलग रन में और इसके अलावा में एक ही सामग्री है, लेकिन अलग-अलग पतों के साथ दो vector<double> अलग ढंग से मैप किया जाएगा (के लिए अवांछित व्यवहार का उपयोग किया जाएगा यह अनुप्रयोग)।

Answer 1

नोट:Asperthecomments, आप अनुकूलन के साथ संकलन के द्वारा एक 25-50x गति-अप मिलता है। ऐसा करो, पहले। फिर, यदि यह अभी भी बहुत धीमा है, तो नीचे देखें।

---

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

एक विकल्प हैश फंक्शन parallelize हो सकता है। यदि आपके पास 8 कोर हैं, तो आप वेक्टर के प्रत्येक हैश 1/8 वें में 8 थ्रेड चला सकते हैं, फिर अंत में 8 परिणामी मानों को जोड़ सकते हैं। सिंक्रनाइज़ेशन ओवरहेड बहुत बड़े वैक्टरों के लिए इसके लायक हो सकता है।

Answer 2

दृष्टिकोण है कि MSVC के पुराने इस्तेमाल किया hashmap कम अक्सर नमूने के लिए किया गया था।

इसका मतलब है कि पृथक परिवर्तन आपके हैश में दिखाई नहीं देंगे, लेकिन बात आप से बचने के लिए कोशिश कर रहे हैं पढ़ने और डेटा के पूरे 80 एमबी प्रसंस्करण क्रम में अपने वेक्टर हैश करने के लिए है। कुछ पात्रों को पढ़ना बहुत अपरिहार्य है।

दूसरी बात आपको क्या करना चाहिए है सभी vector रों पर std::hash विशेषज्ञ नहीं, तो इस अपने कार्यक्रम बीमार का गठन कर सकते हैं (जैसा कि एक दोष संकल्प, जिसकी स्थिति मुझे याद नहीं है ने सुझाव दिया), और कम से कम एक है खराब योजना (std के रूप में खुद को हैश संयोजन और वैक्टर के हैशिंग जोड़ने की अनुमति है)।

जब मैं एक कस्टम हैश बारे में, मैं आमतौर पर ADL (कोएनिग लुक) का उपयोग आसान विस्तार करने के लिए बनाने के लिए।

namespace my_utils { 
    namespace hash_impl { 
    namespace details { 
     namespace adl { 
     template<class T> 
     std::size_t hash(T const& t) { 
      return std::hash<T>{}(t); 
     } 
     } 
     template<class T> 
     std::size_t hasher(T const& t) { 
     using adl::hash; 
     return hash(t); 
     } 
    } 
    struct hash_tag {}; 
    template<class T> 
    std::size_t hash(hash_tag, T const& t) { 
     return details::hasher(t); 
    } 
    template<class T> 
    std::size_t hash_combine(hash_tag, std::size_t seed, T const& t) { 
     seed ^= hash(t) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 
    } 
    template<class Container> 
    std::size_t fash_hash_random_container(hash_tag, Container const& c) { 
     std::size_t size = c.size(); 
     std::size_t stride = 1 + size/10; 
     std::size_t r = hash(hash_tag{}, size); 
     for(std::size_t i = 0; i < size; i += stride) { 
     r = hash_combine(hash_tag{}, r, c.data()[i]) 
     } 
     return r; 
    } 
    // std specializations go here: 
    template<class T, class A> 
    std::size_t hash(hash_tag, std::vector<T,A> const& v) { 
     return fash_hash_random_container(hash_tag{}, v); 
    } 
    template<class T, std::size_t N> 
    std::size_t hash(hash_tag, std::array<T,N> const& a) { 
     return fash_hash_random_container(hash_tag{}, a); 
    } 
    // etc 
    } 
    struct my_hasher { 
    template<class T> 
    std::size_t operator()(T const& t)const { 
     return hash_impl::hash(hash_impl::hash_tag{}, t); 
    } 
    }; 
} 

अब my_hasher एक सार्वभौमिक हैशर है। यह my_utils::hash_impl (std प्रकारों के लिए) में घोषित हैंश या तो hash नामक नि: शुल्क फ़ंक्शंस का उपयोग करता है जो हैश चीजों के लिए एक दिया गया प्रकार हैश। यह विफल होने पर, यह std::hash<T> का उपयोग करने का प्रयास करता है। यदि यह विफल रहता है, तो आपको संकलन-समय त्रुटि मिलती है।

प्रकार आप हैश करने के लिए चाहते हैं, उसके नाम स्थान में एक नि: शुल्क hash समारोह लेखन बंद और खुले std और मेरे अनुभव में std::hash विशेषज्ञ की तुलना में कम कष्टप्रद हो जाता है।

यह वैक्टर और सरणियों समझता है, रिकर्सिवली। Tuples और जोड़ों को करने के लिए थोड़ा और काम की आवश्यकता है।

यह नमूने के बारे में 10 गुना पर वैक्टर और सरणियों कहा।

(नोट:। क्योंकि कि आवश्यकता बेकार hash_tag, दोनों एक मजाक का एक सा है, और ADL मजबूर और आगे-घोषित करने के लिए hash_impl नाम स्थान में hash विशेषज्ञताओं होने को रोकने के लिए एक रास्ता है)

की कीमत नमूना यह है कि आप अधिक टकराव प्राप्त कर सकते हैं।

---

एक और दृष्टिकोण यदि आप डेटा की एक बड़ी राशि उन्हें एक बार हैश, और जब वे संशोधित कर रहे हैं का ट्रैक रखने के है। इस दृष्टिकोण को करने के लिए, अपने प्रकार के लिए एक कॉपी-ऑन-राइट मोनैड इंटरफ़ेस का उपयोग करें जो हैश का अद्यतित है या नहीं। अब एक वेक्टर एक बार धोया जाता है; यदि आप इसे संशोधित करते हैं, तो हैश को त्याग दिया जाता है।

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

तुम भी हैशिंग बहु थ्रेड सकता है, लेकिन मुझे लगता है कि होता है कि अपने कोड शायद स्मृति बैंडविड्थ बाध्य, और बहु ​​सूत्रण बहुत वहाँ मदद नहीं करेगा है। प्रयास योग्य।

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

अंत में

, क्योंकि आप एक समय में 10 लाख तत्वों के साथ काम कर रहे हैं, एक मजबूत बड़े पैमाने पर भंडारण समाधान पर जाने से, डेटाबेस पर विचार या आप क्या कर सकते है। मानचित्र में 80 मेगाबाइट कुंजी का उपयोग करना मेरे लिए अजीब लगता है।