सी # शब्दकोश मेमोरी प्रबंधन

Question

मेरे पास Dictionary<string,int> है जिसमें 10+ मिलियन अद्वितीय कुंजी के ऊपर होने की क्षमता है। मैं अभी भी शब्दकोश की कार्यक्षमता को बनाए रखते हुए, स्मृति की मात्रा को कम करने की कोशिश कर रहा हूं।

मैं के रूप में एक लंबे बजाय तार का एक हैश भंडारण का विचार था, इस (~ 1.5 गिग ~ .5 गिग करने के लिए) एक स्वीकार्य राशि के लिए क्षुधा स्मृति उपयोग कम हो जाती है, लेकिन मैं के बारे में बहुत अच्छा नहीं लग रहा है ऐसा करने के लिए मेरी विधि।

long longKey= 
BitConverter.ToInt64(cryptoTransformSHA1.ComputeHash(enc.GetBytes(strKey)), 0); 

मूल रूप से यह एक SHA1 हैश के अंत कांट-छांट कर, और एक लंबे, जो मैं तो एक प्रमुख के रूप में उपयोग में की पहली हिस्सा डालता है। हालांकि यह काम करता है, कम से कम उस डेटा के लिए जिसके साथ मैं परीक्षण कर रहा हूं, मुझे ऐसा नहीं लगता कि यह महत्वपूर्ण टकरावों की बढ़ती संभावना के कारण एक बहुत ही विश्वसनीय समाधान है।

क्या डिक्शनरी की मेमोरी पदचिह्न को कम करने के कोई अन्य तरीके हैं, या क्या मेरे ऊपर की विधि उतनी ही भयानक नहीं है जितनी मुझे लगता है?

[संपादित करें] स्पष्टीकरण के लिए, मुझे स्ट्रिंग का उपयोग करके शब्दकोश में निहित मान को देखने की क्षमता को बनाए रखने की आवश्यकता है। शब्दकोश में वास्तविक स्ट्रिंग को संग्रहीत करना बहुत मेमोरी तक जाता है। इसके बजाय मैं Dictionary<long,int> का उपयोग करना चाहता हूं जहां स्ट्रिंग पर हैशिंग फ़ंक्शन का परिणाम लंबा है।

Answer 1

इसलिए मैंने हाल ही में ऐसा कुछ किया है और मेरे अनुप्रयोग के लिए काफी अनूठे कारणों के एक निश्चित सेट के लिए डेटाबेस का उपयोग नहीं किया। वास्तव में मैं डेटाबेस का उपयोग बंद करने की कोशिश कर रहा था। मैंने पाया है कि 3.5 में GetHashCode में काफी सुधार हुआ है। एक महत्वपूर्ण नोट, गेटहाशोड से परिणाम कभी भी न करें। कभी नहीं। ढांचे के संस्करणों के बीच संगत होने की गारंटी नहीं है।

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

64 बिट हैश के लिए मैं वर्तमान में लुकअप 3 और एफएनवी 1 का उपयोग करता हूं, जो 32 बिट हैंश दोनों हैं। एक टकराव के लिए दोनों को टकराव की आवश्यकता होगी जो गणितीय रूप से असंभव है और मैंने लगभग 100 मिलियन से अधिक हैश नहीं देखा है। आप वेब पर सार्वजनिक रूप से उपलब्ध दोनों कोड को पा सकते हैं।

अभी भी अपना खुद का विश्लेषण करें। मेरे लिए क्या काम किया है आपके लिए काम नहीं कर सकता है। असल में मेरे कार्यालय के अंदर विभिन्न आवश्यकताओं के साथ विभिन्न अनुप्रयोग वास्तव में विभिन्न हैश कार्यों या हैश कार्यों के संयोजन का उपयोग करते हैं।

मैं किसी भी असुरक्षित हैश फ़ंक्शंस से बचूंगा। ऐसे लोगों के रूप में कई हैश फ़ंक्शन हैं जो सोचते हैं कि उन्हें उन्हें लिखना चाहिए। अपना शोध और परीक्षण परीक्षा परीक्षण करें।

Answer 2

स्ट्रिंग के हैश प्राप्त करने के लिए आप GetHashCode() का उपयोग क्यों नहीं करते हैं?

Answer 3

हैशटेबल कार्यान्वयन के साथ मैंने अतीत में काम किया है, हैश आपको एक बाल्टी में लाता है जो प्रायः अन्य वस्तुओं की एक लिंक सूची होती है जिसमें एक ही हैश होता है। हैश अद्वितीय नहीं हैं, लेकिन वे आपके डेटा को बहुत ही प्रबंधनीय सूचियों (कभी-कभी केवल 2 या 3 लंबे) में विभाजित करने के लिए पर्याप्त हैं, फिर आप अपनी वास्तविक वस्तु को खोजने के लिए खोज सकते हैं।

एक अच्छी हैश की कुंजी इसकी विशिष्टता नहीं है, लेकिन इसकी गति और वितरण क्षमताओं ... आप इसे जितना संभव हो उतना वितरित करना चाहते हैं।

Answer 4

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

/संपादित करें: जैसा कि एंड्रयू ने नोट किया है, इस समस्या के समाधान के बाद से इसका समाधान है। और एक सच्चे शब्दकोश की तरह, आपको टकराव के आसपास काम करना होगा। इसके लिए सबसे अच्छी योजनाओं में से एक double hashing है। दुर्भाग्य से, वास्तव में मूल मूल्यों को संग्रहीत करने के लिए केवल 100% विश्वसनीय तरीका होगा। अन्यथा, आपने एक अनंत संपीड़न बनाया होगा, जिसे हम जानते हैं कि अस्तित्व में नहीं है।

Answer 5

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

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

तारों का उपयोग अंतरिक्ष ले सकता है, लेकिन यह विश्वसनीय है ...यदि आप x64 पर हैं तो यह बहुत बड़ा नहीं होना चाहिए (हालांकि) यह निश्चित रूप से "बड़ा" के रूप में गिना जाता है ;-p)

Answer 6

बस SQLite प्राप्त करें। आपको इसे हरा करने की संभावना नहीं है, और यदि आप ऐसा करते हैं, तो शायद यह समय/प्रयास/जटिलता के लायक नहीं होगा।

SQLite।