Лучший алгоритм для поиска среднего

Я занимаюсь программированием книги «Книга на C» . Упражнение предполагает, что для нахождения среднего числа чисел, алгоритм:

avg += (x - avg) / i; 

лучше, чем:

 sum += x; avg = sum / i; 

«x» – это переменная, используемая для хранения входных чисел. Это также предполагает предотrotation переполнения, первый алгоритм имеет некоторые другие преимущества, чем второй альгорифм, может ли кто-нибудь мне помочь? Спасибо!

Я предполагаю, что мы говорим о арифметике с плавающей точкой здесь (иначе «лучший» средний будет ужасным).

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

Однако я могу представить, что по мере того, как i становлюсь все больше и больше, значение (x - avg) / i будет становиться все меньше и меньше (относительно). Таким образом, он также имеет свои недостатки.

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

Последний алгоритм быстрее первого, потому что вам нужно выполнить n операций (на самом деле последнее требует выполнения операций 2 * n). Но это правда, что первый предотвращает переполнение. Например, если у вас есть этот набор из 1000 номеров: 4000000 * 250, 1500000 * 500, 2000000 * 500, общая сумма всех целых чисел будет 2’750.000.000, но верхняя граница типа данных c ++ int составляет 2,147,483,647. Итак, в этом случае мы имеем дело с проблемой переполнения. Но если вы выполните первый алгоритм, тогда вы сможете справиться с этой проблемой.

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

Хорошо, ответ кроется не в переполнении суммы (так как это исключено), но, как сказал Оли, «теряя низкую точность». Если среднее из сумм, которые вы суммируете, намного больше, чем расстояние каждого числа от среднего, второй подход потеряет бит мантиссы. Поскольку первый подход рассматривает только относительные значения, он не страдает от этой проблемы.

Таким образом, любой список чисел, который больше, чем, скажем, 60 миллионов (для плавающей точки с одной точностью), но значения не меняются более чем на 10 или около того, должен показать вам поведение.

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

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

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

И, если сумма значений переполняет достаточно большой тип данных, у вас, вероятно, будет больше проблем, чем вычисление среднего.

 sum += x; avg = sum / i; 

В вышеприведенном коде предположим, что у нас есть числа как 10000,20000, … это числа, содержащие большое количество цифр, тогда значение в сумме может превышать его значение MAX. Это не так в I, поскольку сумма всегда делится на элементов перед хранением в нем.

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

Эксперты говорят: «Используйте тип данных согласно вашему заявлению и требованию».

Как насчет такого вычисления, если ints находятся в массиве ?:

 sum += x[i] / N; rem += x[i] % N; avg = sum + rem/N; 

Если N велико (0xFFFFF), а x[i] все маленькие, поэтому rem добавляет до 0xFFFF (наибольший int), тогда может произойти переполнение.