предотвратить переполнение длительного усреднения?

предположим, я хочу рассчитать среднее значение набора данных, такого как

class Averager {
   float total;
   size_t count;
   float addData (float value) {
       this->total += value;
       return this->total / ++this->count;
   }
}

рано или поздно значение total или count переполнится, поэтому я не запоминаю общее значение:

class Averager {
   float currentAverage;
   size_t count;
   float addData (float value) {
       this->currentAverage = (this->currentAverage*count + value) / ++count;
       return this->currentAverage;
   }
}

кажется, что они будут переполняться дольше, но умножение между average и count приводит к проблеме переполнения, поэтому следующее решение:

class Averager {
   float currentAverage;
   size_t count;
   float addData (float value) {
       this->currentAverage += (value - this->currentAverage) / ++count;
       return this->currentAverage;
   }
}

кажется лучше, следующая проблема - как предотвратить переполнение count?


c++ numeric average overflow math
person uray    schedule 23.07.2010    source источник
comment
Я думаю, что проблема числовой неточности более серьезна, чем переполнение.   -  person kennytm    schedule 23.07.2010
comment
Очень маловероятно, что total переполнится. Он потеряет точность, если станет намного больше среднего.   -  person Marcelo Cantos    schedule 23.07.2010
comment
@kenny: будет некоторая потеря точности, но по мере роста количества добавленная стоимость становится менее чувствительной к среднему значению, ее можно решить статистически.   -  person uray    schedule 23.07.2010
comment
@marcelo: если count 32 бита, он переполнится, если счетчик больше 2 ^ 32   -  person uray    schedule 23.07.2010

Ответы (6)


arrow_upward
7
arrow_downward

Агрегатные ковши.

Мы выбираем размер ведра, который удобно меньше, чем SquareRoot(MAXINT). Для простоты возьмем 10.

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

Когда ведро наполнится, запустите новое ведро, помня о среднем значении полного ведра. Мы можем безопасно рассчитать общее среднее значение, объединив средние значения полных сегментов и текущего частичного сегмента. Когда мы доберемся до 10 полных ведер, мы создадим ведро побольше, вместимостью 100.

Чтобы вычислить общее среднее значение, мы сначала вычисляем среднее значение «10», а затем объединяем его с «сотнями». Этот шаблон повторяется для «1000 с», «10 000 с» и так далее. На каждом этапе нам нужно рассматривать только два уровня, один из которых в 10 раз больше предыдущего.

person djna    schedule 23.07.2010
comment
Я думаю, что вы описываете скользящую среднюю (en.wikipedia.org/wiki/Moving_average) - person Daniel Rikowski; 23.07.2010
comment
@DR Я думаю, что это немного больше - классическая скользящая средняя должна поддерживать подсчет того, сколько элементов мы видели, и в конечном итоге это может переполниться. Техника, которую я описываю, позволяет избежать этой проблемы. - person djna; 23.07.2010

arrow_upward
2
arrow_downward

Используйте 1_. Вы все равно должны беспокоиться о точности, но это будет гораздо меньше проблем, чем с float.

person Marcelo Cantos    schedule 23.07.2010
comment
Мне нужен статистический подход к этой проблеме, независимо от того, насколько велик тип данных counter, рано или поздно он переполнится - person uray; 23.07.2010
comment
@uray: ты серьезно? 64-разрядному счетчику потребуется 70 лет, даже если вы будете увеличивать его 4 миллиарда раз в секунду. Вы ожидаете, что ваша программа будет работать 70 лет? Ожидаете ли вы, что вам придется усреднять более 18 квинтиллионов чисел? - person Marcelo Cantos; 23.07.2010
comment
@uray и Марсело: тогда я не вижу возможного решения. В конце концов виртуальная память будет исчерпана или вселенная рухнет. ;-) - person Peter G.; 23.07.2010
comment
@marcelo: проблема в том, что по мере роста счетчика эта часть (value - this->currentAverage) / ++count станет равной нулю, и вычисления не требуются, поэтому больший тип данных бесполезен. - person uray; 23.07.2010
comment
@uray: Марсело указал вам на это в качестве комментария к вашему вопросу, и вы сказали, что это не имеет значения. Я думаю, вам нужно определить, какую проблему вы пытаетесь решить. - person Dennis Zickefoose; 23.07.2010
comment
@dennis: да, судя по моему первому комментарию, марсело отвечает правильно, увеличивая тип данных счетчика, но моя точка зрения заключается в том, что я ищу решение без изменения типа данных, используемый тип данных счетчика является плавающим (как мой пример кода) или меньше будет лучше. - person uray; 23.07.2010

arrow_upward
1
arrow_downward

Как насчет использования арифметики произвольной точности?

В Википедии есть список библиотек, которые вы можете использовать: http://en.wikipedia.org/wiki/Bignum#Libraries

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

person SirDarius    schedule 23.07.2010

arrow_upward
1
arrow_downward

Вы хотите использовать алгоритм суммирования Кахана:

http://en.wikipedia.org/wiki/Kahan_summation_algorithm

См. также раздел об ошибках суммирования в статье «Что должен знать каждый компьютерный ученый об арифметике с плавающей запятой».

http://docs.sun.com/source/806-3568/ncg_goldberg.html#1262

person user239558    schedule 23.07.2010
comment
Алгоритм Кахана уменьшает потерю точности, но не решит проблему переполнения. - person kennytm; 23.07.2010

arrow_upward
0
arrow_downward

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

person Henri    schedule 23.07.2010

arrow_upward
0
arrow_downward

Я как раз тоже об этом думал. Я думаю, что это решение работает с точки зрения нового значения «перемещение иглы». Он перемещает его только на коэффициент количества предыдущих значений, которые внесли свой вклад в среднее значение на данный момент (плюс 1 для себя). Он будет терять точность по мере роста входных данных, но в среднем должен быть практически приемлемым. Вот некоторый код Java, который, кажется, работает. Я использовал числа с плавающей запятой и целые числа здесь, чтобы продемонстрировать, что он будет работать с этими ограничениями, но вы можете использовать double для повышения точности. Это просто для того, чтобы дать вам представление о том, как усреднять массив почти максимальных целых чисел. Вам нужно будет отслеживать общее количество входов и текущее среднее значение, но не общую сумму входов. Если ваше общее количество входных данных приближается к MAX_INT, это в конечном итоге не сработает, и вам следует использовать приведенное выше предложение с ведром, но в большинстве случаев это довольно радикально.

    public float calcAverageContinuous(int[] integers)
{
    float ave = 0;
    for (int i = 0; i < integers.length; i++) {
        ave += (((float)integers[i] - ave) / (float)(i + 1));
    }
    return ave;
}
person Alex Worden    schedule 17.08.2019