как лучше посчитать среднее? С этим вопросом я хочу знать, какой алгоритм вычисления среднего является лучшим в числовом смысле. Он должен иметь наименьшие ошибки округления, не должен быть чувствителен к переполнению или недостатку и так далее.
Спасибо.
Дополнительная информация: предпочтительны инкрементальные подходы, так как количество значений может не уместиться в ОЗУ (несколько параллельных вычислений на файлах размером более 4 ГБ).
Вы можете посмотреть на http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.3535 (Ник Хайэм, "Точность суммирования с плавающей запятой", SIAM Journal of Scientific Computation, 1993).
Если я правильно помню, компенсированное суммирование (суммирование Кахана) хорошо, если все числа положительны, по крайней мере так же хорошо, как их сортировка и сложение в порядке возрастания (если только чисел не очень-очень много). История намного сложнее, если некоторые числа положительные, а некоторые отрицательные, так что вы получаете отмену. В этом случае есть аргумент для добавления их в порядке убывания.
Если вам нужен алгоритм O(N), посмотрите на суммирование Кэхана.
Расположите числа в порядке возрастания величины. Суммируйте их, сначала низкую величину. Разделить на количество.
Просто добавьте один возможный ответ для дальнейшего обсуждения:
Постепенно вычисляйте среднее значение для каждого шага:
AVG_n = AVG_(n-1) * (n-1)/n + VALUE_n / n
или попарное сочетание
AVG_(n_a + n_b) = (n_a * AVG_a + n_b * AVG_b) / (n_a + n_b)
(надеюсь формулы достаточно понятны)
1/n вносит ошибки в младшие значащие биты, поэтому n/n != 1, по крайней мере, когда выполняется как трехэтапная операция (разделить-сохранить-умножить). Это сводится к минимуму, если деление выполняется только один раз, но вы будете делать это с данными в ГБ.
- person rcollyer; 06.10.2011
double average(IList<int> numbers, int avgUpTo1BasedIndex) { return (avgUpTo1BasedIndex == 1) ? numbers[0] : average(numbers, avgUpTo1BasedIndex - 1) * (avgUpTo1BasedIndex - 1) / avgUpTo1BasedIndex + (double)numbers[avgUpTo1BasedIndex - 1] / avgUpTo1BasedIndex; }
- person ShawnFeatherly; 25.10.2014
Я всегда использую следующий псевдокод:
float mean=0.0; // could use doulbe
int n=0; // could use long
for each x in data:
++n;
mean+=(x-mean)/n;
У меня нет формальных доказательств его стабильности, но вы можете видеть, что у нас не будет проблем с числовым переполнением, если предположить, что значения данных ведут себя хорошо. Об этом говорится в книге Кнута Искусство компьютерного программирования.
float это будет тем менее точным, чем ближе n будет к 2^23. Например, последовательность из 10 миллионов значений 1.0, за которыми следуют 10 миллионов значений 2.0, в среднем составит 1.269. Это потому, что (x-mean)/n приближается к нулю, а mean не меняется при добавлении.
- person jpa; 06.03.2021
Очень поздний пост, но, поскольку у меня недостаточно репутации, чтобы комментировать, метод @Dave используется (по состоянию на декабрь 2020 г.) Научная библиотека Gnu.
Вот код, извлеченный из mean_source.c:
double FUNCTION (gsl_stats, mean) (const BASE data[], const size_t stride, const size_t size)
{
/* Compute the arithmetic mean of a dataset using the recurrence relation mean_(n) = mean(n-1) + (data[n] - mean(n-1))/(n+1) */
long double mean = 0;
size_t i;
for (i = 0; i < size; i++)
{
mean += (data[i * stride] - mean) / (i + 1);
}
return mean;
}
GSL использует тот же алгоритм для вычисления дисперсии, которая, в конце концов, является просто средним значением квадратов разностей от заданного числа.
