एक अनियंत्रित सूची के कई उप श्रेणियों में मध्यस्थ खोजें

Question

E.g. एन तत्वों की एक अनियमित सूची दी गई, उप श्रेणियों के लिए औसत खोजें 0..100, 25..200, 400..1000, 10..500, ... मुझे प्रत्येक के माध्यम से जाने से बेहतर तरीका नहीं दिख रहा है उप श्रेणी और मानक औसत खोज एल्गोरिदम चलाएं।

एक साधारण उदाहरण: [5 3 6 2 4] औसत 0..3 के लिए औसत 5 है। (4 नहीं, क्योंकि हम मूल सूची के पहले तीन तत्वों के औसत से पूछ रहे हैं)

Answer 1

मुझे लगता है कि उप श्रेणियों की संख्या बढ़ने के साथ ही आपको बहुत जल्दी पता चल जाएगा कि यह क्रमबद्ध करने के लिए तेज़ है और फिर तत्व को पुनर्प्राप्त करें संख्या जो आप चाहते हैं।

प्रैक्टिस में, क्योंकि अत्यधिक अनुकूल सॉर्ट दिनचर्या आप कॉल कर सकते हैं।

सिद्धांत में, और शायद अभ्यास में भी, क्योंकि चूंकि आप पूर्णांक से निपट रहे हैं, आपको किसी प्रकार के लिए n लॉग n का भुगतान नहीं करना है - http://en.wikipedia.org/wiki/Integer_sorting देखें।

यदि आपका डेटा वास्तव में फ़्लोटिंग पॉइंट है और नाएन नहीं है तो वास्तव में थोड़ा सा twiddling वास्तव में आपको उन पर पूर्णांक प्रकार का उपयोग करने की अनुमति देगा - http://en.wikipedia.org/wiki/IEEE_754-1985#Comparing_floating-point_numbers - द्विआधारी प्रतिनिधित्व में विशेष संपत्ति है, NaNs को छोड़कर, किसी भी दो संख्याओं की तुलना संकेत और परिमाण पूर्णांक की तुलना में की जा सकती है (हालांकि आधुनिक कंप्यूटर प्रोसेसर के साथ यह अब सीधे लागू नहीं होता है): यदि साइन बिट अलग है, तो ऋणात्मक संख्या सकारात्मक संख्या से पहले होती है (सिवाय इसके कि ऋणात्मक शून्य और सकारात्मक शून्य बराबर माना जाना चाहिए) , अन्यथा, सापेक्ष आदेश लेक्सिकोोग्राफिक क्रम के समान है लेकिन दो नकारात्मक संख्याओं के लिए उलटा हुआ है; endianness मुद्दों लागू होते हैं।

तो आप नाएन और अन्य मज़ेदारों की जांच कर सकते हैं, फ़्लोटिंग पॉइंट नंबरों का संकेत करते हैं कि साइन + परिमाण पूर्णांक हैं, ऋणात्मक संख्याओं के क्रम में सही करने के लिए ऋणात्मक होने पर घटाना, और फिर सामान्य 2 एस पूरक हस्ताक्षर पूर्णांक, सॉर्ट, और फिर के रूप में व्यवहार करें प्रक्रिया को उलट दें।

Answer 2

पूर्णांक तत्व:

अपने तत्वों के प्रकार पूर्णांक हैं, तो सबसे अच्छा तरीका है प्रत्येक संख्या के लिए अपने उप पर्वतमाला है, जहां प्रत्येक बाल्टी गिनती के लिए प्रयोग किया जाता है में से किसी में निहित एक बाल्टी के लिए है आपके इनपुट तत्वों में इसके संबंधित पूर्णांक की संख्या (उदाहरण के लिए, bucket[100] स्टोर करता है कि आपके इनपुट अनुक्रम में कितने 100 एस हैं)। असल में आप इसे निम्न चरणों में प्राप्त कर सकते हैं:

1. प्रत्येक संख्या के लिए बाल्टी बनाएं आपकी उप-श्रेणियों में से किसी एक में है।
2. प्रत्येक संख्या n के लिए सभी तत्वों के माध्यम से पुनरावृत्त करें, यदि हमारे पास bucket[n] है, तो bucket[n]++।
3. अपनी बाल्टी में संग्रहीत समेकित मूल्यों के आधार पर मध्यस्थों की गणना करें।

इसे एक और तरीके से रखें, मान लीजिए कि आपके पास उप-श्रेणी [0, 10] है, और आप औसत गणना करना चाहते हैं। बाल्टी दृष्टिकोण मूल रूप से गणना करता है कि आपके इनपुट में कितने 0 एस हैं, और आपके इनपुट में कितने 1 एस हैं और इसी तरह। मान लीजिए n संख्या रेंज [0, 10] में झूठ है, तो मंझला n/2 वां सबसे बड़ा तत्व है, जो खोजने i ऐसी है कि या इसके बराबर bucket[0] + bucket[1] ... + bucket[i] अधिक से अधिक n/2 लेकिन bucket[0] + ... + bucket[i - 1]n/2 से कम है से पहचाना जा सकता है।

इस बारे में अच्छी बात यह है कि आपके इनपुट तत्व भी कई मशीनों (यानी वितरित मामले) में संग्रहीत होते हैं, प्रत्येक मशीन अपनी बाल्टी बनाए रख सकती है और इंट्रानेट से गुजरने के लिए केवल समेकित मूल्यों की आवश्यकता होती है।

आप पदानुक्रमित बाल्टी का भी उपयोग कर सकते हैं, जिसमें एकाधिक पास शामिल हैं। प्रत्येक पास में, bucket[i] आपके इनपुट में तत्वों की संख्या को एक विशिष्ट सीमा में निहित करता है (उदाहरण के लिए, [i * 2^K, (i+1) * 2^K]), और फिर प्रत्येक चरण के बाद मध्यम बाल्टी को पहचानने के द्वारा समस्या स्थान को सीमित कर दें, फिर K1 में घटाएं अगला कदम, और तब तक दोहराएं जब तक कि आप माध्यम को सही ढंग से पहचान सकें।

---

फ्लोटिंग प्वाइंट तत्व

पूरे तत्वों स्मृति में फिट कर सकते हैं:

अपने पूरे तत्वों स्मृति में फिट कर सकते हैं, पहले एन तत्व छँटाई और फिर खोजने माध्यिकाओं प्रत्येक उप श्रेणियों के लिए सबसे अच्छा विकल्प है। The linear time heap solution इस मामले में भी अच्छी तरह से काम करता है यदि आपकी उप-श्रेणियों की संख्या logN से कम है।

पूरे तत्वों स्मृति में फिट नहीं कर सकते, लेकिन एक ही मशीन में संग्रहीत:

आम तौर पर, एक external sort आम तौर पर तीन डिस्क स्कैन की आवश्यकता है। इसलिए, यदि आपकी उप-श्रेणियों की संख्या 3 से अधिक या बराबर है, तो पहले एन तत्वों को क्रमबद्ध करें और फिर डिस्क से आवश्यक तत्वों को लोड करके केवल प्रत्येक उप श्रेणियों के लिए औसत ढूंढना सर्वोत्तम विकल्प है। अन्यथा, बस प्रत्येक उप-श्रेणियों के लिए स्कैन करना और उप-श्रेणी में उन तत्वों को चुनना बेहतर है।

पूरे तत्वों कई मशीनों में जमा हो जाती है: मंझला खोजने के बाद से, एक समग्र ऑपरेटर है जिसका अर्थ है आप पूरे इनपुट के कई हिस्सों की माध्यिकाओं के आधार पर इनपुट के अंतिम मंझला प्राप्त नहीं सकता, यह एक कठिन समस्या है कि कोई भी कुछ वाक्यों में अपने समाधान का वर्णन नहीं कर सकता है, लेकिन शोध हैं (उदाहरण के रूप में this देखें) इस समस्या पर ध्यान केंद्रित किया गया है।

Answer 3

मेरा विचार:

• क्रमबद्ध एक सरणी में सूची (कोई भी उचित छंटाई कलन विधि का उपयोग)

• प्रत्येक श्रेणी के लिए, का उपयोग कर प्रारंभ और सीमा की समाप्ति के सूचकांकों को खोजने बाइनरी खोज

• केवल अपने सूचकांक जोड़कर और 2 से विभाजित करके औसत खोजें (यानीरेंज [x,y] की औसत arr[(x+y)/2])

Preprocessing समय आ गया है: O (n एक सामान्य छंटाई एल्गोरिथ्म के लिए एन) (जल्दी-तरह की तरह) या दिनचर्या चुना छँटाई

क्वेरी के साथ समय का चलने का समय लॉग ऑन : हे (लॉग एन)

गतिशील सूची:

ऊपर मानता है कि सूची स्थिर है। यदि तत्वों को क्वेरी के बीच स्वतंत्र रूप से जोड़ा या हटाया जा सकता है, तो एक संशोधित Binary Search Tree काम कर सकता है, प्रत्येक नोड के वंशजों की संख्या की गणना करते हुए। यह एक गतिशील सूची के साथ उपरोक्त के समान समय की अनुमति देगा।

Answer 4

उत्तर अंततः "निर्भर करता है" होने जा रहा है। कई प्रकार के दृष्टिकोण हैं, जिनमें से कोई भी शायद आप जिन मामलों का सामना कर सकते हैं, उनमें से कोई भी उपयुक्त होगा। समस्या यह है कि प्रत्येक अलग-अलग इनपुट के लिए अलग-अलग प्रदर्शन करने जा रहा है। जहां एक इनपुट के एक वर्ग के लिए बेहतर प्रदर्शन कर सकता है, कोई अन्य इनपुट के विभिन्न वर्गों के लिए बेहतर प्रदर्शन करेगा।

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

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