सॉर्टिंग ... एक हैश टेबल (एक ट्री काउंट और एक हैशपॉप द्वारा भी)

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

तीनों प्रकार की छंटाई ऐसे मामलों के लिए महान होती है जब सरणी में कई अद्वितीय तत्वों की शक्ति अपेक्षाकृत कम होती है (इसका मतलब यह है कि हम परीक्षण के परिणामों पर एक नज़र डालने के बाद स्पष्ट हो जाएंगे)।

ट्री काउंट सॉर्ट

हम स्टीम ट्री (की, क्वांटिटी) का निर्माण करते हैं, जहां एरे तत्व के लिए कुंजी जिम्मेदार है, और क्वांटिटी इस एरे तत्व के दोहराव की संख्या है। उदाहरण के लिए, पेड़ प्राकृतिक रूप से संतुलित, काला और लाल है।

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

हम सरणी को फिर से लिखते हैं, हर बार शीर्ष को हटाते हैं और कुंजी को उसकी संख्या के रूप में कई बार लिखते हैं।

पेड़ को स्वयं लागू करने के लिए नहीं, वर्णित एल्गोरिथ्म के लिए मैंने ट्रीसेट का उपयोग किया, जो एक काले-लाल पेड़ पर काम करता है।

HashMap का उपयोग करना

हम सरणी तत्व को कुंजी के रूप में संग्रहीत करेंगे, और कुंजी मूल्य के रूप में दोहराव की संख्या।

मेरी अपनी हैश टेबल का उपयोग करना

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

टकराव

जाहिर है, टकराव हो सकते हैं और यह हैश के निर्धारण के समय और हैश के परिणामस्वरूप सरणी को क्रमबद्ध करने की गति (आदेशित या लगभग ऑर्डर किए गए डेटा को तेजी से क्रमबद्ध करने) की गति को बुरी तरह से प्रभावित करेगा। लेकिन यहाँ एक बात है: टेबल के फैलते ही हमारा हैश ff बदल जाता है। तो ऐसे डेटा को चुनने के लिए विशेष रूप से अधिक कठिन हो जाता है। इसके अलावा, लोड फैक्टर और विस्तार गुणांक को यादृच्छिक (एक निश्चित सीमा में, निश्चित रूप से) करना संभव है, जिससे टकराव को जन्म देने वाले मूल्यों का पूर्व-चयन करना असंभव हो जाएगा। ठीक है, अगर एक तालिका में कुछ डेटा टकराव का कारण बने, तो री-हैश के बाद, टकरावों की संख्या काफी कम हो सकती है (कई बार)। कमजोर बिंदु संख्याओं के भाज्य होंगे, लेकिन वे अविश्वसनीय रूप से छोटे हैं (2 ^ 31 तक, उदाहरण के लिए, उनमें से केवल 11 हैं (0 को छोड़कर))।

क्रिप्टोग्राफिक हैश हमारे लिए उपयुक्त नहीं हैं, और क्योंकि उनके साथ आप लगभग ऑर्डर किए गए ऐरे के बारे में भूल सकते हैं (चाबियाँ द्वारा ऑर्डर करने के अर्थ में)।

काम का समय

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

स्मृति से क्या?

ट्री-काउंट छँटाई के लिए O (अलग) (n) अतिरिक्त मेमोरी की आवश्यकता होगी
एक हैश तालिका के लिए, हमें हेश को चुनने के लिए ओ (अलग (एन)) मेमोरी + मेमोरी की आवश्यकता होती है (चयनित एल्गोरिदम के आधार पर)।

यहां मिलीसेकंड में परिणाम हैं कि मैं यादृच्छिक संख्या में मिला जब वस्तुओं की एक सरणी को 10 मिलियन elts में क्रमबद्ध करता है, जिसमें मानों की एक सीमा होती है [0; x]:

परीक्षण पर, मेरी हैश तालिका में लोड कारक = 0.75, प्रारंभिक क्षमता = 20, तालिका हर बार दोगुनी हो जाती है

X = 10 के लिए:
2044 - एकीकृत
285 - ट्री काउंट (उसटोव सॉर्ट)
276 - हैशपॉप (उसातोव-प्रोकोरट सॉर्ट)
140 - मेरी हैश टेबल के साथ (Usatov-Prokurat myHashTable का उपयोग करके)

x = 100:
2406 - बिल्ट-इन
455 - गिनती के पेड़
283 - हैशपॉप
134 - हैश टेबल

x = 1_000:
2171 - एकीकृत
930 - गिनती के पेड़
380 - हैशपॉप
209 - हैश टेबल

x = 10_000
2879 - एकीकृत
1666 - पेड़ की गिनती
634 - हैशपॉप
326 - हैश टेबल

x = 100_000
4045 - एकीकृत
2899 - पेड़ की गिनती
866 - हैशपॉप
762 - हैश टेबल

x = 1_000_000
4997 - एकीकृत
5762 - गिनती के पेड़
2505- हैशपॉप
1294 - हैश टेबल

x = 10_000_000
5083 - एकीकृत
11480 - पेड़ की गिनती
5099 - हैशपॉप
3240 - हैश टेबल

जैसा कि मैंने शुरुआत में कहा, ये छांटें उन मामलों के लिए सबसे उपयुक्त हैं जब सरणी के कई तत्वों की शक्ति सरणी के आकार के सापेक्ष पर्याप्त रूप से छोटी होती है।

यह भी ध्यान देने योग्य है कि बिल्ट-इन सॉर्टिंग ऑर्डर (लगभग ऑर्डर किए गए) डेटा (या रिवर्स ऑर्डर में एक सरणी) पर बहुत तेजी से काम करता है, लेकिन मेरी विधि यादृच्छिक संख्याओं पर इसे तेजी से करती है।

ट्री गणना क्रमबद्ध करें:

static void usatovSort(Integer[] arr) { TreeSet<MyPair> tree = new TreeSet<>(); MyPair temp; MyPair mp = new MyPair(); for (int i : arr) { temp = mp; temp.first = i; temp = tree.ceiling(temp); if (temp != null && temp.first == i) //   , .    ,      temp.second++; else tree.add(new MyPair(i, 1)); } int ptr = 0; while (!tree.isEmpty()) { temp = tree.pollFirst(); for (int i = 0; i < temp.second; i++) arr[ptr++] = temp.first; } } 

HashMap के माध्यम से क्रमबद्ध करें:

  static void usatovProkuratSortUsingHashMap(Integer[] arr) { HashMap<Integer, Integer> hm = new HashMap<>(); Integer temp; for (Integer i : arr) { temp = hm.get(i); if (temp == null) hm.put(i, 1); else hm.put(i, temp + 1); } ArrayList<Integer> keys = new ArrayList<>(hm.keySet().size()); keys.addAll(hm.keySet()); keys.sort(Comparator.naturalOrder()); int ptr = 0; for (Integer i : keys) for (int j = 0; j < hm.get(i); j++) arr[ptr++] = i; } 

मेरी हैश तालिका के माध्यम से क्रमित करें:

  static void usatovProkuratSortUsingMyHashTable(Integer[] arr) { MyHashTable mht = new MyHashTable(); for (Integer i : arr) mht.add(i); MyPair[] res = mht.getPairs(); int ptr = 0; Arrays.sort(res, Comparator.comparingInt(o -> o.first)); for (MyPair mp : res) for (int i = 0; i < mp.second; i++) arr[ptr++] = mp.first; } 

हैश तालिका का कार्यान्वयन:

 public class MyHashTable { private MyPair[] hashArr; private double count = 0; private double loadFactor = 0.5; private double expansivity = 2; private static final int DEFAULT_CAPACITY = 20; public MyHashTable() { hashArr = new MyPair[DEFAULT_CAPACITY]; } public MyHashTable(double loadFactor) { hashArr = new MyPair[DEFAULT_CAPACITY]; this.loadFactor = loadFactor; } public MyHashTable(int capacity) { hashArr = new MyPair[capacity]; } public MyHashTable(int capacity, double loadFactor) { hashArr = new MyPair[capacity]; this.loadFactor = loadFactor; } public MyHashTable(int capacity, double loadFactor, double expansivity) { hashArr = new MyPair[capacity]; this.loadFactor = loadFactor; this.expansivity = expansivity; } public MyPair[] getPairs() { MyPair[] pairs = new MyPair[(int) count]; int ptr = 0; for (MyPair i : hashArr) if (i != null) pairs[ptr++] = i; return pairs; } public MyPair get(int key) { int add = 0; while (true) if (hashArr[(key + add) % hashArr.length].first == key) { return hashArr[(key + add) % hashArr.length]; } else if (add++ == hashArr.length) return null; } public void add(int key) { if (count / hashArr.length >= loadFactor) grow(); int add = 0; while (true) { if (hashArr[(key + add) % hashArr.length] == null) { hashArr[(key + add) % hashArr.length] = new MyPair(key, 1); count++; return; } if (hashArr[(key + add) % hashArr.length].first == key) { hashArr[(key + add) % hashArr.length].second++; return; } add++; } } public void add(MyPair newMP) { if (count / hashArr.length >= loadFactor) grow(); int add = 0; while (true) { if (hashArr[(newMP.first + add) % hashArr.length] == null) { hashArr[(newMP.first + add) % hashArr.length] = newMP; count++; return; } if (hashArr[(newMP.first + add) % hashArr.length].first == newMP.first) { hashArr[(newMP.first + add) % hashArr.length].second += newMP.second; return; } add++; } } private void grow() { MyPair[] oldHash = hashArr; hashArr = new MyPair[(int) (expansivity * hashArr.length)]; for (MyPair i : oldHash) if (i != null) innerAdd(i); } private void innerAdd(MyPair mp) { int add = 0; while (true) { if (hashArr[(mp.first + add) % hashArr.length] == null) { hashArr[(mp.first + add) % hashArr.length] = mp; return; } if (hashArr[(mp.first + add) % hashArr.length].first == mp.first) { hashArr[(mp.first + add) % hashArr.length].second += mp.second; return; } add++; } } } 

स्टीम क्लास:

 public class MyPair implements Comparable<MyPair> { public int first; public int second; public MyPair() { } public MyPair(int first, int second) { this.first = first; this.second = second; } @Override public int compareTo(MyPair o) { return first - o.first; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; MyPair myPair = (MyPair) o; return first == myPair.first; } @Override public int hashCode() { return first; } }