У меня есть требование рассчитать среднее значение очень большого набора удвоений (10 ^ 9 значений). Сумма значений превышает верхнюю границу двойника, так ли кто-нибудь знает какие-либо опрятные маленькие трюки для вычисления среднего значения, которое не требует также вычисления суммы?
Я использую Java 1.5.
Самый первый вопрос, который я хотел бы задать вам, таков:
Если нет, тогда у вас мало выбора, кроме как суммировать, подсчитывать и делить, делать средний. Если Double недостаточно высокой точности для обработки этого, тогда вам не удастся использовать Double, вам нужно найти тип данных, который может обрабатывать его.
Если, с другой стороны, вы заранее знаете количество значений, вы можете посмотреть, что вы действительно делаете, и изменить, как вы это делаете, но сохранить общий результат.
Среднее значение N, хранящееся в некоторой коллекции A, таково:
A[0] A[1] A[2] A[3] A[N-1] A[N]
---- + ---- + ---- + ---- + .... + ------ + ----
N N N N N N
Чтобы вычислить подмножества этого результата, вы можете разбить вычисление на равные по размеру множества, поэтому вы можете сделать это для 3-значных множеств (если число значений делится на 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 даст вам достаточно хорошую точность в таком случае, если он изначально не может удерживать всю сумму значений.
Вы можете вычислить среднее значение итеративно. Этот алгоритм прост, быстр, вам нужно обрабатывать каждое значение только один раз, а переменные никогда не будут больше, чем наибольшее значение в наборе, поэтому вы не получите переполнение.
double mean(double[] ary) {
double avg = 0;
int t = 1;
for (double x : ary) {
avg += (x - avg) / t;
++t;
}
return avg;
}
Внутри цикла avg всегда есть среднее значение всех обработанных значений. Другими словами, если все значения конечны, вы не должны переполняться.
IMHO, самый надежный способ решения вашей проблемы -
Одна из хороших вещей в этом подходе заключается в том, что он хорошо масштабируется, если у вас есть действительно большое количество элементов для суммирования - и большое количество процессоров/машин, которые будут использоваться для выполнения математики
Помимо использования более совершенных подходов, которые уже были предложены, вы можете использовать BigDecimal для выполнения своих расчетов. (Имейте в виду, что он неизменен)
Просьба уточнить диапазоны значений значений.
Учитывая, что двойник имеет диапазон ~ = +/- 10 ^ 308, и вы суммируете значения 10 ^ 9, видимый диапазон, предложенный в вашем вопросе, составляет величину порядка 10 ^ 299.
Это кажется несколько, ну, маловероятно...
Если ваши значения действительно такие большие, то с обычным двойным вы получите только 17 значащих десятичных цифр, чтобы вы могли играть, поэтому вы будете выбросить около 280 цифр информации, прежде чем вы сможете даже подумать об усреднении значения.
Я также хотел бы отметить (поскольку ни у кого другого нет), что для любого набора чисел X:
mean(X) = sum(X[i] - c) + c
-------------
N
для любой произвольной константы c.
В этой конкретной задаче установка c = min(X) может значительно снизить риск переполнения во время суммирования.
Могу ли я смиренно предположить, что постановка проблемы неполна...?
Вы можете взять среднее значение средних равных по размеру подмножеств чисел, которые не превышают предела.
делить все значения на заданный размер, а затем суммировать его
Двойник можно разделить на мощность 2 без потери точности. Поэтому, если ваша единственная проблема, если абсолютный размер суммы, вы можете предварительно масштабировать свои номера перед их суммированием. Но с набором данных такого размера все еще существует риск того, что вы столкнетесь с ситуацией, когда вы добавляете небольшие числа в большую, а маленькие числа будут в основном (или полностью) проигнорированы.
например, когда вы добавляете 2.2e-20 в 9.0e20, результат равен 9.0e20, потому что, как только шкалы будут скорректированы так, чтобы их числа могли быть добавлены вместе, меньшее число равно 0. Удвои могут содержать только 17 цифр, и вам понадобится более 40 цифр, чтобы добавить эти два номера вместе без потерь.
Итак, в зависимости от вашего набора данных и количества цифр, которые вы можете позволить себе потерять, вам, возможно, придется делать другие вещи. Ломать данные в наборах поможет, но лучший способ сохранить точность может заключаться в определении приблизительного среднего (вы уже знаете это число). затем вычтите каждое значение из грубой средней, прежде чем суммировать ее. Таким образом, вы суммируете расстояния от среднего, поэтому ваша сумма никогда не должна становиться очень большой.
Затем вы берете среднюю дельту и добавляете ее к своей приблизительной сумме, чтобы получить правильное среднее значение. Отслеживание минимальной и максимальной дельты также расскажет вам, сколько точности вы потеряли во время суммирования. Если у вас много времени и вам нужен очень точный результат, вы можете выполнять итерацию.
Вариант 1 - использовать библиотеку произвольной точности, поэтому у вас нет верхней границы.
Другие варианты (которые теряют точность) состоят в том, чтобы суммировать в группах, а не сразу, или делиться перед суммированием.
Поэтому я не повторяю себя так сильно, позвольте мне сказать, что я предполагаю, что список чисел обычно распределяется и вы можете суммировать много чисел перед переполнением. Техника по-прежнему работает для нестандартных дистрибутивов, но что-то не соответствует ожиданиям, которые я описываю ниже.
-
Подведите подсерию, отслеживая, сколько чисел вы едите, пока не приблизитесь к переполнению, а затем возьмите среднее. Это даст вам среднее значение a0 и count n0. Повторяйте, пока не исчерпаете список. Теперь у вас должно быть много ai, ni.
Каждое ai и ni должно быть относительно близко, за исключением, возможно, последнего укуса списка. Вы можете смягчить это путем недокусания в конце списка.
Вы можете комбинировать любое подмножество этих ai, ni, выбирая любое ni в подмножестве (назовите его np) и разделив все ni в подмножестве на это значение. Максимальный размер подмножеств для объединения - это примерно постоянное значение n.
ni/np должен быть близок к одному. Теперь сумма ni/np * ai и кратная np/(sum ni), отслеживая сумму ni. Это дает вам новую комбинацию ni, ai, если вам нужно повторить процедуру.
Если вам нужно будет повторить (т.е. число ai, ni-пар намного больше, чем типичное ni), попробуйте сохранить относительные n-размеры константы, сначала объединив все средние значения на одном n-м уровне, а затем объединив в следующий уровень и т.д.
Прежде всего, ознакомьтесь с внутренним представлением значений double. Википедия должна стать хорошей отправной точкой.
Затем рассмотрим, что двойники выражаются как "значение плюс экспонента", где показатель степени равен двум. Предел наибольшего двойного значения - верхний предел показателя, а не предел значения! Таким образом, вы можете разделить все большие входные числа на достаточно большую мощность в два. Это должно быть безопасным для всех достаточно больших чисел. Вы можете повторно умножить результат с коэффициентом, чтобы проверить, потеряли ли вы точность при умножении.
Здесь мы идем с алгоритмом
public static double sum(double[] numbers) {
double eachSum, tempSum;
double factor = Math.pow(2.0,30); // about as large as 10^9
for (double each: numbers) {
double temp = each / factor;
if (t * factor != each) {
eachSum += each;
else {
tempSum += temp;
}
}
return (tempSum / numbers.length) * factor + (eachSum / numbers.length);
}
и не беспокоится о дополнительном делении и умножении. FPU будет оптимизировать ад из них, так как они выполняются с силой двух (для сравнения представьте себе добавление и удаление цифр в конце десятичных чисел).
PS: кроме того, вы можете использовать суммирование Kahan для повышения точности. Суммирование Kahan позволяет избежать потери точности при суммировании очень больших и очень малых чисел.
Случайная выборка небольшого набора полного набора данных часто приводит к "достаточно хорошему" решению. Вы, очевидно, должны сделать это определение самостоятельно на основе системных требований. Размер выборки может быть очень маленьким и получить достаточно хорошие ответы. Это можно адаптивно вычислить, вычислив среднее значение возрастающего числа случайно выбранных выборок - среднее будет сходиться в течение некоторого интервала.
Отбор проб не только затрагивает проблему двойного переполнения, но намного, намного быстрее. Не применимо для всех проблем, но, безусловно, полезно для многих проблем.
Я отправил ответ на вопрос, порожденный из этого, осознав впоследствии, что мой ответ лучше подходит для этого вопроса, чем для этого. Я воспроизвел его ниже. Однако я замечаю, что мой ответ похож на комбинацию Bozho's и Anon .суб > 's.
Поскольку другой вопрос был помечен как язык-агностик, я выбрал С# для образца кода, который я включил. Его относительная простота использования и простой в использовании синтаксис, а также включение в него нескольких функций, облегчающих эту процедуру (функция DivRem в BCL и поддержка функций итератора), а также мое собственное знакомство с ней это хороший выбор для этой проблемы. Поскольку OP здесь интересуется Java-решением, но я не достаточно Java-достаточно, чтобы писать его эффективно, было бы неплохо, если бы кто-то мог добавить перевод этого кода на Java.
Некоторые из математических решений здесь очень хорошие. Здесь простое техническое решение.
Используйте больший тип данных. Это разбивается на две возможности:
Используйте высокоточную библиотеку с плавающей запятой. Тот, кто сталкивается с необходимостью усреднять миллиард чисел, вероятно, имеет ресурсы для покупки или умственного использования для записи 128-битной (или более поздней) библиотеки с плавающей запятой.
Я понимаю недостатки здесь. Это, конечно, будет медленнее, чем использование собственных типов. Если количество значений слишком велико, вы можете превысить/недопустить. Яда-яда.
Если ваши значения являются целыми числами или могут быть легко масштабированы до целых чисел, держите свою сумму в списке целых чисел. Когда вы переполняете, просто добавьте другое целое число. Это, по сути, упрощенная реализация первого варианта. Простой пример (untested) в С# следует
class BigMeanSet{
List<uint> list = new List<uint>();
public double GetAverage(IEnumerable<uint> values){
list.Clear();
list.Add(0);
uint count = 0;
foreach(uint value in values){
Add(0, value);
count++;
}
return DivideBy(count);
}
void Add(int listIndex, uint value){
if((list[listIndex] += value) < value){ // then overflow has ocurred
if(list.Count == listIndex + 1)
list.Add(0);
Add(listIndex + 1, 1);
}
}
double DivideBy(uint count){
const double shift = 4.0 * 1024 * 1024 * 1024;
double rtn = 0;
long remainder = 0;
for(int i = list.Count - 1; i >= 0; i--){
rtn *= shift;
remainder <<= 32;
rtn += Math.DivRem(remainder + list[i], count, out remainder);
}
rtn += remainder / (double)count;
return rtn;
}
}
Как я уже сказал, это непроверено - у меня нет миллиарда значений, которые я действительно хочу усреднить, поэтому я, вероятно, совершил ошибку или два, особенно в функции DivideBy, но это должно демонстрируют общую идею.
Это должно обеспечить такую же точность, как двойник, который может представлять и должен работать для любого количества 32-битных элементов, до 2 32 - 1. Если требуется больше элементов, то count необходимо расширить, а функция DivideBy будет увеличиваться по сложности, но я оставлю это как упражнение для читателя.
С точки зрения эффективности, он должен быть таким же быстрым или быстрым, как и любой другой метод здесь, поскольку он требует только повторения в списке один раз, выполняет только одну операцию деления (ну, один набор из них) и делает большую часть своих работать с целыми числами. Однако я не оптимизировал его, и я уверен, что при необходимости он может быть немного быстрее. Отключение рекурсивного вызова функции и индексации списка было бы хорошим началом. Опять же, упражнение для читателя. Код предназначен для простого понимания.
Если кто-то более мотивирован, чем я сейчас, чувствую, что проверяю правильность кода и исправляю любые проблемы, которые могут возникнуть, пожалуйста, будь моим гостем.
Теперь я проверил этот код и сделал пару небольших исправлений (отсутствующая пара круглых скобок в вызове конструктора List<uint> и неправильный делитель в конечном делении функции DivideBy).
Я проверил его, сначала выполнив его через 1000 наборов случайной длины (от 1 до 1000), заполненных случайными целыми числами (в диапазоне от 0 до 2 32 - 1). Это были наборы, для которых я мог легко и быстро проверить точность, также используя для них каноническое среднее.
Затем я тестировал большие серии со 100 * со случайной длиной между 10 5 и 10 9. Нижняя и верхняя границы этих рядов также выбирались случайным образом, с ограничениями, чтобы серия соответствовала диапазону 32-разрядного целого. Для любого ряда результаты легко проверяются как (lowerbound + upperbound) / 2.
* Хорошо, это немного белая ложь. Я прервал испытание большой серии после 20 или 30 успешных прогонов. Ряд длины 10 9 занимает всего полторы минуты, чтобы работать на моей машине, поэтому полчаса или около того тестирования этой процедуры было достаточно для моих вкусов.
Для тех, кого интересует, мой тестовый код ниже:
static IEnumerable<uint> GetSeries(uint lowerbound, uint upperbound){
for(uint i = lowerbound; i <= upperbound; i++)
yield return i;
}
static void Test(){
Console.BufferHeight = 1200;
Random rnd = new Random();
for(int i = 0; i < 1000; i++){
uint[] numbers = new uint[rnd.Next(1, 1000)];
for(int j = 0; j < numbers.Length; j++)
numbers[j] = (uint)rnd.Next();
double sum = 0;
foreach(uint n in numbers)
sum += n;
double avg = sum / numbers.Length;
double ans = new BigMeanSet().GetAverage(numbers);
Console.WriteLine("{0}: {1} - {2} = {3}", numbers.Length, avg, ans, avg - ans);
if(avg != ans)
Debugger.Break();
}
for(int i = 0; i < 100; i++){
uint length = (uint)rnd.Next(100000, 1000000001);
uint lowerbound = (uint)rnd.Next(int.MaxValue - (int)length);
uint upperbound = lowerbound + length;
double avg = ((double)lowerbound + upperbound) / 2;
double ans = new BigMeanSet().GetAverage(GetSeries(lowerbound, upperbound));
Console.WriteLine("{0}: {1} - {2} = {3}", length, avg, ans, avg - ans);
if(avg != ans)
Debugger.Break();
}
}
Рассмотрим это:
avg(n1) : n1 = a1
avg(n1, n2) : ((1/2)*n1)+((1/2)*n2) = ((1/2)*a1)+((1/2)*n2) = a2
avg(n1, n2, n3) : ((1/3)*n1)+((1/3)*n2)+((1/3)*n3) = ((2/3)*a2)+((1/3)*n3) = a3
Итак, для любого набора удвоений произвольного размера вы можете сделать это (это на С#, но я уверен, что его можно легко перевести на Java):
static double GetAverage(IEnumerable<double> values) {
int i = 0;
double avg = 0.0;
foreach (double value in values) {
avg = (((double)i / (double)(i + 1)) * avg) + ((1.0 / (double)(i + 1)) * value);
i++;
}
return avg;
}
На самом деле, это легко упрощается (уже предоставлено martinus):
static double GetAverage(IEnumerable<double> values) {
int i = 1;
double avg = 0.0;
foreach (double value in values) {
avg += (value - avg) / (i++);
}
return avg;
}
Я написал быстрый тест, чтобы попробовать эту функцию против более традиционного метода суммирования значений и деления на count (GetAverage_old). Для моего ввода я написал эту быструю функцию, чтобы вернуть как можно больше случайных положительных удвоений:
static IEnumerable<double> GetRandomDoubles(long numValues, double maxValue, int seed) {
Random r = new Random(seed);
for (long i = 0L; i < numValues; i++)
yield return r.NextDouble() * maxValue;
yield break;
}
И вот результаты нескольких тестовых испытаний:
long N = 100L;
double max = double.MaxValue * 0.01;
IEnumerable<double> doubles = GetRandomDoubles(N, max, 0);
double oldWay = GetAverage_old(doubles); // 1.00535024998431E+306
double newWay = GetAverage(doubles); // 1.00535024998431E+306
doubles = GetRandomDoubles(N, max, 1);
oldWay = GetAverage_old(doubles); // 8.75142021696299E+305
newWay = GetAverage(doubles); // 8.75142021696299E+305
doubles = GetRandomDoubles(N, max, 2);
oldWay = GetAverage_old(doubles); // 8.70772312848651E+305
newWay = GetAverage(doubles); // 8.70772312848651E+305
ОК, но как насчет значений 10 ^ 9?
long N = 1000000000;
double max = 100.0; // we start small, to verify accuracy
IEnumerable<double> doubles = GetRandomDoubles(N, max, 0);
double oldWay = GetAverage_old(doubles); // 49.9994879713857
double newWay = GetAverage(doubles); // 49.9994879713868 -- pretty close
max = double.MaxValue * 0.001; // now let try something enormous
doubles = GetRandomDoubles(N, max, 0);
oldWay = GetAverage_old(doubles); // Infinity
newWay = GetAverage(doubles); // 8.98837362725198E+305 -- no overflow
Естественно, насколько приемлемо это решение, будет зависеть от ваших требований к точности. Но стоит подумать.
Ознакомьтесь с разделом совокупная скользящая средняя
Чтобы сделать логику простой и сохранить производительность не лучшим, но приемлемым, я рекомендую вам использовать BigDecimal вместе с примитивным типом. Концепция очень проста: вы используете примитивный тип для суммирования значений вместе, всякий раз, когда значение будет переполняться или переполняется, вы перемещаете значение вычисления в BigDecimal, а затем сбрасываете его для следующего расчета суммы. Еще одна вещь, о которой вы должны знать, - это когда вы строите BigDecimal, вы должны всегда использовать String вместо double.
BigDecimal average(double[] values){
BigDecimal totalSum = BigDecimal.ZERO;
double tempSum = 0.00;
for (double value : values){
if (isOutOfRange(tempSum, value)) {
totalSum = sum(totalSum, tempSum);
tempSum = 0.00;
}
tempSum += value;
}
totalSum = sum(totalSum, tempSum);
BigDecimal count = new BigDecimal(values.length);
return totalSum.divide(count);
}
BigDecimal sum(BigDecimal val1, double val2){
BigDecimal val = new BigDecimal(String.valueOf(val2));
return val1.add(val);
}
boolean isOutOfRange(double sum, double value){
// because sum + value > max will be error if both sum and value are positive
// so I adapt the equation to be value > max - sum
if(sum >= 0.00 && value > Double.MAX - sum){
return true;
}
// because sum + value < min will be error if both sum and value are negative
// so I adapt the equation to be value < min - sum
if(sum < 0.00 && value < Double.MIN - sum){
return true;
}
return false;
}
Из этой концепции каждый раз, когда результат является недостаточным или переполненным, мы будем держать это значение в большей переменной, это решение может немного замедлить производительность из-за вычисления BigDecimal, но это гарантирует стабильность выполнения.
(n 1 + n 2 +... + n k)/k = (n 1 + n 2)/k + (n 3 + n 4)/k +... + (n k- 1 + n k)/k, если k четно
(n 1 + n 2 +... + n k)/k = n 1/k + (n 2 + n 3)/k +... + (n k-1 + n k)/k, если k нечетно
Почему так много сложных длинных ответов. Вот самый простой способ найти текущее среднее значение до сих пор, без необходимости знать, сколько элементов или размеров и т.д.
long int я = 0; double average = 0; в то время как (все еще есть элементы) { средний = средний * (i/i + 1) + X [i]/(i + 1); я ++; } средний доход;