Как найти хорошее решение для вычисления среднего значения, если сумма всех значений превышает пределы типа double?

Первый вопрос, который я хотел бы задать, заключается в следующем:

• Знаете ли вы заранее количество значений?

Если нет, то у вас нет другого выбора, кроме как складывать, считать и делить, чтобы получить среднее. Если Double недостаточно точен для этого, то увы, вы не можете использовать Double, вам нужно найти другой тип данных, способный справиться с этой задачей.

С другой стороны, если вы заранее знаете количество значений, вы можете взглянуть на то, что вы на самом деле делаете, и изменить метод расчета, сохраняя общий результат.

Среднее значение N значений, хранящихся в некоторой коллекции A, рассчитывается следующим образом:

A[0]   A[1]   A[2]   A[3]          A[N-1]   A[N]
---- + ---- + ---- + ---- + .... + ------ + ----
 N      N      N      N               N       N

Для вычисления подсчетов этого результата вы можете разделить расчет на равные наборы, чтобы сделать это для трехзначных наборов (при условии, что количество значений делится на 3, в противном случае вам понадобится другой делитель):

/ A[0]   A[1]   A[2] \   / A[3]   A[4]   A[5] \   //      A[N-1]   A[N] \
| ---- + ---- + ---- |   | ---- + ---- + ---- |   \\    + ------ + ---- |
\  3      3      3   /   \  3      3      3   /   //        3       3   /
 --------------------- +  --------------------  + \\      --------------
          N                        N                        N
         ---                      ---                      ---
          3                        3                        3

Обратите внимание, что вам нужны равные наборы, иначе числа в последнем наборе, в котором не будет достаточного количества значений по сравнению со всеми предыдущими наборами, окажут большее влияние на окончательный результат.

Рассмотрим последовательность чисел от 1 до 7, если вы выберете размер набора 3, вы получите следующий результат:

/ 1   2   3 \   / 4   5   6 \   / 7 \ 
| - + - + - | + | - + - + - | + | - |
\ 3   3   3 /   \ 3   3   3 /   \ 3 /
 -----------     -----------     ---
      y               y           y

Это приводит к следующему:

     2   5   7/3
     - + - + ---
     y   y    y

При условии, что y равно 3 для всех наборов, вы получите:

     2   5   7/3
     - + - + ---
     3   3    3

Это дает:

2*3   5*3    7
--- + --- + ---
 9     9     9

Что в итоге равно:

6   15   7
- + -- + -
9    9   9

В результате получаем:

28
-- ~ 3,1111111111111111111111.........1111111.........
 9

Среднее значение для чисел от 1 до 7 равно 4. Очевидно, что данный подход не сработает. Обратите внимание, что если вы выполните данный расчет с числами 1, 2, 3, 4, 5, 6, 7, 0, 0 (обратите внимание на два нуля в конце), то получите тот же результат.

Итак, вам нужны равные наборы. Увы, если в вашем исходном наборе - простое число значений.

Что меня беспокоит, так это потеря точности. Я не уверен, что Double обеспечит достаточную точность в таком случае, если изначально он не может удержать всю сумму значений.

На мой взгляд, самый надежный способ решения вашей проблемы заключается в следующем:

1. Отсортируйте ваш набор данных.
2. Разделите его на группы элементов, сумма которых не приведет к переполнению – поскольку они отсортированы, это будет быстро и просто.
3. Посчитайте сумму в каждой группе и разделите её на размер группы.
4. Посчитайте сумму полученных групповых сумм (возможно, применяя тот же алгоритм рекурсивно) – имейте в виду, что если группы будут разного размера, вам потребуется учитывать их размеры при расчете весов.

Одним из преимуществ этого подхода является то, что он хорошо масштабируется, если у вас действительно большое количество элементов для суммирования и много процессоров или машин, которые можно использовать для выполнения вычислений.

Пожалуйста, уточните возможные диапазоны значений.

Учитывая, что тип double имеет диапазон примерно ±10^{308, и вы складываете 10}9 значений, предполагаемый диапазон, упомянутый в вашем вопросе, составляет порядка 10^299.

Это кажется немного, ну, неправдоподобным...

Если ваши значения действительно настолько велики, то с обычным double у вас есть только 17 значащих десятичных цифр, так что вы потеряете примерно 280 цифр информации до того, как сможете даже подумать о среднем значении.

Также хочу отметить (поскольку никто другой этого не сделал), что для любого множества чисел X:

mean(X) = sum(X[i] - c)  +  c
          -------------
                N

где c — это произвольная константа.

В данной ситуации установка c = min(X) может значительно снизить риск переполнения при суммировании.

Могу ли я скромно предложить, что условие задачи неполное...?

Действительно, разделить число типа double на степень двойки можно без потери точности. Если ваша проблема заключается в абсолютном размере суммы, вы можете предварительно отмасштабировать свои числа перед их сложением. Однако при большом объеме данных все равно существует риск, что вы столкнетесь с ситуацией, когда добавляете маленькие числа к большому, и маленькие значения окажутся в основном (или полностью) проигнорированными.

Например, когда вы складываете 2.2e-20 с 9.0e20, результат будет 9.0e20, поскольку после коррекции масштабов для сложения меньший член фактически становится 0. double может хранить всего около 17 цифр, а для сложения этих двух чисел без потерь вам потребуется более 40 цифр.

Таким образом, в зависимости от вашего набора данных и того, сколько точности вы можете позволить себе потерять, вам может потребоваться предпринять дополнительные шаги. Разделение данных на наборы поможет, но более эффективным способом сохранения точности может быть нахождение грубого среднего значения (возможно, вы уже знаете это число). Затем вычитаете каждое значение из грубого среднего перед их сложением. Таким образом, вы суммируете расстояния от среднего, и ваша сумма не будет достигать слишком больших значений.

После этого вам нужно взять среднее значение дельты и добавить его к вашей грубой сумме, чтобы получить корректное среднее. Отслеживание минимальной и максимальной дельты также позволит узнать, сколько точности вы потеряли в процессе сложения. Если у вас есть время и нужно получить очень точный результат, вы можете использовать итерации.

Вы можете взять среднее значение средних выборок равного размера, параметры которых не превышают заданный лимит.