大数的计算加权平均数

我试图获得几个数字的加权平均数。基本上我有：大数的计算加权平均数

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

大数的计算加权平均数

回答

相关问题