Я занимаюсь программированием книги "Книга на С". Упражнение предполагает, что для нахождения среднего числа чисел, алгоритм:
avg += (x - avg) / i;
лучше, чем:
sum += x;
avg = sum / i;
'x' - это переменная, используемая для хранения входных чисел. Это также предполагает предотвращение переполнения, первый алгоритм имеет некоторые другие преимущества, чем второй альгорифм, может ли кто-нибудь мне помочь? Спасибо!
Я предполагаю, что мы говорим о арифметике с плавающей запятой здесь (иначе "лучший" средний будет ужасным).
Во втором методе промежуточный результат (sum) будет стремиться расти без ограничений, а это означает, что вы в конечном итоге потеряете низкую точность. В первом методе промежуточный результат должен оставаться примерно одинаковой по величине вашим входным данным (при условии, что ваш вход не имеет огромного динамического диапазона). что означает, что он сохранит точность лучше.
Однако я могу представить, что по мере того, как i становится все больше и больше, значение (x - avg) / i будет становиться все меньше и меньше (относительно). Таким образом, он также имеет свои недостатки.
Лучше в том смысле, что он вычисляет текущее среднее значение, т.е. вам не нужно иметь все ваши номера заранее. Вы можете рассчитать, что по мере того, как вы идете, или когда числа становятся доступными.
Последний алгоритм быстрее первого, потому что вам нужно выполнить n операций (на самом деле последнее требует выполнения операций 2 * n). Но это правда, что первый предотвращает переполнение. Например, если у вас есть этот набор из 1000 номеров: 4000000 * 250, 1500000 * 500, 2000000 * 500, общая сумма всех целых чисел будет 2'750.000.000, но верхняя граница типа данных С++ 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), тогда может произойти переполнение.