如何高效地計算 2 億多個 0 到 INT_MAX 隨機數的平均值？

我想的是，每1000個求一次平均數，把求得的平均數放在另一個文件中，這樣問題的數據就變小了，遞歸多次，平均數就求出來了。求平均數不能有溢出，所以我用減法求平均數。

---

如INT_MAX是2^31-1，2億大約是2^27.6，2億個INT_MAX之和也僅是2^58.6。

用64位整數計算和，再轉換成double計算除數。這樣除數會有一些精度損失，可改用long double（有些平台是80位，這樣有63位mantissa），或使用128位的浮點數除法實現。

如果個數剛好是2的冪，就能完全精確地把那個和以定點數表示平均數。

上述的做法都是O(n)，一般64位平台上性能不做成問題，而且較使用浮點數「穩定」（這裡指結果不受數據次序影響）。

---

用MPI並行處理啊，so easy

---

cuda

---

如果禁止使用所有其他數據類型的話，建議

每個數減去INT_MAX/2;

從小到大排序；

交替求和；（最小的數加上最大的數，結果為正就加次小的數，結果為負就加上次最大的數...）

求平均值；

平均值+INT_MAX/2

--------------提升性能的方法--------------

不必嚴格排序， 只需要把正數和負數分開就可以了，相當於QuickSort的第一次迭代。複雜度為O(n)。

求和不找最小和最大。 和為正就不斷加負數，和為負就不斷加正數。

---

能單機處理當然就單機處理啦~

但是你的label有個海量數據處理，所以我就說說map-reduce想法啦。

其實很簡單啦

mapper:計算輸入值得均值

reducer:把map傳過來的值求和除以台數

很簡單吧~

私以為既然追求效率就不要用單機做啦~

---

其實按照概率分布來算，你取這麼多的隨機數，已經很非常穩定了，可以大膽的告訴你答案就是INX_MAX/2。

---

前n個數平均值為a，第n+1個數為p

則前n+1個數平均值為a/(n+1)*n + p/(n+1)

---

大家都說的是暴力解法。這裡提供一個巧妙一點的思路，就是利用Central Limit Theorem.

Central Limit Theorem是說，多個從同一分布P中獨立抽取的隨機變數的平均數，在數量增加時，趨近於正態分布。樣本數為n時，平均值趨近於P的平均值，方差趨近。

可以首先隨機抽取一千個數字，估計一下方差，然後根據你要的精度，計算一個n。然後隨機抽取n個樣本取平均數即可。不過如果方差巨大的話，這個方法可能不好使。

順便說一句，暴力解法可就不能排序了。直接做一個大的數據類型做n次加法就好。任何一個小常數擴大兩億倍也是很嚇人的。

---

c/c++不是自帶有64位整形long long嗎...不能直接用嗎...如果不讓用就自己寫個大整數類

---

簡單問題就用簡單方法。

2億多個32位整數佔據空間也就800~1200M位元組左右吧，全部放在一台機器內存，根據CPU數量劃分若干組，每組用一個線程求和到各自的64位整數變數中(VC上是unsigned __int64，GCC是unsigned long long int)，所有線程計算完畢後，計算總和，轉成double計算平均值。

海量數據可以用彙編指令ADD和ADC實現高精度的整數加法，SSE/MMX指令集自帶128位整數運算指令，AVX2上有256位運算指令了，將數據劃分到n個磁碟上即可。

---

既然是隨機數直接取中值就好了...

---

用unsigned int s[10]={0}存每位數的和：32位數化成10進位數最多10位數，每位最大為9，2億多1位的10進位數相加不會越界；然後都除以總共的個數，再乘以對應當10進位位權值。

avg(n) = sum(s[i]*10^i)/n, i from 0 to 9; ==&>

avg(n) = sum(s[i]/n*10^i), i from 0 to 9.

---

數據量過大,數據處理需要先分組了.先求與INT_MAX/2的差值,然後分組求平均值.每個組個數不超過65535個(非均勻分布不會越界),然後各組之間求平均值.每組內求和可以用32位變數,這樣處理的會稍快一些.我記得好像是對32位計算有優化的,這個你可以跟做CPU架構的確認一下.

每組間求平均數記得換成Double.按照你說的量不會超過65535組,用Double也可以了.

---

v[k]=v[k-1] - （v[k-1] - i[k]）/k

剛用java寫了個測試了下。結果是按這種演算法計算2億個數的平均值大約需要2秒，讀文件應該沒這麼快吧。我的測試是計算2147483646個隨機整數(&>=0)，比題主的2億要多10倍，總耗時116秒左右，然後不計算，只算隨機數，總耗時94秒左右，兩者相減為22秒，而計算的次數為21億，因此在我機器上計算一億個平均數約需1秒。計算的精度相當可觀，結果是1.0737436273706791E9，而直接用最大數除以2的結果是1073741823。

測試代碼如下，其中語句(1)耗時是(2)的4+倍，因此我會單獨測(1)的總耗時：

long start = System.currentTimeMillis();
double avg = 0.0;
Random rand = new Random();
int v = 0;
for (int i=1; i&

你可以開2個大小為1k的緩衝區。

sometype buf[2][20000]

讀進來的數先試圖填充buf[0]，然後當buf[0]滿了之後就求和然後推到buf[1]。。

至於sometype就取決於你最後所需要的精度了。。

---

double getAvarage(const int[] numbers, int count) {
if (numbers == NULL || count &<= 0) return 0d; long long sum = 0; for (int i = 0; i&

---

2億 = 2* 10^8，

然後把數據分為前後兩部分，每部分一億個數據。

1.每10個數據一組，算平均值，要高效的話，避免除法，用INT_MAX/2做減法，申請一個long的變數存儲跟INT_MAX/2的差值。

2.把這個差值作為新的輸入，就有一千萬個差值。

3.這些差值的期望是0，所以按照1的思路，10個差值一組，繼續，直到遞歸結束，得出一個差值X。

4.同理後半部分可以得出Y。

最後，結果 avg = （INT_MAX/2） + （X+Y）/2億

時間複雜度 2*lg（一億）

---

數據這麼大，上hoeffding"s bounds吧, 又快又好用

---

一個個加，然後判斷是否溢出。並計算溢出的總次數。

通過這個方法，可以得到總和，然後再求平均。

---

我又想到一種方法，每次2000數字求一次平均數，平均數帶小數點0.5，則把這個平均數放在文件A中，平均數不帶小數點則放在文件B中，這樣分別對兩個文件中的文件數平均數，這要遞歸下去，最後再歸併回來求平均數，就可以保證求的的平均數沒有誤差。

---

推薦閱讀：