Среднее арифметическое куууучи чисел

#алгоритм #big_data #java

Дано: пару миллиардов int -ов (короче очень много)
Найти: их среднее арифметическое (оссобой точности не надо, 1-2 знаков после запятой
хватит)
Можно конечно их всех просуммировать в какой-нибудь BigInteger (или собственную реализацию),
но нет ли способов покрасивее и попроще :) ?
p.s. в моём случае скорость не играет роли, но вообще хотелось бы увидеть что-нибудь
не очень тормознутое     

Ответы

Ответ 1

А в чём проблема? Сумма двух милллиардов int'ов поместится в long даже если они все
равны максимальному значению. А уж если int'ы нормальные...
Так что смело суммируйте всё в long с детектированием переполнения. И делите на количество.


Ответ 2

Всё ещё проще на самом деле...


  
  Имеем последовательность чисел x1, x2, x3, x4, x5...
  k=2; //количество чисел, текущий шаг
  Находим среднее арифметическое первых двух чисел r=(x1+x2)/k.
  Далее не будем постоянно считать суммы, а будем брать следующий множитель для следующего
среднего арифметического: n=(k*r+x3)/((k+1)* r). //x3 естественно на каждом шаге меняется
на следующий элемент
  Следующее среднее арифметическое: r=r*n.
  k=k+1
  Повторяем шаги 4..6 для нужного числа чисел.


Ответ 3

Предложу свой вариант.
Этот миллиард группируется в какой-то класс. Много объектов. Группируется так, чтобы
сумма этой группы нечаянно не превыcила Integer.MAX_VALUE. В объект заносится сумма
этих чисел и их количество. Сами числа уже не нужны. Далее вычисляется ср. арифметическое
для этого объекта. Придётся создать много таких объектов-групп. После разбивания всех
входных данных на эти объекты-группы, зная общую сумму и общее количество, делим - и всё.
Очень хорошо, если хоть кто-то понял мой алгоритм.


Ответ 4

Страдает точность, но переполнение невозможно.

avg = 0;
for (int i = 0, n = 1; i < array.length; i++, n++)
    avg = avg * (1 - 1f / n) + (float) array[i] / n;
return avg;


А если нам не нужно добавлять новые элементы в среднее арифметическое, мы можем сразу
делить каждый элемент на n.

avg = 0;
for (int i = 0; i < array.length; i++)
    avg += (float) array[i] / array.length;
return avg;


Ответ 5

Среднее арифметическое можно искать не складывая все числа разом.
Их можно складывать группами.

Например:

даны числа 

   [1, 2, 3, 4, 5]


среднее арифметическое 

   (1 + 2 + 3 + 4 + 5) / 5 = 3


то же самое можно получить, если складывать пересекающимися парами

   (1 + 2) / 2 = 1.5
   (2 + 3) / 2 = 2.5
   (3 + 4) / 2 = 3.5
   (4 + 5) / 2 = 4.5
   (1.5 + 2.5) / 2 = 2
   (2.5 + 3.5) / 2 = 3
   (3.5 + 4.5) / 2 = 4
   (2 + 3) / 2 = 2.5
   (3 + 4) / 2 = 3.5
   (2.5 + 3.5) / 2 = 3 // результат


или тройками

   (1 + 2 + 3) / 3 = 2
   (3 + 4 + 5) / 3 = 4
   (2 + 4) / 2 = 3 // результат


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

   [1, 2, 3, 4, 5, 6] -> (1 + 2 + 3 + 4 + 5 + 6) / 6 = 3.5

   (1 + 2 + 3) / 3 = 2
   (4 + 5 + 6) / 3 = 5
   (2 + 5) / 2 = 3.5 // результат


И, разумеется, можно комбинировать. То есть, на первом уровне, например, складывать
парами, на втором тройками.

Группы конечно могут быть и по сто и по тысяче чисел. Но думаю, что это может помочь
от переполнения.