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

Question

Программа получает приблизительно 50 000 номеров каждую секунду.

В ЛЮБОЙ данный момент мне нужно рассчитать минимальные, максимальные и средние значения (числа), которые прибыли в последнюю секунду (относительно заданного момента).

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

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

(Обратите внимание, что номера из буфера также должны быть эффективно удалены время от времени)

Answer 1

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

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

2. Когда запрос на average, min или max сделан, цикл через от задней части буфера и начать удаление значений старших чем за одну секунду. Вычитайте из sum и count, как вы идете.

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

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

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

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

Обновление

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

---

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

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

---

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

---

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

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

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

Answer 6

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

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

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

Для этого вам понадобится Очередь.

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

Тогда вы будете иметь что-то более или менее, как это:

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); 
} 

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

Answer 7

Если среднее значение последних 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; 

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

Answer 8

Если числа идут один за другим, то используйте секундомер и цикл 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; 

Затем верните мин., Макс. И сред.

Answer 9

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

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

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

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

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

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

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

Answer 10

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

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

1. прибыли в пределах временного окна, и
2. меньше (или больше), чем любое более позднее значение.

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

При запуске:

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

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

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

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

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

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

---

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

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

При запуске:

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

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

• Пусть i = пол (t/дт) мод (n +1).
• Если i ≠ 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 = пол (t/DT) мод (п +1).
• Если i ≠ prev:
  • Вычесть sum[i] из total и cnt[i] от count.
  • Let sum[i] = 0, cnt[i] = 0, и пусть prev = i.
• Пусть j = (i − п) мод (п +1) = (i + 1) мод (п +1).
• Пусть w = гидроразрыва (t/дт) = (t/DT) − этаж (t/дт).
• Return (total − w × sum[j])/(count − w × cnt[j]).

Answer 11

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

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

Для мин и макс (релевантно только для # 1 и # 3 выше):

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

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

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