किसी सरणी में अक्सर होने वाले तत्वों को खोजें

कार्य: N की लंबाई के सरणी में एक ऐसा तत्व मिलता है जो N / 2 बार से अधिक दोहराया जाता है।

यह प्रतीत होता है, सोचने के लिए क्या है? चलिए शब्दकोश लेते हैं <तत्व मान, दिखावे की संख्या>, सरणी में से गुजरते हुए हम प्रत्येक तत्व की घटनाओं को गिनते हैं, फिर उस तत्व का चयन करते हैं जिसे हम शब्दकोश से ढूंढ रहे हैं। समाधान ओ ( एन ) है, जहां यह और भी तेज हो सकता है?

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

सौभाग्य से नहीं: पर्याप्त ओ (1) अतिरिक्त मेमोरी, और अभी भी एक सरणी से गुजरता है। बोयर-मूर एल्गोरिथ्म - बहुत बोयर और मूर एल्गोरिथ्म जो बहुत अधिक प्रसिद्ध विकल्प एल्गोरिथ्म के साथ आया था - इस प्रकार की कल्पना करना सबसे आसान है : एन लोग पार्टी में एकत्र हुए , और प्रत्येक के पास सरणी से एक तत्व है। जब दो मिलते हैं, जिनके तत्व अलग होते हैं, तो वे इस पर चर्चा करने के लिए बैठते हैं। अंत में, केवल एक ही तत्व वाले लोग खड़े रहेंगे; स्पष्ट रूप से यह वही तत्व है जो एन / 2 बार से अधिक हुआ है ।

बोयर-मूर एल्गोरिथ्म के कार्यान्वयन में केवल कुछ लाइनें लगती हैं:

int* majority(int[] array, int N) { int confidence = 0; //  ,       int* candidate = NULL; //  ,    -- // ,      //          for (int i = 0; i<N; i++) { //      ,      if (confidence == 0) { candidate = array+i; confidence++; } //        , //      ,       else if (*candidate == array[i])) confidence++; else confidence--; } return confidence > 0 ? candidate : NULL; } 

अंत में, हमें एन / 2 उदाहरणों में उपस्थिति के लिए "सबसे अधिक संभावना वाले उम्मीदवार" मिलते हैं: यदि सरणी में ऐसा कोई तत्व वास्तव में मौजूद है, तो यह मिल जाएगा; यदि ऐसा कोई तत्व नहीं है, तो शायद कुछ गरीब साथी, जिनके पास कुछ भी नहीं है, खड़े रहेंगे। majority अधिक कठोर कार्यान्वयन के लिए majority दूसरी बार सरणी से गुजरना होगा और जांचना होगा कि क्या पाया गया तत्व वास्तव में आवश्यक संख्या में पाया गया है।


आइए कार्य को जटिल करते हैं। अब लंबाई N की एक सरणी में आपको उन तत्वों को खोजने की आवश्यकता है जो N / 3 बार से अधिक दोहराए जाते हैं - यदि दो हैं, तो दोनों, यदि एक है, तो एक।

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

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

कोड पिछले एक से थोड़ा अलग है: सरणी और O (1) अतिरिक्त मेमोरी के माध्यम से एक पास अभी भी है।

 void majority(int[] array, int N, int** cand1, int** cand2) { int conf1 = 0, conf2 = 0; //       *cand1 = NULL; *cand2 = NULL; //       //          for (int i = 0; i<N; i++) { //     ,   ?      if (conf1 > 0 && **cand1 == array[i]) conf1++; else if (conf2 > 0 && **cand2 == array[i]) conf2++; else // ,     ,    ? if (conf1 == 0) { *cand1 = array+i; conf1++; } else if (conf2 == 0) { *cand2 = array+i; conf2++; } else { //     ,      conf1--; conf2--; } } if(conf1 == 0) *cand1 = NULL; if(conf2 == 0) *cand2 = NULL; } 

यह एल्गोरिथ्म 1982 में अमेरिकी वैज्ञानिकों जयदेव मिश्रा और डेविड ग्रिस द्वारा प्रकाशित किया गया था, और वे एक अधिक उबाऊ रूपक का उपयोग करते हैं - एन नंबर के साथ एक बैग, जिसमें से वे प्रत्येक ऑपरेशन के लिए 3 अलग-अलग संख्याएं निकालते हैं। इसके अलावा, उनका छद्म कोड किसी भी भाषा की तरह नहीं है जो एक आधुनिक प्रोग्रामर के लिए समझ में आता है। मुझे पिछले वर्ष के पहले अमेरिकी प्रोफेसर अमित चक्रवर्ती के व्याख्यान नोट्स में उनके एल्गोरिथ्म की व्याख्या पसंद आई।



सबसे सामान्य रूप में, जब लंबाई एन की एक सरणी में आपको उन तत्वों को खोजने की आवश्यकता होती है जो एन / के बार से अधिक दोहराए जाते हैं - आपको अभी भी शब्दकोश का उपयोग करना होगा। हम शब्दकोश में केवल उन तत्वों को संग्रहीत करेंगे जिनके साथ लोग खड़े हैं - अर्थात्। के -1 प्रविष्टियों से अधिक नहीं।

 int[] majority(int[] array, int N, int k) { //      Dictionary<int,uint> candidates = new Dictionary<int,uint>{}; //        k for (int i = 0; i<N; i++) { //     ,   ?      if (candidates.ContainsKey(array[i])) candidates[array[i]]++; else // ,     k-1 ? if (candidates.Count < k - 1) candidates[array[i]] = 1; else //   k-1  ,      foreach(int l in candidates.Keys) if (candidates[l]-- == 0) // (**) candidates.Remove(l); // (*) } return candidates.Keys.ToArray(); } 

एल्गोरिथ्म के इस सबसे सामान्य रूप में, सरणी और O ( k ) अतिरिक्त मेमोरी के माध्यम से एक पास अभी भी है। यदि हम शब्दकोश के कार्यान्वयन के लिए एक हैश तालिका का उपयोग करते हैं और सूची में सभी प्रविष्टियों को सूची में लिंक करते हैं, तो एल्गोरिथम की समग्र जटिलता रैखिक रहेगी: शब्दकोश से प्रविष्टि को हटाने के साथ लाइन (*) सबसे अधिक एन बार पर प्रदर्शन किया जाता है, क्योंकि मुख्य लूप के प्रत्येक पुनरावृत्ति में, इसे शब्दकोश में जोड़ा जाता है। एक से अधिक प्रवेश नहीं। एक अभ्यास के रूप में, पाठकों को यह समझने के लिए आमंत्रित किया जाता है कि रेखा (**) एल्गोरिदम की रैखिकता का उल्लंघन क्यों नहीं करती है।

इस प्रकार, एक छोटी सी मेमोरी वाला हमारा उपकरण एक शराबी जानवर के साथ संवाद कर सकता है, जिसे हाल ही में हैबरूमेल ने तैयार किया है। इस जानवर के संकेतों के पांच तार्किक स्तर हैं: हमने k = 6 सेट किया है, और हम सभी पाँच स्तरों को सही तरीके से चलते हैं, यहां तक ​​कि स्मृति को सिग्नल को बचाने के बिना भी। यह केवल एक प्रोटोकॉल प्रदान करने के लिए आवश्यक है ताकि सिग्नल में सभी पांच स्तर समान रूप से पाए जाएं।

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

चित्र के साथ पाठ को पुनर्जीवित करने के लिए धन्यवाद Nitatunarabe