Вычислите взвешенные средние для больших количеств
Я пытаюсь получить взвешенное среднее нескольких чисел. В основном я имею:
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;
Проблема, я очень быстро истратил "прокручивающуюся" переменную.
Как я могу на самом деле получить свое взвешенное среднее?
7 ответов
Двойка может хранить довольно большое число (около 1.7 x 10^308, согласно документации), но вам, вероятно, не следует использовать ее для значений, где требуется точная точность (таких как денежные значения).
Обратите внимание на класс BigDecimal. Этот вопрос на SO рассказывает об этом более подробно.
Одно из решений - использовать java.math.BigInteger как для прокрутки , так и totalQuantity , и разделять их только на конец. Это обеспечивает лучшую числовую стабильность, поскольку у вас есть только одно деление с плавающей запятой в конце, а все остальное - целочисленные операции.
BigInteger в основном неограничен, поэтому вы не должны сталкиваться с какими-либо переполнениями.
РЕДАКТИРОВАТЬ: Извините, только перечитав, я заметил, что ваша цена в любом случае равна вдвое . Возможно, стоит обойти это, умножив его на 100, а затем преобразовав в BigInteger - поскольку я вижу в вашем примере, он имеет ровно 2 цифры справа от десятичной точки - а затем разделите его на 100 в конце, хотя это что-то вроде взлома.
Ваш конечный результат - это просто средневзвешенное значение точности, поэтому, предположительно, вам не нужно следовать правилам, используемым при вычислении остатков на счетах и т.д. Если я прав, то вам не нужно использовать 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. ОП усредняет положительные числа, поэтому ошибки отмены не будет. Сторонники арифметики произвольной точности не говорят вам, что, если оставить в стороне правила округления, в тех случаях, когда она дает большую дополнительную точность по сравнению с арифметикой с плавающей запятой IEEE754, это будет сопровождаться значительными затратами памяти и производительности. Арифметика с плавающей запятой была разработана очень умными людьми (профессор Кахан, среди прочих), и если бы существовал способ дешево увеличить точность арифметики по сравнению с тем, что предлагает плавающая запятая, они бы сделали это.
Оговорка: если ваши веса совершенно сумасшедшие (один равен 1, другой 10000000), то я не уверен на 100%, что вы получите удовлетворительную точность, но вы можете проверить это на каком-нибудь примере, когда вы знаете, каким должен быть ответ.
Во-первых, я не понимаю, как можно «максимально увеличить» скользящую переменную. Как указывает @Ash, он может представлять значения примерно до 1,7 x 10 ^ 308 . Единственная возможность, о которой я могу думать, - это то, что у вас есть неправильные значения во входных данных. (Возможно, настоящая проблема в том, что вы теряете точность ...)
Во-вторых, использование вами Карты для представления приказов странно и, вероятно, не работает. В том виде, в котором вы его используете в настоящее время, вы не можете представлять заказы, включающие два или более товаров с одинаковой ценой.
Выполните два цикла: сначала вычислите totalQuantity в первом цикле. Затем во втором цикле накапливается цена * (количество / totalQuantity).
Для максимальной гибкости используйте BigDecimal для rolling, и BigInteger для totalQuantity. После деления (обратите внимание, у вас все наоборот; должно быть rolling / totalQuantity), вы можете либо вернуть BigDecimal, либо использовать doubleValue с потерей точности.
В любой момент вы записали как общее значение 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 каким-то образом было кратным многим числам.