更好的算法來找到平均值

我正在做一個編程書的練習關於C的書。演習表明，找到一組數字的平均值算法：更好的算法來找到平均值

avg += (x - avg)/i;

優於：

sum += x; 
avg = sum/i;

「X」是用來存儲輸入數字的變量。它還表明，除了防止溢出之外，第一種算法還有其他優點，比第二種算法更好，任何人都可以幫助我嗎？謝謝！

來源

2011-06-03 Oliver

heh。我碰巧在我的辦公桌上有這本書的第一版。這是什麼章節？ – 2011-06-03 13:29:08

第一章練習17. – Oliver 2011-06-03 13:31:13

counter-argument ---忽略溢出的第二種方法是（可能）[更快（對於數十億次操作）]（http://ideone.com/5kHKK），因爲只有1個分區是執行:) – pmg 2011-06-03 13:37:22

從某種意義上說，它計算一個連續的平均值就是更好，也就是說，你不需要提前獲得所有的數字。你可以隨時計算，或者隨着數字的變化。

來源

2011-06-03 13:20:58 mbatchkarov

你可以計算每個遞增的平均值，而不是O（N） – pepsi 2011-06-03 13:31:22

謝謝！它說：「在這個練習中，你要繼續你做的工作在前面的練習中，如果運行better_average程序從包含一些普通數字的文件輸入數據，那麼第一個算法和第二個算法似乎會產生相同的答案，發現情況並非如此。，通過實驗證明，即使總和沒有溢出，更好的平均值也會更好。「你能告訴我哪種情況會發生嗎？ – Oliver 2011-06-03 13:33:04

-1：它們都能夠計算runni平均水平。 – 2011-06-03 13:41:15

sum += x; 
avg = sum/i;

在上面的代碼中，假設我們有一個數字爲10000,20000，...那是含有大量的位數，然後在和值可能超過其MAX值，這是不I'st一個視情況數總和在存儲之前總是被沒有元素所分割。

雖然因爲在編程語言存在大量的數據類型，這可能不是一個problem.Thus的

專家說什麼「使用數據類型，按您的應用和需求。」

來源

2011-06-03 13:25:56 Algorithmist

OP說「旁邊防止溢出」 – pepsi 2011-06-03 13:30:02

後一種算法比前者快，因爲你必須執行n個操作（實際上，後者需要執行2 * n個操作）。但第一個防止溢出是事實。例如，如果您有這一組1000個數字：4000000 * 250，1500000 * 500，2000000 * 500，則所有整數的總和將是2'750.000.000，但C++ int數據類型的上限是2,147,483,647。所以，我們在這種情況下處理溢出問題。但是如果你執行第一個算法，那麼你就可以處理這個問題。

所以我建議你使用第一種算法，如果它很可能發生溢出，否則它只會增加額外的操作。如果您決定首先使用第一個，那麼我建議您使用更大範圍的類型。

來源

2011-06-03 13:39:02

很可能，這將是浮點運算。所以溢出考慮通常是不相關的。 – 2011-06-03 13:44:02

其實，這是真的 – 2011-06-03 13:44:49

我假設我們在這裏談論浮點運算（否則「更好」的平均值將會很糟糕）。

在第二種方法中，中間結果（sum）將傾向於無限制地增長，這意味着您最終將失去低端精度。在第一種方法中，中間結果應保持與輸入數據大致相似的量級（假設您的輸入沒有巨大的動態範圍）。這意味着它會更好地保持精度。

然而，我可以想像，作爲i變得越來越大，中(x - avg)/i價值將得到越來越少準確的（相對）。所以它也有它的缺點。

來源

2011-06-03 13:39:08

+1請你解釋一下「失去低端精度」，並且我們必須使用哪一個。 – Algorithmist 2011-06-03 13:43:19

@算法：考慮浮點表示的結構; a *尾數*和*指數*。尾數表示精度，即有效數字，並且有固定的數字。隨着數字變大，指數將開始增加，這意味着您的有效數字開始遠離二進制點。 – 2011-06-03 13:45:58

就像我看到的那樣，'（x-avg）/ i'的問題只是部分由'i'變大引起的。如果許多數字接近平均值，那麼'（x-avg）'部分本身也是個問題，因爲減去附近的浮點數會失去精度。 – 2011-06-04 06:29:04

我更喜歡第二種方法（總結一個循環並在最後分割），並且可以比第一種更快地識別第二種方法。

性能差異如果有的話是無關緊要的。

而且，如果一個值的總和溢出了一個足夠大的數據類型，那麼與計算平均值相比，您可能會遇到更多的問題。

來源

2011-06-03 13:47:34 pmg

數字差異可能是相關的。正是這種考慮導致了Kahan求和算法和類似的問題。 – 2011-06-03 13:51:33

+1 Oli：只要確保它明確說明 - sum方法之後的除法更可靠（禁止溢出） – pmg 2011-06-03 14:00:58

好吧，答案不在於溢出總和（因爲這被排除），但正如奧利在「失去低端精度」中所說的那樣。如果你正在求和的數字的平均值遠大於每個數字與平均值的距離，那麼第二種方法將失去尾數位。由於第一種方法只考慮相對值，因此不會遇到這個問題。

因此，任何大於6000萬（對於單精度浮點）數值列表，但值不會超過10個左右的變化應該會顯示您的行爲。

如果您使用雙精度浮點數，平均值應該更高。或者三角洲低得多。

來源

2011-06-03 15:33:39

請注意這一點：小心您的值可以用您選擇的精度表示。然後在列表中包含足夠的值。 – 2011-06-03 15:41:12

-3

如何計算這樣的，假設是整數數組中的？：

sum += x[i]/N; rem += x[i] % N; 
avg = sum + rem/N;

如果N很大（的0xFFFFF）和x[i]都小，因此rem加起來到0xFFFF（最大INT），然後溢出可能發生。

來源

2012-10-22 23:47:50 eye

更好的算法來找到平均值

回答

相關問題