सुपर उच्च प्रदर्शन सी/सी ++ हैश नक्शा (तालिका, शब्दकोश)

Question

मुझे उच्च प्रदर्शन हैश मानचित्र डेटा संरचना में संरचना मानों के लिए आदिम कुंजी (int, शायद लंबा) मानचित्रण करने की आवश्यकता है।

मेरे कार्यक्रम में इन मानचित्रों में से कुछ सौ होंगे, और प्रत्येक मानचित्र में आमतौर पर कुछ हज़ार प्रविष्टियां होंगी। हालांकि, नक्शे लगातार "ताज़ा" या "मंथन" होगा; add और delete संदेशों को एक सेकंड में संसाधित करने की कल्पना करें।

सी या सी ++ में कौन सी पुस्तकालयों में डेटा संरचना है जो इस उपयोग के मामले को फिट करती है? या, आप अपना खुद का निर्माण करने की सिफारिश कैसे करेंगे? धन्यवाद!

Answer 1

मैं आपको Google SparseHash (या C11 संस्करण Google SparseHash-c11) का प्रयास करने की सलाह दूंगा और देखें कि यह आपकी आवश्यकताओं के अनुरूप है या नहीं। उनके पास एक मेमोरी कुशल कार्यान्वयन है और साथ ही गति के लिए अनुकूलित भी है। मैंने बहुत समय पहले एक बेंचमार्क किया था, यह गति के मामले में उपलब्ध सर्वोत्तम हैशटेबल कार्यान्वयन था (हालांकि कमियों के साथ)।

Answer 2

सी या सी ++ में कौन सी लाइब्रेरी में डेटा संरचना है जो इस उपयोग के मामले को फिट करती है? या, आप अपना खुद का निर्माण करने की सिफारिश कैसे करेंगे? धन्यवाद!

LGPL'd Judy arrays देखें। कभी भी खुद का इस्तेमाल नहीं किया, लेकिन कुछ मौकों पर मुझे विज्ञापन दिया गया था।

आप एसटीएल कंटेनर (std :: hash_map, आदि) को बेंचमार्क करने का भी प्रयास कर सकते हैं। मंच/कार्यान्वयन और स्रोत कोड ट्यूनिंग के आधार पर (जितना आप गतिशील स्मृति प्रबंधन महंगे हो सकते हैं) वे पर्याप्त प्रदर्शन कर सकते हैं।

इसके अलावा, अगर अंतिम समाधान के प्रदर्शन समाधान की लागत श्रेष्ठ माना जाता है, तो आप पर्याप्त रैम के साथ प्रणाली ऑर्डर करने के लिए सादे विन्यास में, सब कुछ डाल करने के लिए कोशिश कर सकते हैं। इंडेक्स द्वारा एक्सेस का प्रदर्शन नामुमकिन है।

ऐड/डिलीट ऑपरेशन अधिक ऑपरेशन से अधिक (100x) अधिक होते हैं।

यह संकेत देता है कि आप पहले एल्गोरिदम सुधारने पर ध्यान केंद्रित करना चाहते हैं। यदि डेटा केवल लिखा गया है, पढ़ा नहीं है, तो उन्हें बिल्कुल क्यों लिखें?

Answer 3

डिफ़ॉल्ट रूप से boost::unordered_map (या tr1 आदि) का उपयोग करें। फिर अपना कोड प्रोफाइल करें और देखें कि क्या कोड बाधा है। केवल तभी मैं एक तेज़ विकल्प खोजने के लिए आपकी आवश्यकताओं का सटीक विश्लेषण करने का सुझाव दूंगा।

Answer 4

सबसे पहले जांचें कि libmemcache जैसे मौजूदा समाधान आपकी आवश्यकता के अनुरूप हैं।

यदि नहीं ...

हैश नक्शे आपकी आवश्यकता के लिए निश्चित जवाब हो रहा है। यह कुंजी पर आधारित ओ (1) लुकअप प्रदान करता है। ज्यादातर एसटीएल पुस्तकालय इन दिनों कुछ प्रकार के हैश प्रदान करते हैं। तो अपने मंच द्वारा प्रदान किए गए एक का उपयोग करें।

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

यदि ऐसा नहीं है, तो आप शुद्ध

1. अच्छे पुराने अभाज्य संख्या पर पाया कुछ अच्छी तेजी हैशिंग एल्गोरिदम का पता लगाने चाहिए गुणा algo
2. http://www.azillionmonkeys.com/qed/hash.html
3. http://burtleburtle.net/bob/
4. http://code.google.com/p/google-sparsehash/

यदि यह पर्याप्त नहीं है, तो आप एक हैशिंग मॉड्यूल रोल कर सकते हैं ई स्वयं द्वारा, यह आपके द्वारा परीक्षण किए गए एसटीएल कंटेनर के साथ देखी गई समस्या को हल करता है, और उपरोक्त हैशिंग एल्गोरिदम में से एक है। परिणाम कहीं कहीं पोस्ट करना सुनिश्चित करें।

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

आप देख सकते हैं कि कैसे है कि समाधान नक्शे के सैकड़ों की तुलना में कैसा प्रदर्शन कर .. मैं लगता है कि देखने के एक स्मृति रूपरेखा बिंदु से बेहतर हो सकता है ... कृपया पोस्ट करूँ परिणाम कहीं अगर आप इस व्यायाम करने मिलता है

मुझे विश्वास है कि हैशिंग एल्गोरिथ्म की तुलना में अधिक यह निरंतर ऐड हो सकता है/और सीपीयू कैश उपयोग प्रोफ़ाइल है कि आपके आवेदन

अच्छी किस्मत के प्रदर्शन के लिए और अधिक महत्वपूर्ण हो सकता है स्मृति की हटाना (यह बचा जा सकता है?)

Answer 5

Miscellaneous Container Templates से हैश टेबल आज़माएं। इसका closed_hash_map Google की dense_hash_map जैसी ही गति के बारे में है, लेकिन उपयोग करना आसान है (निहित मानों पर कोई प्रतिबंध नहीं) और इसमें कुछ अन्य सुविधाएं भी हैं।

Answer 6

एंड्रॉयड स्रोतों (इस प्रकार अपाचे 2 लाइसेंस) hashmap.c पर

https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils

देखो, से

शामिल/cutils/hashmap.h, यदि आप धागा सुरक्षा की जरूरत नहीं है तुम म्युटेक्स कोड को हटा सकते हैं लेने , नमूना कार्यान्वयन libcutils/str_parms.c

Answer 7

यदि आपके पास एक बहुप्रचारित प्रोग्राम है, तो आप intel thread building blocks library में कुछ उपयोगी हैश टेबल पा सकते हैं। उदाहरण के लिए, tbb :: concurrent_unordered_map में std :: unordered_map के समान api है, लेकिन यह मुख्य कार्य थ्रेड सुरक्षित हैं।

फेसबुक के folly library पर भी एक नज़र डालें, इसमें उच्च प्रदर्शन समवर्ती hash table और skip list है।

Answer 8

http://incise.org/hash-table-benchmarks.html जीसीसी का एक बहुत ही अच्छा कार्यान्वयन है। हालांकि, ध्यान रखें कि यह एक बहुत ही बुरा मानक निर्णय का सम्मान करना चाहिए: एक मिश्रित होता है

हैं, सभी iterators अवैध हैं, लेकिन संदर्भ और अलग-अलग तत्वों को संकेत दिए गए वैध रहेगा। यदि कोई वास्तविक रीहाश होता है, तो कोई परिवर्तन नहीं होता है।

http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/

इसका मतलब यह है मूल रूप से मानक है कि कार्यान्वयन से जुड़े हुए सूचियों पर आधारित होना चाहिए कहते हैं। यह खुले पते को रोकता है जिसमें बेहतर प्रदर्शन होता है।

मुझे लगता है कि Google स्पैस खुले पते का उपयोग कर रहा है, हालांकि इन बेंचमार्क में केवल घने संस्करण प्रतिस्पर्धा से बेहतर प्रदर्शन करते हैं। हालांकि, स्पैस संस्करण स्मृति उपयोग में सभी प्रतिस्पर्धाओं को बेहतर बनाता है। (इसमें कोई पठार नहीं है, तत्वों की शुद्ध सीधी रेखा wrt संख्या नहीं है)

Answer 9

मैं uthash का सुझाव दूंगा। बस #include "uthash.h" शामिल करें और फिर संरचना के लिए UT_hash_handle जोड़ें और अपनी संरचना में एक या अधिक फ़ील्ड को कुंजी के रूप में कार्य करने के लिए चुनें। प्रदर्शन here के बारे में एक शब्द।

Answer 10

खश बहुत कुशल है। लेखक का विस्तृत बेंचमार्क है: https://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/ और यह भी दिखाता है कि खश कई अन्य हैश पुस्तकालयों को धड़कता है।