大數的計算加權平均數

我試圖獲得幾個數字的加權平均數。基本上我有：大數的計算加權平均數

Price - 134.42 
Quantity - 15236545

可以有少至一個或兩個或多達五60對價格和數量。我需要弄清楚價格的加權平均值。基本上，加權平均值應該給予非常小的權重，如

Price - 100000000.00 
Quantity - 3

和更多的對上面。

我現在有計算公式爲：

((price)(quantity) + (price)(quantity) + ...)/totalQuantity

到目前爲止，我有這個工作：

 double optimalPrice = 0; 
     int totalQuantity = 0; 
     double rolling = 0; 
     System.out.println(rolling); 

     Iterator it = orders.entrySet().iterator(); 
     while(it.hasNext()) { 
      System.out.println("inside"); 
      Map.Entry order = (Map.Entry)it.next(); 
      double price = (Double)order.getKey(); 
      int quantity = (Integer)order.getValue(); 
      System.out.println(price + " " + quantity); 

      rolling += price * quantity; 
      totalQuantity += quantity; 
      System.out.println(rolling); 
     } 
     System.out.println(rolling); 
     return rolling/totalQuantity;

問題是，我很快就最大程度的發揮「滾動」變量。

我怎樣才能真正得到我的加權平均值？

來源

2010-05-30 Travis

一種解決方案是對rolling和totalQuantity都使用java.math.BigInteger，並且只在最後將它們分開。這有一個更好的數字穩定性，因爲你最終只有一個浮點除法，而其他所有操作都是整數運算。

BigInteger基本上是無界的，所以你不應該遇到任何溢出。

編輯：對不起，只有重新閱讀我已經注意到你的價格是double無論如何。也許有必要通過將它乘以100然後轉換爲BigInteger來避開這個問題 - 因爲我在你的例子中看到它有小數點右邊的2位數 - 然後在最後除以100，雖然這有點破解。

來源

2010-05-30 07:07:38 Oak

'1.055' - >'105'，您應該在乘以100之前，但在整數轉換之前加上'0.005'，然後再乘以100， ' - >'106'，這是正確的四捨五入。 – Pindatjuh 2010-05-30 11:45:11

@Pindatjuh：這個想法不會失去任何精度。我建議乘以100，因爲它看起來像OP的價格恰好在該點後兩位數，而不是更多。 – Oak 2010-05-30 12:03:30

當然，但這不是批評你的出色建議（+1），只是在使用乘以100並轉換爲整數的「黑客」時更好的四捨五入的註釋，如果超過2數字。 – Pindatjuh 2010-05-30 14:00:13

double可以保存相當大的數字（根據文檔大小約爲1.7 x 10^308），但是您可能不應該將它用於需要精確精確度的值（例如貨幣值）。

請查看BigDecimal類。 This question on SO更詳細地談論它。

來源

2010-05-30 07:09:24 Ash

爲了獲得最大的靈活性，請使用BigDecimal代替rolling和BigInteger代替totalQuantity。分割之後（注意，它有倒退;它應該是滾動/ totalQuantity），您可以返回一個BigDecimal，或使用doubleValue以精確度損失。

來源

2010-05-30 07:14:05

在任何給定的點上，您都記錄了總價值ax + by + cz + ... = pq和總重量a + b + c + ... = p。知道兩者然後給你的平均值pq/p = q。問題是pq和p是溢出的大數目，即使您只是想要中等大小的q。

下一步將增加例如r的權重和值s。您想通過僅使用q的值來找到新金額(pq + rs)/(p + r)，這隻有在p和pq以某種方式通過在相同分數的分子和分母中「消滅」纔會發生。正如我所表明的那樣，這是不可能的。

，你需要在這個迭代中添加的價值，自然就

(pq + rs)/(p + r) - q

不能被簡化到一個地步，p*q和p消失。您還可以找到

(pq + rs)/q(p + r)

您乘以q以獲得下一個平均值的因子;但仍然存在pq和p。所以沒有巧妙的解決方案。

其他人提到了任意精度變量，這是一個很好的解決方案。 p和pq的大小隨條目數量線性增長，整數/浮點的內存使用率和計算速度隨着值的大小呈對數增長。因此，性能是O（log（n）），不像災難那樣，如果p在某種程度上是許多數字的倍數。

來源

2010-05-30 07:44:49

首先，我沒有看到你怎麼能「變出」rolling變量。正如@Ash指出的那樣，它可以代表高達約1.7 x 10^308的值。我能想到的唯一可能性是你在輸入中有一些不好的值。（也許真正的問題是，你正在失去精確度...）

其次，您使用Map來表示訂單是很奇怪的，可能是壞的。您目前使用它的方式，不能以相同的價格表示涉及兩個或更多項目的訂單。

來源

2010-05-30 07:46:07

是的，爲什麼不把訂單存儲在列表中？ – 2010-05-30 08:47:05

該程序的前一部分將相同價格的訂單組合在一起。 – Travis 2010-05-30 15:29:05

您的最終結果只是精確度的加權平均值，因此您可能無需遵循計算帳戶餘額時使用的規則等。如果我對上述內容正確，則無需使用BigDecimal,double就足夠了。

溢出問題可以通過存儲「運行平均值」並使用每個新條目更新來解決。即，讓

A_N =（sum_ {I = 1}^N X_I * w_i）/（sum_ {I = 1}^N w_i）

對於n = 1，...，N。您開始與A_N = x_n然後添加

D_N：= A_ {N + 1} - A_N

到它。對於D_N式是

D_N =（X_ {N + 1} - W_ {N + 1} * A_N）/ W_ {N + 1}

其中W_n：= sum_ {I = 1}^n w_n。你需要跟蹤W_n，但是這個問題可以通過將其存儲爲double來解決（因爲我們只對平均值感興趣，所以這個問題會好起來的）。您還可以對權重進行歸一化，如果您知道所有權重都是1000的倍數，只需將它們除以1000即可。

要獲得更高的準確性，您可以使用compensated summation。

搶先說明：這裏可以使用浮點運算。 double的相對精度爲2E-16。OP正在平均正數，所以不會有取消錯誤。什麼是任意精度算術的支持者沒有告訴你的是，拋開舍入規則，在確實爲提供了很多IEEE754浮點運算的附加精度的情況下，這會帶來顯着的內存和性能成本。浮點算法是由非常聰明的人（Kahan教授等人）設計的，如果存在一種便宜地增加浮點提供的算術精度的方法，他們會這樣做。免責聲明：如果你的權重完全瘋狂（一個是1，另一個是10000000），那麼我不是100％確定你是否會得到滿意的準確性，但你可以在某些例子中測試它，當你知道答案時應該。

來源

2010-05-30 08:46:13

您仍然有W_n隨（數量，價格）對的數量增加的問題。但這最多不得超過60對。 – 2010-05-31 19:28:26

那麼它可能不會溢出'double'。 – 2010-06-01 08:14:40

做兩個循環：首先在第一個循環中計算totalQuantity。然後在第二個循環中累計價格*（數量/總數量）。

來源

2010-05-30 11:04:14

然後OP可能會有下溢而不是溢出。 – 2010-05-30 20:00:57

大數的計算加權平均數

回答

相關問題