Вычислить средневзвешенные значения для больших чисел

Question

Я пытаюсь получить средневзвешенное значение для нескольких чисел.В основном у меня есть:

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;

Проблема в том, что я очень быстро максимизирую "прокатку"переменная.

Как я могу получить средневзвешенное значение?

Answer 1

Двойное число может содержать довольно большое число (около 1,7 x 10 ^ 308, согласно документам), но вам, вероятно, не следует использовать его для значений, где требуется точная точность (например, денежные значения).

Взамен BigDecimal класс. Этот вопрос о SO говорит о нем более подробно.

Answer 2

Одним из решений является использование java.math.BigInteger для rolling и totalQuantity, и только делите их в конце. Это обеспечивает лучшую числовую стабильность, поскольку в конце у вас только одно деление с плавающей точкой, а все остальное - целочисленные операции.

BigInteger в основном неограничен, поэтому вам не следует сталкиваться с какими-либо переполнениями.

РЕДАКТИРОВАТЬ: Извините, только после перечитывания я заметил, что ваша цена в любом случае double. Может быть, стоит обойти это, умножив его на 100, а затем преобразовав в BigInteger - так как я вижу в вашем примере, что оно имеет ровно 2 цифры справа от десятичной точки - и затем разделите его на 100 в конце, хотя это немного хак.

Answer 3

Для максимальной гибкости используйте BigDecimal для rolling и BigInteger для totalQuantity. После деления (обратите внимание, оно у вас задом наперед; оно должно быть подвижным / totalQuantity), вы можете либо вернуть BigDecimal, либо использовать doubleValue с потерей точности.

Answer 4

Делать два цикла: сначала вычислить totalQuantity в первом цикле. Затем во втором цикле накапливаются цены * (количество / общее количество).

Answer 5

Ваш конечный результат представляет собой средневзвешенное значение точности, поэтому, по-видимому, вам не нужно следовать правилам, используемым при расчете остатков на счетах и ​​т. Д. Если я прав в отношении вышеизложенного, вам не нужно использовать 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%, если вы получите удовлетворительную точность, но вы можете проверить это на некотором примере, когда вы знаете, какой ответ должен быть будет.

Answer 6

Во-первых, я не понимаю, как вы могли бы "увеличить" переменную rolling. Как указывает @Ash, он может представлять значения примерно до 1.7 x 10^308. Единственная возможность, о которой я могу думать, - это то, что у вас есть плохие значения в ваших входных данных. (Возможно, настоящая проблема в том, что вы теряете точность ...)

Во-вторых, использование Map для представления заказов странно и, вероятно, не работает. То, как вы используете его в настоящее время, вы не можете представлять заказы с двумя или более предметами по одинаковой цене.

Answer 7

В любой данный момент вы записали как общее значение 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 было кратно многим числам.