Я отправил ответ на вопрос , породивший этот вопрос, после чего я понял, что мой ответ лучше подходит для этого вопроса, чем для этого. Я воспроизвел это ниже. Однако я замечаю, что мой ответ похож на комбинацию Божо и Анон . .
Поскольку другой вопрос был помечен как независимый от языка, я выбрал C # для примера кода, который я включил. Его относительная простота использования и понятный синтаксис, а также включение нескольких функций, облегчающих эту процедуру (функция DivRem в BCL и поддержка функций итераторов), а также мое собственное знакомство с ней, сделали это хороший выбор для этой проблемы. Поскольку OP здесь заинтересован в Java-решении, но я недостаточно владею Java, чтобы эффективно его написать, было бы неплохо, если бы кто-то мог добавить перевод этого кода в Java.
Некоторые из математических решений здесь очень хороши. Вот простое техническое решение.
Используйте больший тип данных. Это разбивается на две возможности:
Использование высокоточной библиотеки с плавающей точкой. У того, кто сталкивается с необходимостью усреднить миллиард чисел, вероятно, есть ресурсы для покупки или умственные способности для написания 128-битной (или более длинной) библиотеки с плавающей запятой.
Я понимаю недостатки здесь. Конечно, это будет медленнее, чем использование внутренних типов. Вы все еще можете переполнить / потерять, если число значений становится слишком большим. Яда Яда.
Если ваши значения являются целыми числами или могут быть легко масштабированы до целых чисел, сохраните вашу сумму в списке целых чисел. Когда вы переполняете, просто добавьте еще одно целое число. По сути это упрощенная реализация первого варианта. Простой (непроверенный) пример в C # следует
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();
}
}