Быстрый расчет минимального, максимального и среднего числа входящих номеров

Ответ 1

Вот алгоритм, который будет несколько работать для экономии эффективности в некоторых случаях:

• По мере того как происходят события, буферизируйте их полностью и вычисляйте текущие sum, count, min, max (тривиальные).

• Когда выполняется запрос для average, min или max, пройдите через обратную сторону буфера и начните удаление значений более одной секунды. Вычитайте из sum и count, как вы идете.

  • Если все значения выше min, вы можете сохранить min. Если значения ниже max, вы можете сохранить свой max. В этом случае вы эффективно average, min и max.

  • Если значения ниже min или выше max, вам нужно будет пропустить оставшуюся часть массива и пересчитать его.

• Сделайте шаг два раз в секунду или около того, чтобы буфер не заполнился слишком сильно. Этот код можно было бы выполнять и в каждой буферной вставке, или там, где это имело смысл.

Лучшей структурой для такого рода работ является круговой буфер, чтобы избежать выделения памяти и сбоя GC. Он должен быть достаточно большим, чтобы покрыть наихудший сценарий для размера сообщения в секунду.

Обновление

В зависимости от сценария использования еще одна задача - запустить алгоритм выше, но в 10 х 100 мс фрагментов, а не 1 х 1000 мсек. То есть, продолжайте работать min, max, sum и count на этих 10 кусках. Затем, когда вы достигаете сценария "недействительности", вам обычно нужно просматривать только последние 100 мс данных или быстро пройти через мин и максимум остальных 9 фрагментов.

@ja72 предоставили отличную идею, чтобы сэкономить на поиске значений min и max, если они недействительны:

Вместо сохранения значений min/max x_min, x_max вместо этого укажет индекс где они находятся в массиве x [i] с i_min и i_max. Тогда их поиск может быть тривиальным иногда, но когда последнее рассматриваемое значение содержит min и max, весь список необходимо отсканировать, чтобы установить новые пределы.

У Sam Holder была другая хорошая идея в комментариях - держите параллельный массив, который всегда сортируется, это позволяет вам вырезать числа сверху или снизу, чтобы легче найти новые минимумы и максимумы. Однако скорость вставки здесь немного скомпрометирована (она должна оставаться в порядке).

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

Ответ 2

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

Когда каждый элемент вставлен в буферную головку, проверьте истечение на другой стороне буфера, удалите элемент.

Если удаленный элемент является минимальным или максимальным, вам нужно будет вычислить новый min/max. Если это не так, вы обновите min/max в соответствии с новыми поступлениями.

Для avg сохраните общее количество, сохраните счет и разделите.

Ответ 3

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

Затем, когда число прибывает, добавьте его в очередь и настройте min/max/value и count. Затем посмотрите на другой конец очереди и удалите все элементы, которые не находятся в пределах 1 секунды от прибытия последнего номера, и снова настройте максимальное/минимальное/общее значение.

Тогда вам не нужно постоянно вычислять что-либо, просто верните предварительно рассчитанный материал (т.е. прочитайте текущее значение min/max или total/count)

Как отметил @yaman, вы не можете сохранить только мин и макс, как при удалении вы можете не знать нового. в этом случае я, вероятно, просто сохранил бы вторую копию всех номеров в списке, но вместо того, чтобы заказывать по времени прибытия, я заказываю по значению. Затем вы просто добавляете и удаляете каждый номер из этого списка, так что вы всегда будете знать максимальные и минимальные значения. Это избавит вас от необходимости сканировать все элементы в буфере, чтобы найти новый макс/мин, за счет хранения 2 копий, но обновления этого списка должны быть дешевыми, поскольку они уже заказываются.

Ответ 4

@DanRedux корректен; вам нужно будет их вычислять каждый раз, потому что ваш вход меняется. Теперь вы можете рассчитывать эти числа по требованию или вверх (т.е. Когда вы получаете новую партию) в зависимости от того, насколько часто нужны результаты.

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

Как их хранить, у вас действительно нет выбора, не так ли? Вам нужно пространство для всех 50 000 номеров в памяти. Итак... вам нужен кусок памяти, достаточно большой, чтобы держать их. Чтобы избежать постоянного выделения 2 КБ каждый раз, когда приходит новая последовательность, вам, вероятно, лучше объявить массив, достаточный для того, чтобы максимально использовать максимально возможный набор данных и просто повторно использовать его. Опять же, это сводится к вашим требованиям, то есть вы знаете, какой будет ваш самый большой возможный набор данных? Выделяет ли новый блок памяти когда-либо второй причиной проблем в вашем приложении с течением времени?

Ответ 5

Если среднее из последних значений N x[0].. x[N-1] равно m_1 (x[0] - последнее значение, а x[N-1] рассмотрено последнее значение), тогда среднее значение m_2 значения, отталкивающие все назад одним индексом, и добавление значения x равно

 m_2 = m_1+(x-x[N-1])/N;
 for(i=N-1;i>0;i--) { x[i]=x[i-1]; }
 x[0] = x;

Вместо сохранения значений min/max x_min, x_max следует вместо этого указывать индекс где они находятся в массиве x[i] с i_min и i_max. Тогда их поиск может быть тривиальным иногда, но когда последнее рассматриваемое значение содержит min и max, весь список необходимо отсканировать, чтобы установить новые пределы.

Ответ 6

Существует эффективный способ отслеживания минимального (или максимального) значения в заданном временном окне без необходимости хранить все числа, поступившие в это окно. (Однако в худшем случае все еще требуется хранить все номера, поэтому вам нужно зарезервировать место для всех или принять, что иногда вы можете получить неверные результаты.)

Хитрость заключается только в хранении значений, которые:

• пришли в окно времени и
• меньше (или больше), чем любое последующее значение.

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

При запуске:

• Выделите буфер N-элементов val значений и соответствующий N-элементный буфер time временных меток.
• Пусть imax= 0 (или любое другое значение между 0 и N & минус 1 включительно) и inext= imax. Это означает, что буфер пуст.

При получении нового значения new в момент времени t:

• Пока imax & ne; inext и time[imax] находится за пределами интервала, приращение imax на единицу (по модулю N).
• Пока imax & ne; inext и val[inext-1] & ge; new, декремент inext на один (по модулю N).
• Пусть val[inext]= new и time[inext]= t.
• Если inext & ne; imax-1, приращение inext на единицу (по модулю N); иначе примените условие "полное заполнение буфера" (например, выделите больший буфер, выбросьте исключение или просто проигнорируйте его и примите, что последнее значение было неправильно записано).

Когда запрашивается минимальное значение:

• Пока imax & ne; inext и time[imax] находится за пределами интервала, приращение imax на единицу (по модулю N).
• Если imax & ne; inext, return val[imax]; else вернет ошибку, указывающую, что в течение интервала не было получено никаких значений.

Если полученные значения независимы и идентично распределены (и поступают как процесс Пуассона), я считаю, что можно показать, что среднее количество значений, хранящихся в списке в любой момент времени, равно ln (n + 1), где n - среднее число значений, полученных в течение интервала времени. При n = 50 000, ln (n + 1) & approx; 10,82. Однако следует иметь в виду, что это только среднее значение, и иногда может потребоваться несколько раз больше места.

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

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

При запуске:

• Пусть интервал - это длина интервала времени для среднего значения, а n - количество подинтервалов.
• Пусть dt = интервал /n.
• Выделите буфер n + 1 -элемент sum значений и n + 1 -элементный буфер cnt неотрицательных целых чисел и заполните оба нули.
• Пусть prev имеет любое значение. (Это не имеет значения.)

При получении нового значения new в момент времени t:

• Пусть i= floor (t/dt) mod (n + 1).
• Если i & ne; prev:
  • Вычитайте sum[i] из total и cnt[i] из count.
  • Пусть sum[i]= 0, cnt[i]= 0 и prev= i.
• Добавьте new в sum[i] и увеличьте cnt[i] на единицу.
• Добавьте new в total и увеличьте count на единицу.

Когда среднее значение запрашивается в момент времени t:

• Пусть i= floor (t/dt) mod (n + 1).
• Если i & ne; prev:
  • Вычитайте sum[i] из total и cnt[i] из count.
  • Пусть sum[i]= 0, cnt[i]= 0 и prev= i.
• Пусть j= (i & minus; n) mod (n + 1) = (i +1) mod (n + 1).
• Пусть w= frac (t/dt) = (t/dt) & minus; этаж (t/dt).
• Возврат (total & minus; w & times; sum[j])/(count & минус; w & times; cnt[j]).

Ответ 7

К сожалению, нет. Причина, по которой это невозможно, состоит в том, что вам нужно учитывать только те, которые являются вторыми, что означает, что вам нужно каждый раз переучитывать результат, что означает HUGE Loops.

Если вы хотите рассчитать последние 40 000 номеров или все из них, это будет проще, но поскольку это зависит от времени, вам нужно циклически перебирать весь список каждый раз.

Ответ 8

Есть ли способ сделать это без использования массива или списка (буфера) для хранить прибывающие номера и рассчитывать результаты?

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

Если мне нужно использовать буфер, то какой эффективный способ достичь это?

Вы хотите использовать для этого очередь.

Когда элемент добавляется, если новый max или min соответствующим образом изменяют эти переменные. Вы можете постепенно изменять среднее значение по формуле здесь. Просто возьмите новое значение, минус среднее значение, деленное на новое количество элементов в наборе (то есть размер очереди плюс один), а затем добавьте это к среднему значению.

Тогда у вас будет нечто более или менее похожее:

while(queue.Peek < oneSecondAgo)
{
  oldItem = queue.Peek
  queue.Dequeue();
  if(oldItem == min) //recalculate min
  if(oldItem == max) //recalculate max
  mean += SubtractValueFromMean(oldItem.Value, queue.Count);
}

Чтобы удалить значение из среднего, вы должны просто использовать ту же формулу для добавления, но использовать отрицательный результат, а не положительный... Я думаю. Лучший математик, возможно, должен помочь вам здесь.

Ответ 9

Если числа идут один за другим, используйте секундомер и цикл while, чтобы каждый номер один за другим в течение одной секунды вычислял min, max и avg.

double min = double.MaxValue;
double max = double.MinValue;
double sum = 0;
int count = 0;
double avg;
StopWatch sw = new StopWatch();
sw.Start();
while(sw.Elapsed.TotalSeconds <= 1)
{
   // Get the next number in the stream of numbers
   double d = GetNextNumber();

   // Calculate min
   if(d < min) min = d;
   // Calculate max
   if(d > max) max = d;

   // Calculate avg = sum/ count
   sum += d;
   count++;
}

avg = sum/count;

Затем верните min, max и avg.

Ответ 10

Невозможно обойтись без чисел в буфере или очереди.

Причина этого проста: когда максимальное значение истекает (выпадает из окна с 1 секундой), новый максимум является некоторым другим числом, которое прибыло в течение последней секунды, поэтому вам нужно иметь запись о кандидатах, которые может стать новым максимумом.

Необходимость среднего означает, что все значения имеют эффект, когда они истекают, и ничто не может быть выброшено раньше, чем одна секунда.

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

Использование одного объекта node с двумя следующими и двумя предыдущими указателями (одна пара временно, а другая с точки зрения размера) позволит удалить элементы из обоих списков одновременно, когда элемент истекает из временного списка, у вас есть доступ к указателям для списка размеров, потому что они находятся в одном и том же объекте node.

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

Как было предложено btilly в своем комментарии к сообщению Sam Holder, было бы более эффективно использовать максимальную кучу и кучу минут, чем использовать список, нам снова понадобится использовать один node с указателями для обеих куч и список, поэтому нам не нужно искать элементы для их удаления, и может потребоваться потратить некоторое время на то, как правильно удалить элементы, не находящиеся в верхней части кучи, сохраняя при этом гарантию O (log n ) вставки и удаления.

Ответ 11

В среднем есть 3 случая:

• Ваши числа - целые числа. Сохраняйте общее количество и количество, добавляйте новые значения к сумме, вычесть старые значения из общего числа и делить по мере необходимости. Это просто, потому что вам не нужно беспокоиться о потере точности.
• Ваши цифры - с плавающей запятой, и вам требуется 0 потеря точность: вам нужно будет перебирать весь односекундный список вычислить средний
• Ваши цифры являются плавающей точкой, и вы можете жить с некоторой потерей точность: действовать как для целочисленного среднего значения, выполняя полный пересчет каждые 1000 значений.

Для min и max (только для № 1 и № 3 выше):

• Сохраняйте значения в переменной, индексированной по значению.
• Также сохраняйте значения в двусвязном списке, упорядоченном по времени. Сохраните начало и конец список.
• Удалить из начала списка и добавить к концу список.
• Для каждого нового значения: добавьте его в начало связанного со временем списка. Удалите значения по мере необходимости с конца связанного со временем списка.

По мере добавления и удаления значений в и из связанного списка выполните соответствующие операции в treap. Чтобы получить min и max из treap, просто найдите find_minimum и find_maximum операции в log (n) времени. Когда вы удаляете вещи из правого конца связанного списка в постоянное время, также удаляйте их из treap в log (n) времени.

Treaps может найти свое минимальное значение в log (n) времени, найти максимальное значение в log (n) time и найти произвольное значение в log (n) времени. В общем, чем более разнообразны способы доступа к данным, тем лучше выглядит хорошо округленная структура данных, такая как treap.