क्या अंक()/एन से अंकगणितीय माध्य "बेहतर" खोजने का कोई तरीका है?

Question

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

def simple_mean(array[N]): # pseudocode 
    sum = 0 
    for i = 1 to N 
     sum += array[i] 
    return sum/N 

यह ठीक काम करता है, लेकिन बड़ी पूर्णांकों की आवश्यकता है। यदि हम बड़े पूर्णांक नहीं चाहते हैं और हम गोल करने वाली त्रुटियों के साथ ठीक हैं, और एन दो की शक्ति है, तो हम 'divide-and-conquer' का उपयोग कर सकते हैं: ((a+b)/2 + (c+d)/2)/2 = (a+b+c+d)/4, ((a+b+c+d)/4 + (e+f+g+h)/4)/2 = (a+b+c+d+e+f+g+h)/8, आदि।

def bisection_average(array[N]): 
    if N == 1: return array[1] 
    return (bisection_average(array[:N/2])+bisection_average(array[N/2:]))/2 

कोई अन्य तरीका?

पीएस। playground for lazy

Answer 1

बड़ा पूर्णांक समस्या हैं ... यह ठीक

a/N + b/N+.... n/N 

मेरा मतलब है तुम सिर्फ अन्य तरीकों या इष्टतम तरीका ढूंढ रहे हैं क्या है?

Answer 2

यदि आप float का उपयोग आप बड़े पूर्णांकों से बचने के सकता है:

def simple_mean(array[N]): 
    sum = 0.0 # <--- 
    for i = 1 to N 
     sum += array[i] 
    return sum/N 

Answer 3

नुथ फ्लोटिंग बिंदु (मूल पी पर Vol 2 of The Art of Computer Programming के 232, 1998 संस्करण दिए गए माध्य और मानक विचलन की गणना के लिए सूचीबद्ध करता है निम्न विधि; नीचे मेरी अनुकूलन। से बचा जाता है विशेष आवरण पहले यात्रा):

double M=0, S=0; 

for (int i = 0; i < N; ++i) 
{ 
    double Mprev = M; 
    M += (x[i] - M)/(i+1); 
    S += (x[i] - M)*(x[i] - Mprev); 
} 

// mean = M 
// std dev = sqrt(S/N) or sqrt(S/N+1) 
// depending on whether you want population or sample std dev 

Answer 4

यहाँ त्रुटियों गोलाई और बड़े मध्यवर्ती मूल्यों से परहेज बिना सिर्फ पूर्णांकों का उपयोग कर मतलब गणना करने के लिए एक तरीका है:

sum = 0 
rest = 0 
for num in numbers: 
    sum += num/N 
    rest += num % N 
    sum += rest/N 
    rest = rest % N 

return sum, rest 

Answer 5

यदि सरणी फ़्लोटिंग-पॉइंट डेटा है, तो "सरल" एल्गोरिदम भी गोल त्रुटि से पीड़ित है। दिलचस्प बात यह है कि, उस मामले में, वर्ग वर्ग (एन) की वर्ग वर्ग (एन) की गणना में गणना को अवरुद्ध करना वास्तव में औसत मामले में त्रुटि को कम करता है (भले ही फ़्लोटिंग-पॉइंट राउंडिंग की संख्या समान हो)।

पूर्णांक डेटा के लिए, ध्यान दें कि आपको सामान्य "बड़े पूर्णांक" की आवश्यकता नहीं है; यदि आपके सरणी (संभवतः) में 4 बिलियन से कम तत्व हैं, तो आपको सरणी डेटा के प्रकार की तुलना में केवल एक पूर्णांक प्रकार 32 बिट्स की आवश्यकता होती है। इस थोड़ा बड़े प्रकार पर अतिरिक्त प्रदर्शन करना हमेशा प्रकार पर विभाजन या मॉड्यूलस करने से काफी तेज होगा। उदाहरण के लिए, अधिकांश 32 बिट सिस्टम पर, 64-बिट अतिरिक्त 32-बिट विभाजन/मॉड्यूलस से तेज़ है। यह प्रभाव केवल अधिक अतिरंजित हो जाएगा क्योंकि प्रकार बड़े हो जाते हैं। O(n) - -

Answer 6

Kahan algorithm (विकिपीडिया के अनुसार) बेहतर क्रम प्रदर्शन (जोड़ो में योग की तुलना में) है और एक O(1) त्रुटि विकास:

function KahanSum(input) 
    var sum = 0.0 
    var c = 0.0     // A running compensation for lost low-order bits. 
    for i = 1 to input.length do 
     var y = input[i] - c  // So far, so good: c is zero. 
     var t = sum + y   // Alas, sum is big, y small, so low-order digits of y are lost. 
     c = (t - sum) - y // (t - sum) recovers the high-order part of y; subtracting y recovers -(low part of y) 
     sum = t   // Algebraically, c should always be zero. Beware overly-aggressive optimizing compilers! 
     // Next time around, the lost low part will be added to y in a fresh attempt. 
    return sum 

इसका विचार यह है कि चल बिन्दु संख्या के कम बिट्स मुख्य सारांश से स्वतंत्र रूप से संक्षेप में और सही किया जाता है।