6

我试图得到几个数字的加权平均值。基本上我有：

Price    - 134.42
Quantity - 15236545

价格和数量少则一两对，多则五十或六十对。我需要计算出价格的加权平均值。基本上，加权平均值应该对像这样的配对给予很小的权重

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;

问题是我很快将“滚动”变量最大化。

我怎样才能真正得到我的加权平均值？

4

7 回答 7

3

一种解决方案是同时使用java.math.BigIntegerand rolling，totalQuantity并且只在最后将它们分开。这具有更好的数值稳定性，因为最后只有一个浮点除法，其他一切都是整数运算。

BigInteger基本上是无界的，所以你不应该遇到任何溢出。

编辑：对不起，只有在重新阅读时我才注意到你的价格是double无论如何。也许值得通过将其乘以 100 然后转换为来规避这一点BigInteger- 因为我在你的示例中看到它正好有小数点右边的 2 位数字 - 然后在最后除以 100，尽管它有点像黑客。

于 2010-05-30T07:07:38.363 回答
3

double 可以容纳一个相当大的数字（根据文档，大约为 1.7 x 10^308），但您可能不应该将它用于需要精确精度的值（例如货币值）。

请查看BigDecimal类。SO上的这个问题更详细地讨论了它。

于 2010-05-30T07:09:24.373 回答
1

为了获得最大的灵活性，请使用BigDecimalforrolling和BigIntegerfor totalQuantity。划分后（注意，你有它向后；它应该是滚动/总数量），你可以返回一个 BigDecimal，或者doubleValue在精度损失的情况下使用。

于 2010-05-30T07:14:05.797 回答
0

在任何给定点，您都记录了总值ax + by + cz + ... = pq 和总重量a + b + c + ... = p。知道两者然后给你平均值pq/p = q。问题是pq和p是溢出的大数目，即使您只想要中等大小的q.

例如，下一步添加权重r和值s。您想(pq + rs) / (p + r)通过仅使用 的值来找到新的总和q，这只有在以某种方式通过位于同一分数的分子和分母中“湮灭”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-30T07:44:49.950 回答
0

首先，我看不出你如何“最大化”这个rolling变量。正如@Ash 指出的那样，它可以表示高达 about 的值1.7 x 10^308。我能想到的唯一可能性是您的输入中有一些错误的值。（也许真正的问题是你正在失去精度......）

其次，您使用Mapas 来表示订单很奇怪，并且可能已损坏。您当前使用它的方式，您不能代表涉及具有相同价格的两个或多个项目的订单。

于 2010-05-30T07:46:07.437 回答
0

您的最终结果只是精确度的加权平均值，因此大概您不需要遵循计算账户余额等时使用的规则。如果我对上述内容正确，那么您不需要使用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。

要获得更高的准确性，您可以使用补偿求和。

先发制人的解释：这里可以使用浮点运算。double具有2E-16的相对精度。OP 对正数进行平均，因此不会出现取消错误。任意精度算术的支持者没有告诉您的是，抛开舍入规则，在它确实为您提供比 IEEE754 浮点算术更高的精度的情况下，这将带来显着的内存和性能成本。浮点运算是由非常聪明的人（Kahan 教授等）设计的，如果有一种方法可以廉价地提高浮点运算的运算精度，他们就会这样做。

免责声明：如果您的权重完全疯狂（一个是 1，另一个是 10000000），那么我不能 100% 确定您是否会获得令人满意的准确性，但是当您知道答案应该是什么时，您可以通过一些示例对其进行测试。

于 2010-05-30T08:46:13.803 回答
0

做两个循环：在第一个循环中首先计算 totalQuantity。然后在第二个循环中累积价格 *（数量/总数量）。

于 2010-05-30T11:04:14.377 回答