🆓 👏 🏞️ हैश टेबल सम्मिलन प्रकार 🖋️ 👞 〽️

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

कौन परवाह करता है - मैं एक बिल्ली के लिए पूछता हूं।

इसलिए, एल्गोरिथ्म निम्नानुसार काम करता है:

पहली पास पर, हम हैश तालिका सूचकांकों (ए _मिन , ए _{मैक्स} ) की श्रेणी में मानों को पेश करने के हैश फ़ंक्शन के गुणांक की गणना के लिए स्रोत डेटा के न्यूनतम और अधिकतम मान पाते हैं।
दूसरे पास में, हम हैश फ़ंक्शन इंडेक्स = ( int ) (k * (A _i -A _min ) * TMPLEN / (एक _{अधिकतम} - _{न्यूनतम} ) का उपयोग करके सूचकांक की गणना करते हुए हैश तालिका में प्रारंभिक मान सम्मिलित करते हैं।
तीसरे पास पर, हम हैश टेबल के माध्यम से जाते हैं और सॉर्ट किए गए डेटा को मूल सरणी में कॉपी करते हैं।

टकरावों को हल करने के लिए, व्यस्त कोशिकाओं को छोड़ें (यदि डाला गया मान <= तालिका में लिखा गया है) और तालिका के दाहिने हिस्से में (पहले मुक्त सेल में) स्थानांतरित करें, यदि आवश्यक हो, तो उस स्थान पर सम्मिलित करने के लिए जहां मूल्य अधिक है।

हैश तालिका के लिए अस्थायी सरणी मूल सरणी से 2-3 गुना बड़ी है। इसके कारण, टकराव के समाधान का अनुकूलन करना और दाईं ओर केवल एक शिफ्ट का उपयोग करना संभव है।

एल्गोरिथ्म तुलना और गणना के संयोजन के साथ स्थिर सॉर्टिंग के वर्ग के अंतर्गत आता है।

कम्प्यूटेशनल जटिलता ओ (एन * लॉग एन) से होती है (जैसा कि मैं इसे समझता हूं कि सबसे खराब स्थिति में ओ (एन * एन) में ओ (एन * एन) के त्वरित छंटाई वाले जावा में तुलना करते समय। यदि आप एक उपकरण के मालिक हैं, तो आप इसे औपचारिक रूप से वापस ले सकते हैं। मैं पहले ही सब कुछ भूल चुका हूं। टिप्पणियों में आपके विचारों की प्रतीक्षा है।

एक समान वितरण के साथ, मैंने पाया कि एल्गोरिथ्म त्वरित छंटाई की तुलना में 20-25% तेजी से काम करता है!

मेमोरी ओवरहेड O (n) है ।

त्वरित छँटाई के साथ तुलना करते हुए, मैंने पाया कि स्रोत डेटा मूल्यों की एक छोटी संख्या के साथ, एल्गोरिथ्म बहुत नीचा है, क्योंकि बहुत सारे टकरावों को हल करना होगा।
हालांकि, विलय के साथ संयोजन (500 मूल्यों में ब्लॉक करना), मैंने त्वरित विलय के साथ तुलनीय प्रदर्शन किया और शुद्ध विलय से अधिक।

फायदे:

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

नुकसान:

बहुत अधिक स्मृति की आवश्यकता होती है;
मूल्यों की एक छोटी श्रेणी में या बहुत असमान वितरण के साथ, प्रदर्शन में गिरावट।

मुझे नहीं पता कि यह एल्गोरिथम व्यवहार में उपयोगी होगा या नहीं, लेकिन यह निश्चित रूप से अकादमिक अध्ययन के लिए दुख नहीं होगा।

जावा में परीक्षण के लिए मेरा स्रोत कोड।

मापदंडों के साथ खेलना आप विभिन्न मोड में परीक्षण कर सकते हैं। उदाहरण के लिए, यदि आप SORTBLOCK = SOURCELEN सेट करते हैं, तो शुद्ध हैशिंग एल्गोरिथ्म लागू किया जाएगा। MIN_VAL और MAX_VAL का उपयोग करके, आप यादृच्छिक संख्या उत्पन्न करने के लिए कई मान निर्दिष्ट कर सकते हैं।

जब SOURCELEN <300, सॉर्ट किया गया डेटा कंसोल पर आउटपुट होता है। सरणी में रिक्त मान के लिए, मैंने शून्य को चुना, इसलिए आपको इसे सीमा में शामिल नहीं करना चाहिए।

और मैं समझता हूं कि प्रदर्शन को मापना पूरी तरह से सही नहीं है। लेकिन प्रारंभिक मूल्यांकन के लिए यह करेगा। जब समय होता है, तो मैं एक विशेष ढांचे पर कोशिश करता हूं, जैसा कि सहकर्मी सलाह देते हैं।

import java.util.Arrays; import java.util.Date; import java.util.Random; public class HashSort { //     static int SOURCELEN = 1000000; int source[] = new int[SOURCELEN]; //         int quick[] = new int[SOURCELEN]; //      static int SORTBLOCK = 500; static int k = 3; //   static int TMPLEN = (SOURCELEN < SORTBLOCK * k) ? SORTBLOCK * k : SOURCELEN; int tmp[] = new int[TMPLEN]; //     static int MIN_VAL = 10; static int MAX_VAL = 1000000; int minValue = 0; int maxValue = 0; double hashKoef = 0; long finishTime = 0; long startTime = 0; long finishTimeQuick = 0; long startTimeQuick = 0; //       public void randomize() { int i; Random rnd = new Random(); for(i=0; i<SOURCELEN; i++) { int rndValue = MIN_VAL + ((int)(rnd.nextDouble()*((double)MAX_VAL-MIN_VAL))); source[i] = rndValue; } } //          - public void findMinMax(int startIndex, int endIndex) { int i; minValue = source[startIndex]; maxValue = source[startIndex]; for(i=startIndex+1; i<=endIndex; i++) { if( source[i] > maxValue) { maxValue = source[i]; } if( source[i] < minValue) { minValue = source[i]; } } hashKoef = ((double)(k-1)*0.9)*((double)(endIndex-startIndex)/((double)maxValue-(double)minValue)); } //       public void stickParts(int startIndex, int mediana, int endIndex) { int i=startIndex; int j=mediana+1; int k=0; while(i<=mediana && j<=endIndex) { if(source[i]<source[j]) { tmp[k] = source[i]; i++; } else { tmp[k] = source[j]; j++; } k++; } if( i>mediana ) { while(j<=endIndex) { tmp[k] = source[j]; j++; k++; } } if(j>endIndex) { while(i<=mediana) { tmp[k] = source[i]; i++; k++; } } System.arraycopy(tmp, 0, source, startIndex, endIndex-startIndex+1); } //         boolean shiftRight(int index) { int endpos = index; while( tmp[endpos] != 0) { endpos++; if(endpos == TMPLEN) return false; } while(endpos != index ) { tmp[endpos] = tmp[endpos-1]; endpos--; } tmp[endpos] = 0; return true; } // -    public int hash(int value) { return (int)(((double)value - (double)minValue)*hashKoef); } //         public void insertValue(int index, int value) { int _index = index; while(tmp[_index] != 0 && tmp[_index] <= value) { _index++; } if( tmp[_index] != 0) { shiftRight(_index); } tmp[_index] = value; } //         public void extract(int startIndex, int endIndex) { int j=startIndex; for(int i=0; i<(SORTBLOCK*k); i++) { if(tmp[i] != 0) { source[j] = tmp[i]; j++; } } } public void clearTMP() { if( tmp.length < SORTBLOCK*k) { Arrays.fill(tmp, 0); } else { Arrays.fill(tmp, 0, SORTBLOCK*k, 0); } } //   public void hashingSort(int startIndex, int endIndex) { // 1.          findMinMax(startIndex, endIndex); // 2.    clearTMP(); // 3.       - for(int i=startIndex; i<=endIndex; i++) { insertValue(hash(source[i]), source[i]); } // 4.         extract(startIndex, endIndex); } //          public void sortPart(int startIndex, int endIndex) { if( (endIndex - startIndex) <= SORTBLOCK ) { hashingSort(startIndex, endIndex); return; } int mediana = startIndex + (endIndex - startIndex) / 2; sortPart(startIndex, mediana); sortPart(mediana+1, endIndex); stickParts(startIndex, mediana, endIndex); } public void sort() { sortPart(0, SOURCELEN-1); } //   public String toString() { int i; String res = ""; res += "Source:"; if( SOURCELEN < 300) { for(i=0; i<SOURCELEN; i++) { res += " " + source[i]; } } res += "\n"; res += "Quick: "; if( SOURCELEN < 300) { for(i=0; i<SOURCELEN; i++) { res += " " + quick[i]; } } res += "\n"; res += "len: " + SOURCELEN + "\n"; res += "hashing&merge sort time: " + (finishTime - startTime) + "\n"; res += "quick sort time: " + (finishTimeQuick - startTimeQuick) + "\n"; return res; } //         public void copyToQuick() { System.arraycopy(source, 0, quick, 0, source.length); } public static void main(String[] args) { HashSort hs = new HashSort(); hs.randomize(); hs.copyToQuick(); hs.startTime = (new Date()).getTime(); hs.sort(); hs.finishTime = (new Date()).getTime(); hs.startTimeQuick = (new Date()).getTime(); Arrays.sort(hs.quick); hs.finishTimeQuick = (new Date()).getTime(); System.out.println(hs.toString()); } }

हैश टेबल सम्मिलन प्रकार

More articles: