शीर्ष 3 संख्याओं को खोजने के लिए सबसे तेज़ और सबसे प्रभावी तरीका?

Question

मेरे पास वर्तमान में लगभग 8 - 10 संख्याएं हैं जो आवधिक आधार पर बदलती हैं।

तो हर 5 के आसपास - 10 सेकंड संख्या अपडेट होते हैं।

मैं हर 10 सेकंड सरणी में शीर्ष 3 नंबर प्राप्त करने की जरूरत है।

यह सब एक मोबाइल डिवाइस पर किया जाता है। इसलिए अपने कार्यालय में अपने आम तौर पर लगभग 10 लेकिन क्षेत्र में परीक्षण यह मिनट मैं सरणी 3 बार के माध्यम से पुनरावृति पर चारों ओर 50

तक बढ़ सकता

सरणी, वर्तमान में स्कैन किया पहुंच बिंदुओं की RSSI है और हर बार जब मैं तीन उच्चतम संख्याओं को निकालता हूं और उन्हें तीन पहले घोषित चर में डाल देता हूं।

मेरा प्रश्न मैं इस उदाहरण में गति और दक्षता बढ़ाने के लिए क्या करना है दिखना चाहिए है?

Answer 1

संख्या केवल 10 कर रहे हैं - कुछ भी नहीं। यह पहले से ही काफी कुशल है।

यदि आकार बढ़ता है, तो आप अपनी संख्याओं को संग्रहीत करने के लिए max-heap का उपयोग कर सकते हैं।

Answer 2

क्यों Arrays.sort विधि का उपयोग नहीं करते हैं, जहां तक ​​मैं हुड के नीचे quick sort से अवगत हूं।

पॉल

संपादित करें: इसे इस्तेमाल करता है एक tuned quick sort

Answer 3

आपका एल्गोरिथ्म पहले से ही हे (एन), त्वरित तरह है सत्यापित> O (n n लॉग इन करें) इतना है कि निश्चित रूप से जिस तरह से यह करने के लिए नहीं है। यदि आप पेड़ की संरचना का उपयोग करते हैं, उदाहरण के लिए एवीएल पेड़ का उपयोग करते हैं तो आप गति को ओ (लॉग एन) में बढ़ा सकते हैं। केवल सरणी के लिए, आपका वर्तमान एक ऐसा करने का सबसे तेज़ तरीका है।

Answer 4

आप वर्तमान एल्गोरिथ्म 3 * n तुलना की जरूरत है। आपको लगता है कि सुधार करने के लिए प्रविष्टि प्रकार का परिवर्तन प्रदर्शन कर सकता है:

1. इनपुट सरणी के आइटम के बाकी के माध्यम से उत्पादन सरणी में इनपुट सरणी के पहले 3 आइटम रखो, तरह उन्हें
2. दोहराएं,
   1. प्रत्येक आइटम उत्पादन सरणी में सही स्थिति
   2. पर 3

आइटम करने के लिए उत्पादन सरणी रखो ट्रिम

इसे 2 * एन तुलना की आवश्यकता है। (मुझे यकीन है कि अगर यह, अतिरिक्त जटिलता के लायक है, हालांकि नहीं हूँ।)

Answer 5

मैं सामान्य मामले में लगता है कि आप आप समय हे में, QuickSelect एल्गोरिथ्म जो quicksort पर आधारित है और उपयोग करने का उपयोग करना चाहिए (एन) अपने सरणी को संशोधित करता है इनलाइन और 'अर्ध-क्रम' इसे।

कहें कि आपकी सरणी एक [1..10] है और क्विकसेलेक्ट (ए, 7) को कॉल करके सॉर्ट नहीं किया गया है, आप पूछ रहे हैं 'सॉर्टेड सरणी में सातवीं स्थिति में कौन सा नंबर होना चाहिए?', और यह कहने जैसा ही है 'इस विशेष सरणी में कौन सा नंबर तीसरा बड़ा है?'।अब बड़ी बात यह है कि क्विक सिलेक्ट यह सुनिश्चित करता है कि इस कॉल के बाद ए [i] < = ए [7] सभीi < 7 और ए [7] < = ए [जे] सभी 7 < जे के लिए। विकिपीडिया Quick Selection Algorithm में अधिक जानकारी।

आकार सिर्फ 10 है फिर भी रूप में, आप प्रविष्टि-तरह का उपयोग करें (सबसे खराब स्थिति O (n^2) लेकिन छोटे सरणियों के साथ अच्छा काम करता है) और फिर तीन प्रथम/अंतिम तत्व मिल सकता है

संपादित करें: - वृक्ष संरचनाएं केवल दस तत्वों के लिए एक ओवरकिल हैं, और आम तौर पर एक समय/स्थान व्यापार (आपको बहुत सारे पॉइंटर्स की आवश्यकता होती है) - क्विकसेलेक्ट में ओ (एन^2) सबसे खराब केस परिदृश्य है, लेकिन 'मध्य-मध्य-मेडियन 'एक ही परिणाम को एक सबसे खराब मामले में प्राप्त करता है ओ (एन)