अधिकतम मेमोरी दक्षता के साथ वृद्धिशील औसत गणना

Question

मेरे पास एक प्रक्रिया है जो मान उत्पन्न करती है और जो मैं देखता हूं। जब प्रक्रिया समाप्त हो जाती है, तो मैं उन मानों के औसत की गणना करना चाहता हूं।

यदि मुझे माध्य की गणना करना पड़ा, तो मैं केवल योग और जेनरेट किए गए मानों की संख्या संग्रहीत कर सकता था और इस प्रकार ओ (1) स्मृति आवश्यकता होती है। औसत के बारे में कैसे? क्या सभी ओ मूल्यों को संग्रहित करने से आने वाले स्पष्ट ओ (एन) को सहेजने का कोई तरीका है?

संपादित करें: 2 मामलों में रूचि: 1) धारा की लंबाई ज्ञात है, 2) यह नहीं है।

Answer 1

आप, कम से कम प्लस्तर लगाना (एन/2) अंक संग्रहीत करने की आवश्यकता करने जा रहे हैं क्योंकि पहली n/2 अंक में से किसी एक मंझला हो सकता है। बस अंक को स्टोर करने और औसत खोजने के लिए शायद सबसे आसान है। यदि बचत छत (एन/2) बिंदु मूल्य का है, तो पहले एन/2 बिंदुओं में एक क्रमबद्ध सूची में पढ़ें (एक बाइनरी पेड़ शायद सबसे अच्छा है), फिर नए बिंदु जोड़े गए हैं जो कम या उच्च बिंदुओं को फेंकते हैं और रखें किसी भी अंत में बाहर फेंकने पर अंक की संख्या का ट्रैक।

संपादित करें: धारा लंबाई तो स्पष्ट रूप से अज्ञात है

हैं, के रूप में स्टीफन टिप्पणी में मनाया, तो हम लेकिन सब कुछ याद करने के लिए कोई विकल्प नहीं है। यदि डुप्लिकेट आइटम की संभावना है, तो हम मूल्यों और गणनाओं को संग्रहीत करने के डॉल्फ़िन विचार का उपयोग करके संभवतः कुछ स्मृति को सहेज सकते हैं।

Answer 2

आप

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

Answer 3

यदि आपके पास अलग-अलग मूल्य हैं और पुनरावृत्ति के बहुत सारे हैं तो आप मूल्यों और गणनाओं को स्टोर कर सकते हैं, जो कुछ जगह बचाएंगे।

गणना के माध्यम से संभवतः गणना के माध्यम से आप शीर्ष 'एन' और नीचे 'एन' मानों को त्याग सकते हैं, जब तक आप सुनिश्चित हों कि औसत उस शीर्ष या निचली सीमा में नहीं है।
उदा। मान लीजिए कि आप 100,000 मूल्यों की उम्मीद कर रहे हैं। हर बार जब आपका संग्रहित नंबर 12,000 (कहता है) 12,000 हो जाता है तो आप अधिकतम 1000 और निम्नतम 1000 को छोड़ सकते हैं, भंडारण को 10,000 तक छोड़ सकते हैं।

यदि मूल्यों का वितरण काफी सुसंगत है, तो यह अच्छी तरह से काम करेगा। हालांकि अगर कोई संभावना है कि आपको अंत में बहुत अधिक या बहुत कम मूल्य मिलेगा, तो यह आपके गणना को विकृत कर सकता है। असल में यदि आप "उच्च" मान को छोड़ देते हैं जो (अंतिम) औसत या "कम" मान से कम है जो (अंतिम) औसत से बराबर या उससे अधिक है तो आपकी गणना बंद है।

अद्यतन
एक उदाहरण के बिट
मान लें कि डेटा सेट संख्या 1,2,3,4,5,6,7,8,9 में है।
निरीक्षण द्वारा औसत 5 है।

मान लें कि आपको प्राप्त होने वाले पहले 5 नंबर 1,3,5,7,9 हैं।
अंतरिक्ष को बचाने के लिए हम उच्चतम और निम्नतम को छोड़कर, 3,5,7
छोड़कर अब दो और 2,6 प्राप्त करें, इसलिए हमारा संग्रहण 2,3,5,6,7
उच्चतम और निम्नतम छोड़कर छोड़ें 3,5,6
अंतिम दो 4,8 प्राप्त करें और हमारे पास 3,4,5,6,8
मेडियन अभी भी 5 है और दुनिया एक अच्छी जगह है।

हालांकि, कहते हैं की सुविधा देता है कि पहले पांच नंबर पर हम पाते हैं 1,2,3,4,5
त्यागें ऊपर और नीचे छोड़ने 2,3,4
दो और 6.7 प्राप्त हैं और हम 2 है, 3,4,6,7
शीर्ष और नीचे छोड़कर 3,4,6
पिछले दो 8,9 प्राप्त करें और हमारे पास 3,4,6,8,9
6 के औसत के साथ गलत है।

यदि हमारी संख्या अच्छी तरह से वितरित की जाती है, तो हम चरम सीमा को कम रख सकते हैं। अगर उन्हें बहुत बड़ी या बहुत छोटी संख्या में जोड़ा जा सकता है, तो छोड़ना खतरनाक है।