Суммируйте неограниченную последовательность, используя постоянное хранилище

Question

Предположим, мы часто выбираем определенное значение и хотим вести статистику по выборкам. Самый простой подход - хранить каждую выборку, чтобы мы могли рассчитать любую статистику, какую захотим, но это требует неограниченного хранения. Используя постоянный объем памяти, мы можем отслеживать некоторые характеристики, такие как минимальные и максимальные значения. Что еще мы можем отслеживать, используя только постоянное хранилище? Я имею в виду процентили, стандартное отклонение и любую другую полезную статистику.

Это теоретический вопрос. В моей реальной ситуации примеры - это просто миллисекунды: профилирование информации для долго работающего приложения. Будут миллионы образцов, но не более миллиарда или около того. Так какую статистику можно сохранить для выборок, используя, скажем, не более 10 переменных?

Answer 1

Минимальное, максимальное, среднее, общее количество, дисперсия - все это просто и полезно. Это 5 значений. Обычно вы храните сумму, а не среднее значение, а когда вам нужно среднее значение, вы можете просто разделить сумму на количество.

Итак, в вашем цикле

maxVal=max(x, maxVal);
minVal=min(x, minVal);
count+=1;
sum+=x;
secondorder+=x*x;

позже вы можете распечатать любую из этих характеристик. Среднее и стандартное отклонение может быть вычислено в любое время и составляет:

mean=sum/count;
std=sqrt(secondorder/count - mean*mean);

Оценка медианы и процентиля более сложна, но возможна. Обычный трюк состоит в том, чтобы сделать наборы гистограмм и заполнить их, когда в них будет найден образец. Затем вы можете оценить медиану и тому подобное, посмотрев на распределение этих групп населения. Это только приближение к распределению, но достаточно часто. Чтобы найти точную медиану, вы должны хранить все образцы.

Answer 2

Вот статья, которая отвечает на ваш вопрос: Точное вычисление рабочей дисперсии .

Помните, что существует несколько способов вычисления дисперсии или стандартного отклонения, которые эквивалентны в точной арифметике, но не в компьютерах с конечной точностью. Некоторые алгоритмы, которые хорошо работают в теории, на практике неточны. В вышеприведенной статье вычисляется текущая дисперсия, то есть постоянная память, и выполняется это точно.

Чтобы вычислить процентили, ваши требования к памяти будут варьироваться в зависимости от размера набора данных. Если вы хотите, например, 5-й и 95-й процентили, ваши требования к памяти будут пропорциональны размеру вашего набора данных. Но если вы просто хотите, скажем, 5-й или 95-й наименьший элемент, то вы можете сделать это в постоянной памяти. См. Статью CodeProject Расчет процентилей в приложениях, связанных с памятью .

Answer 3

Ну, их много. Рассмотрим, например, & sigma ;. Квадратный корень дисперсии, который вычисляется из среднего значения и точки данных, многократно. В точке X _i у вас есть расчетная дисперсия для всех точек до этой; затем добавьте (x- & mu;) & sup2; к этому для следующей оценки. Об этом есть хороший раздел в Википедии .

То, что вы ищете, в общем, называется "интерактивными методами для расчета".