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

Question

У меня есть требование рассчитать среднее значение очень большого набора двойных чисел (10 ^ 9 значений). Сумма значений превышает верхнюю границу двойного, поэтому кто-нибудь знает какие-нибудь изящные маленькие хитрости для вычисления среднего, которые не требуют также вычисления суммы?

Я использую Java 1.5.

Answer 1

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

double mean(double[] ary) {
  double avg = 0;
  int t = 1;
  for (double x : ary) {
    avg += (x - avg) / t;
    ++t;
  }
  return avg;
}

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

Answer 2

ИМХО, самый надежный способ решения вашей проблемы -

1. Сортируй свой набор
2. разбить на группы элементов, сумма которых не будет переполнена - поскольку они отсортированы, это быстро и просто
3. сделать сумму в каждой группе - и разделить на размер группы
4. делайте сумму сумм группы (возможно, вызывая этот же алгоритм рекурсивно) - учтите, что если группы не будут иметь одинаковый размер, вам придется взвесить их по размеру

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

Answer 3

Самый первый вопрос, который я хотел бы вам задать, это:

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

Если нет, тогда у вас нет другого выбора, кроме как суммировать, считать и делить, чтобы получить среднее значение. Если 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

Если у равен 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 даст вам достаточно хорошую точность в таком случае, если он изначально не может содержать всю сумму значений.

Answer 4

Помимо использования уже предложенных лучших подходов, вы можете использовать BigDecimal для выполнения своих расчетов. (Имейте в виду, что он неизменен)

Answer 5

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

Учитывая, что у двойного есть диапазон ~ = +/- 10 ^ 308, и вы суммируете 10 ^ 9 значений, очевидный диапазон, предложенный в вашем вопросе, это значения порядка 10 ^ 299.

Это кажется чем-то, ну, вряд ли ...

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

Я бы также отметил (поскольку никто другой не знает), что для любого набора чисел X:

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

для любой произвольной постоянной c.

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

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

Answer 6

разделите все значения на заданный размер и затем сложите его

Answer 7

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

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

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

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

Answer 8

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

Answer 9

Вариант 1 - использовать библиотеку произвольной точности, чтобы у вас не было верхней границы.

Другие варианты (которые теряют точность) - это суммирование по группам, а не по всем сразу, или деление перед суммированием.

Answer 10

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

-

Подведите итоги подсерии, отслеживая, сколько чисел вы съели, пока не дойдете до переполнения, затем возьмите среднее. Это даст вам среднее значение a0 и количество n0. Повторяйте, пока не исчерпаете список. Теперь у вас должно быть много ай, ни.

Все ai и ni должны быть относительно близки, за исключением возможного последнего укуса в списке. Вы можете смягчить это, недоукусив в конце списка.

Вы можете объединить любое подмножество этих ai, ni, выбрав любой ni в подмножестве (назовите его np) и разделив все ni в подмножестве на это значение. Максимальный размер объединяемых подмножеств - это примерно постоянное значение n.

ni / np должно быть близко к единице. Теперь сумма ni / np * ai и кратная np / (сумма ni), отслеживая сумму ni. Это дает вам новую комбинацию ni, ai, если вам нужно повторить процедуру.

Если вам нужно будет повторить (т. Е. Число пар ai, ni намного больше, чем типичное ni), постарайтесь сохранить относительные значения n постоянными, объединяя сначала все средние на одном уровне n, а затем объединяя на следующий уровень и т. д.