मैं कैसे परीक्षण कर सकता हूं कि मेरे हैश फ़ंक्शन अधिकतम लोड के मामले में अच्छा है?

Question

मैंने 'बॉल्स और डिब्बे' समस्या पर विभिन्न कागजात पढ़े हैं और ऐसा लगता है कि यदि हैश फ़ंक्शन सही काम कर रहा है (यानी यह प्रभावी रूप से एक यादृच्छिक वितरण है) तो यदि हैश n मान हैं तो निम्नलिखित सत्य होना चाहिए n स्लॉट (या डिब्बे) के साथ एक हैश तालिका में:

1. संभावना है कि एक बिन खाली है, बड़े n के लिए 1/e है।
2. खाली डिब्बे की अपेक्षित संख्या n/e है।
3. संभावना है कि एक बिन k गेंद <= 1/ek! (सही) है।
4. संभावना है कि एक बिन में कम से कम के टकराव हैं <= ((e/k)**k)/e (सही)।

ये देखने के लिए आसान लग रहा है। लेकिन max-load परीक्षण (उच्च संभावना वाले टकराव की अधिकतम संख्या) आमतौर पर अस्पष्ट रूप से कहा जाता है।

अधिकांश ग्रंथ बताते हैं कि किसी भी बिन में टकराव की अधिकतम संख्या O(ln(n)/ln(ln(n))) है। कुछ कहते हैं कि यह 3*ln(n)/ln(ln(n)) है। अन्य कागजात ln और log मिश्रण करते हैं - आमतौर पर उन्हें परिभाषित किए बिना, या log लॉग बेस ई है और फिर ln कहीं और उपयोग करें।

ln लॉग e या 2 आधार पर है और इस max-load सूत्र सही है और कितना बड़ा n एक परीक्षण चलाने के लिए किया जाना चाहिए?

यह व्याख्यान इसे सबसे अच्छा कवर करने लगता है, लेकिन मैं कोई गणितज्ञ नहीं हूं।

http://pages.cs.wisc.edu/~shuchi/courses/787-F07/scribe-notes/lecture07.pdf

Btw, with high probability1 - 1/n मतलब लगता है।

Answer 1

यह एक आकर्षक पेपर/व्याख्यान है - मुझे इच्छा है कि मैंने कुछ औपचारिक एल्गोरिदम कक्षाएं ली हैं।

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

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

इस बात को ध्यान में रखते हुए, मैं अनुभवजन्य परीक्षण चलाऊंगा, क्योंकि मैं दिल में जीवविज्ञानी हूं और मुझे वास्तव में काम करने के संकेतों के रूप में कठिन और तेज़ सबूत से बचने के लिए प्रशिक्षित किया गया था।कुछ संख्या के रूप में एन के साथ शुरू करें, 100 कहें, और बिन को सबसे बड़ी संख्या में टकराव के साथ ढूंढें। यह उस दौड़ के लिए आपका अधिकतम भार है। अब, आपके उदाहरण वास्तविक उपयोगकर्ताओं के उपयोग के लिए जितना संभव हो उतना करीब होना चाहिए, इसलिए हो सकता है कि आप यादृच्छिक रूप से किसी शब्दकोष या आपके इनपुट के समान कुछ शब्द खींचें।

कम से कम 30 या 40 बार परीक्षण करें। चूंकि आप यादृच्छिक संख्याओं का उपयोग कर रहे हैं, इसलिए आपको स्वयं को संतुष्ट करने की आवश्यकता होगी कि आपके द्वारा प्राप्त औसत अधिकतम लोड सैद्धांतिक 'अपेक्षा' के करीब है आपका एल्गोरिदम अपेक्षा केवल औसत है, लेकिन आपको अभी भी इसे खोजने की आवश्यकता होगी, और उस औसत के बारे में आपके std dev/std त्रुटि को जितना कठिन होगा, उतना ही आप कह सकते हैं कि आपका अनुभवजन्य औसत सैद्धांतिक अपेक्षा से मेल खाता है। एक रन पर्याप्त नहीं है, क्योंकि दूसरा रन (सबसे अधिक संभावना) एक अलग जवाब देगा।

फिर, एन, कहने के लिए, 1000, 10000, आदि को बढ़ाएं, इसे लॉगरिदमिक रूप से बढ़ाएं, क्योंकि आपका सूत्र लॉगरिदमिक है। जैसे ही आपका एन बढ़ता है, आपका अधिकतम भार एलएन (एन)/एलएन (एलएन (एन)) के क्रम में बढ़ाना चाहिए। यदि यह 3 * एलएन (एन)/एलएन (एलएन (एन)) की दर से बढ़ता है, तो इसका मतलब है कि आप उस व्याख्यान में बताए गए सिद्धांत का पालन कर रहे हैं।

इस प्रकार का अनुभवजन्य परीक्षण आपको यह भी दिखाएगा कि आपका दृष्टिकोण टूट गया है। यह हो सकता है कि आपका एल्गोरिदम एन < 10 मिलियन (या कुछ अन्य नंबर) के लिए अच्छी तरह से काम करता है, लेकिन इसके ऊपर, यह पतन शुरू हो जाता है। वह क्यों हो सकता है? हो सकता है कि आपके कोड में 32 बिट्स को कुछ समझने के बिना आपके पास कुछ सीमा हो (यानी, 'डबल' के बजाय 'फ्लोट' का उपयोग करके), या कुछ अन्य कार्यान्वयन विवरण। इस प्रकार के विवरण आपको बताते हैं कि आपका कोड अभ्यास में अच्छी तरह से काम करेगा, और फिर आपकी व्यावहारिक जरूरतों को बदलने के बाद, आप अपने एल्गोरिदम को संशोधित कर सकते हैं। हो सकता है कि बहुत बड़े डेटासेट के लिए एल्गोरिदम काम करना बहुत छोटे लोगों के लिए बहुत अक्षम हो, या इसके विपरीत, तो यह इंगित करें कि ट्रेडऑफ आपको यह जानने में मदद करेगा कि आप अपने एल्गोरिदम को विशेष परिस्थितियों में कैसे अनुकूलित कर सकते हैं। हमेशा एक उपयोगी कौशल है।

संपादित करें: क्यों लॉग समारोह के आधार बड़े हे संकेतन के साथ कोई फर्क नहीं पड़ता का एक सबूत:

log N = log_10 (N) = log_b (N)/log_b (10)= (1/log_b(10)) * log_b(N) 

1/log_b (10) एक निरंतर है, और बड़े-ओ अंकन में, स्थिरांक को नजरअंदाज कर दिया जाता है। आधार परिवर्तन निःशुल्क हैं, यही कारण है कि आप कागजात में इस तरह के बदलाव का सामना कर रहे हैं।

Answer 2

कुछ और शोध और परीक्षण-और-त्रुटि के बाद मुझे लगता है कि मैं किसी उत्तर के लिए कुछ अंश मार्ग प्रदान कर सकता हूं।

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

2. max-load आपकी पसंद की किसी भी संभावना के लिए परिभाषित किया जा सकता है। ठेठ इस्तेमाल किया सूत्र

   1-1 है/एन ** ग

विषय उपयोग

1-1/n 

एक उदाहरण के लिए सबसे आसान हो सकता है पर अधिकांश कागजात।

कहें कि आपके पास 1000 स्लॉट की हैश तालिका है और आप हैश 1000 चीजें चाहते हैं। मान लें कि 1-1/1000 या 0.999 की संभावना के साथ आप max-load को भी जानना चाहते हैं।

max-load हैश मानों की अधिकतम संख्या है जो समान होती है - यानी। टकराव (मानते हुए कि आपका हैश फ़ंक्शन अच्छा है)।

बिल्कुल k समान हैश प्राप्त होने की संभाव्यता के लिए सूत्र का उपयोग कुल बराबरी जब तक बिल्कुल 0..k आइटम की संभावना अर्जित होने के कारण तो

Pr[ exactly k ] = ((e/k)**k)/e 

को महत्व देता है या 0.999 आपको बताता है कि kmax-load है से अधिक है।

उदाहरण के लिए।

Pr[0] = 0.37 
Pr[1] = 0.37 
Pr[2] = 0.18 
Pr[3] = 0.061 
Pr[4] = 0.015 
Pr[5] = 0.003  // here, the cumulative total is 0.999 
Pr[6] = 0.0005 
Pr[7] = 0.00007 

तो, इस मामले में, max-load5 है।

तो यदि मेरा हैश फ़ंक्शन डेटा के मेरे सेट पर अच्छी तरह से काम कर रहा है तो मुझे समान हैश मानों (या टकराव) की अधिकतम संख्या 5 होने की उम्मीद करनी चाहिए।

यदि यह तो नहीं है यह निम्न कारणों से हो सकता है:

1. आपका डाटा छोटे मान (संक्षिप्त स्ट्रिंग की तरह) है एक ही मूल्य है कि हैश। एक ASCII चरित्र का कोई भी हैश 128 हैश मानों में से एक चुनता है (इसके आसपास के तरीके हैं। उदाहरण के लिए आप कई हैश फ़ंक्शंस का उपयोग कर सकते हैं, लेकिन हैशिंग को धीमा कर देते हैं और मुझे इसके बारे में बहुत कुछ पता नहीं है)।

2. आपका हैश फ़ंक्शन आपके डेटा के साथ अच्छा काम नहीं करता है - इसे यादृच्छिक डेटा के साथ आज़माएं।

3. आपका हैश फ़ंक्शन अच्छी तरह से काम नहीं करता है।

मेरे प्रश्न में मैंने जो अन्य परीक्षणों का उल्लेख किया है, यह भी उपयोगी है कि आपका हैश फ़ंक्शन अपेक्षित रूप से चल रहा है।

संयोग से, मेरे हैश फ़ंक्शन ने अच्छी तरह से काम किया - लघु (1..4 वर्ण) तारों को छोड़कर।

मैंने एक साधारण स्प्लिट-टेबल संस्करण भी लागू किया जो हैश मान को कम से कम 2 स्थानों की पसंद से कम से कम इस्तेमाल किए गए स्लॉट में रखता है। यह टकरावों की संख्या से अधिक है और इसका मतलब है कि हैश तालिका जोड़ना और खोजना थोड़ा धीमा है।

मुझे उम्मीद है कि इससे मदद मिलती है।

Answer 3

समान वितरण और अधिकतम भार सहित इस समस्या के समाधान के लिए यहां एक कठिन शुरुआत है।

डिब्बे और गेंदों या कलम या बक्से या बाल्टी या एम और एन, लोगों (पी) और दरवाजे (डी) के बजाय पदनाम के रूप में उपयोग किया जाएगा।

कुछ निश्चित लोगों को दिए गए प्रत्येक दरवाजे के लिए एक सटीक अपेक्षित मूल्य है। उदाहरण के लिए, 5 लोगों और 5 दरवाजों के साथ, अनुमानित अधिकतम दरवाजा औसत (पी/डी) से 1.2864 {(1429-625)/625} है और न्यूनतम दरवाजा बिल्कुल -0.9616 {(24-625)/625 है } मतलब के नीचे}। माध्य से उच्चतम दरवाजे की दूरी का पूर्ण मूल्य छोटे दरवाजे की तुलना में थोड़ा बड़ा है क्योंकि सभी लोग एक दरवाजे से गुजर सकते हैं, लेकिन दरवाजे से एक भी शून्य से कम नहीं जा सकता है।बड़ी संख्या में लोगों (पी/डी> 3000) के साथ, औसत और निम्नतम दरवाजे से उच्चतम दरवाजे की दूरी के पूर्ण मूल्य के बीच का अंतर नगण्य हो जाता है।

दरवाजे की एक विषम संख्या के लिए, केंद्र का दरवाजा अनिवार्य रूप से शून्य है और स्केलेबल नहीं है, लेकिन अन्य सभी दरवाजे पी = डी का प्रतिनिधित्व करने वाले कुछ मूल्यों से स्केलेबल हैं। घ = 5 के लिए ये गोल मान हैं:

-1,163 -0,495 0 * 0,495 1,163 * धीरे-धीरे से -0.12

तो इन मानों से शून्य के करीब पहुंच, आप लोगों की उम्मीद की संख्या लोगों में से किसी की गिनती के लिए गणना कर सकता है अधिकतम दरवाजे सहित 5 दरवाजों में से प्रत्येक के माध्यम से जा रहा है। मध्यम आदेशित द्वार के अलावा, माध्य से अंतर sqrt (पी/डी) द्वारा स्केलेबल है।

तो, पी के लिए = 50,000 और घ = 5:
अपेक्षित अधिकतम दरवाजा है, जो 5 दरवाजे के किसी भी, = 1.163 * sqrt (पी/डी) + पी/डी किया जा सकता है के माध्यम से जा रहे लोगों की संख्या। = 1.163 * वर्ग (10,000) + 10,000 = 10,116.3 पी/डी < 3,000 के लिए, इस समीकरण से परिणाम थोड़ा बढ़ाया जाना चाहिए।

अधिक लोगों के साथ, मध्य दरवाजा धीरे-धीरे शून्य के करीब और 0.11968 से पी = 100 और डी = 5 पर शून्य के करीब आता है। इसे हमेशा शून्य तक गोल किया जा सकता है और अन्य 4 दरवाजे की तरह काफी अंतर होता है।

6 दरवाजों के लिए मूल्य हैं: -1,272 -0,643 -0,202 0,202 0,643 1,272

1000 दरवाजे के लिए, अनुमानित मान हैं: -3.25, -2.95, -2.79 ... 2.79, 2.95, 3.25

किसी भी डी और पी के लिए, आदेशित दरवाजे के लिए एक सटीक अपेक्षित मूल्य है। उम्मीद है कि, एक अच्छा अनुमान (एक सापेक्ष त्रुटि < 1% के साथ) मौजूद है। कुछ प्रोफेसर या गणितज्ञ को कहीं पता होना चाहिए।

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

640 बिट पूर्णांक का उपयोग करके सरासर ब्रूट फोर्स गणना द्वारा 5 और 6 दरवाजे के लिए अपेक्षित मूल्य प्राप्त किए गए थे और इसी विपरीत दरवाजे के पूर्ण मूल्यों के अभिसरण औसत थे। घ के लिए = 5 और पी = 170: -6,63901 -2,95905 -0,119342 2,81054 6,90686 (27,36099 31,04095 33,880658 36,81054 40,90686) घ के लिए = 6 और पी = 108: -5,19024 -2,7711 -0,973979 0,734434 2,66716 5,53372 (12,80976 15.228 9 17.026021 18.734434 20.66716 23.53372)

मुझे आशा है कि आप अपने डेटा को समान रूप से वितरित कर सकते हैं।

• यह लगभग गारंटी है कि जॉर्ज फोरमैन के बेटे या कुछ समान स्थिति आपके हैश फ़ंक्शन के खिलाफ लड़ेंगे। और उचित आकस्मिक योजना सभी अच्छे प्रोग्रामर का काम है।