testdome - test c#

Cálculo rápido de min, max y promedio de números entrantes

Question

El programa recibe aproximadamente 50,000 números por segundo.

En CUALQUIER momento dado, necesito calcular el mínimo, máximo y promedio de los valores (números) que llegaron en el último segundo (con respecto al momento dado).

¿Hay alguna manera de hacer esto sin usar una matriz o lista (buffer) para almacenar los números que llegan y calcular los resultados?

Si necesito usar un buffer, ¿cuál sería la forma más eficiente de lograr esto?

(Tenga en cuenta que los números del búfer también deben eliminarse de vez en cuando de manera eficiente)

Answer 1

¿Hay alguna manera de hacer esto sin usar una matriz o lista (buffer) para almacenar los números que llegan y calcular los resultados?

No. Es probablemente imposible hacer esto sin almacenar la información, como lo dijiste. Sin embargo, podrías modificar un poco los requisitos para deshacerte de la necesidad de un buffer.

Si necesito usar un buffer, ¿cuál sería la forma más eficiente de lograr esto?

Querrá usar una cola para esto.

Cuando se agrega un artículo, si es el nuevo máximo o mínimo, ajuste esas variables en consecuencia. Puede ajustar incrementalmente la media a través de la fórmula here . Simplemente tome el nuevo valor, menos la media, dividido por la nueva cantidad de elementos en el conjunto (es decir, el tamaño de la cola más uno) y luego agréguelo a la media anterior.

Entonces tendrás algo más o menos así:

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

Para eliminar el valor del promedio, debería poder usar la misma fórmula para agregar, pero use el valor negativo del valor en lugar del positivo ... Creo. Un mejor matemático puede necesitar ayudarte aquí.

Answer 2

@DanRedux es correcto; tendrá que calcularlos cada vez porque su entrada está cambiando. Ahora, es posible que prefiera calcular estos números a pedido o por adelantado (es decir, cuando obtiene un nuevo lote) según la frecuencia con que se necesiten los resultados.

Por ejemplo, si su caso de uso promedio sondea para estas estadísticas cada ~ 30 segundos, entonces probablemente solo las calcule a demanda y almacena el resultado en caché hasta que entre un nuevo lote. Sin embargo, realmente todo se reduce a su escenario de uso.

En cuanto a cómo almacenarlos, realmente no tienes opción, ¿verdad? Necesita espacio para todos los 50,000 números en la memoria. Entonces ... necesitas un trozo de memoria lo suficientemente grande como para sostenerlos. Para evitar asignar constantemente 2 KB cada vez que aparece una nueva secuencia, probablemente sea mejor que declare una matriz lo suficientemente grande como para mantener el mayor conjunto de datos posible y simplemente reutilizarlo. Una vez más, esto se reduce a sus requisitos, es decir, ¿sabe cuál será su conjunto de datos más grande posible? ¿La asignación de un nuevo trozo de memoria causa problemas en su aplicación a lo largo del tiempo?

Answer 3

Aquí hay un algoritmo que de alguna manera funcionará para ahorrar eficiencia en ciertos casos:

1. A medida que entran los eventos, búrelos por completo y calcule una sum ejecución, count , min , max (trivial).

2. Cuando se realiza una solicitud de average , min o max , recorra desde la parte posterior del búfer y comience a eliminar valores anteriores a un segundo. Reste de la sum y count sobre la marcha.

   • Si los valores son todos superiores a min , puede mantener su min . Si los valores están por debajo del max , puede mantener su max . En este escenario, tiene average , min y max actualizados de manera eficiente.

   • Si los valores están por debajo del valor max o min , deberá recorrer el resto del conjunto y volver a calcularlo.

3. Haga el paso dos una vez por segundo también para que el buffer no se llene demasiado. Este código podría realizarse en cada inserción de memoria intermedia también, o donde sea que tenga sentido.

La mejor estructura para este tipo de trabajo es un buffer circular, para evitar asignaciones de memoria y GC en el camino. Debe ser lo suficientemente grande como para cubrir el peor escenario posible para el tamaño del mensaje por segundo.

Actualizaciones

Según el escenario de uso, otra cosa sería ejecutar el algoritmo anterior, pero en trozos de 10 x 100 ms en lugar de 1 x 1000ms. Es decir, mantenga el mínimo, máximo, suma y cuente en esos 10 fragmentos. Luego, cuando llegue a un escenario de ''invalidación'', generalmente solo necesita mirar los últimos 100 ms de datos o un pase rápido a través del mínimo y el máximo de los otros 9 fragmentos.

@ ja72 proporcionó una excelente idea para ahorrar al encontrar los valores mínimo y máximo si se invalidan:

En lugar de mantener los valores mínimos / máximos x_min, x_max, mantenga en su lugar el índice de ubicación en la matriz x [i] con i_min e i_max. Luego, encontrarlos puede ser trivial a veces, pero cuando el último valor considerado contiene el mínimo y el máximo, se debe escanear toda la lista para establecer los nuevos límites.

Sam Holder tuvo otra buena idea en los comentarios: mantenga una matriz paralela que siempre esté ordenada, esto le permite separar los números de la parte superior o inferior para encontrar nuevos mínimos y máximos más fácilmente. Sin embargo, la velocidad de inserción aquí se ve comprometida un poco (debe mantenerse en orden).

En definitiva , la elección correcta dependerá de las características de uso del programa. ¿Con qué frecuencia se leerán los valores frente a la frecuencia con que se insertan?

Answer 4

Existe una manera eficiente de realizar un seguimiento del valor mínimo (o máximo) dentro de una ventana de tiempo determinada sin tener que almacenar todos los números que han llegado dentro de esa ventana. (Sin embargo, el peor de los casos todavía requiere almacenar todos los números, por lo que debe reservar espacio para todos ellos o aceptar que a veces puede obtener resultados incorrectos).

El truco es almacenar valores que:

1. han llegado dentro de la ventana de tiempo, y
2. son más pequeños (o más grandes) que cualquier otro valor posterior.

Una estructura de datos adecuada para implementar esto es un simple buffer circular almacenando valores y sus tiempos de llegada. Deberá mantener dos índices en el búfer. Aquí hay una descripción simple en inglés del algoritmo:

Al inicio:

• Asigne un val de valores de buffer N -element y un time de buffer N -element correspondiente de timestamps.
• Deje imax = 0 (o cualquier otro valor entre 0 y N -1 inclusive) y deje inext = imax . Esto indica que el búfer está actualmente vacío.

Cuando se recibe un nuevo valor new en el tiempo t :

• Mientras imax ≠ inext y el time[imax] están fuera del intervalo, incremente imax en uno (módulo N ).
• Mientras imax ≠ inext y val[inext-1] ≥ new , disminuya inext en uno (módulo N ).
• Deje val[inext] = new y time[inext] = t .
• Si inext ≠ imax-1 , incremente inext en uno (módulo N ); de lo contrario, trate la condición de "búfer completo" de forma adecuada (por ejemplo, asigne un búfer más grande, genere una excepción o simplemente ignórelo y acepte que el último valor no se registró correctamente).

Cuando se solicita el valor mínimo:

• Mientras imax ≠ inext y el time[imax] están fuera del intervalo, incremente imax en uno (módulo N ).
• Si imax ≠ inext , devuelve val[imax] ; si no, devuelve un error que indica que no se han recibido valores dentro del intervalo de tiempo.

Si los valores recibidos son independientes e idénticamente distribuidos (y llegan como un proceso de Poisson), creo que se puede demostrar que el número promedio de valores almacenados en la lista en cualquier momento dado es ln ( n +1), donde n es el promedio de valores recibidos dentro del intervalo de tiempo. Para n = 50,000, ln ( n +1) ≈ 10.82. Sin embargo, uno debe tener en cuenta que esto es solo el promedio, y que varias veces puede requerirse más espacio.

Para el promedio, el mismo truco desafortunadamente no funciona. Si es posible, puede cambiar a un promedio exponencialmente móvil , que puede rastrearse fácilmente usando muy poco espacio (solo un número para el promedio y un sello de tiempo que indica cuándo fue actualizado por última vez).

Si eso no es posible, pero está dispuesto a aceptar una pequeña cantidad de suavizado en los valores promedio, podría calcular un promedio en, digamos, cada milisegundo. De esta forma, siempre que se solicite un promedio de los valores en el último segundo, puede tomar un promedio de los últimos promedios de 1001 milisegundos, ponderando el más antiguo y el más nuevo según la cantidad de esos milisegundos dentro del intervalo:

Al inicio:

• Permita que el intervalo sea ​​la longitud del intervalo de tiempo para promediar, y sea n el número de subintervalos.
• Deje dt = intervalo / n .
• Asigne una sum de valores del buffer n + 1 de valores y un buffer n- 1 cnt de enteros no negativos, y llene ambos con ceros.
• Deja que tenga valor. (Realmente no importa)

Cuando se recibe un nuevo valor new en el tiempo t :

• Deje que i = piso ( t / dt ) mod ( n +1).
• Si i ≠ prev :
  • Reste la sum[i] del total y cnt[i] de la count .
  • Deje sum[i] = 0, cnt[i] = 0 y deje prev = i .
• Agregue new a sum[i] e incremente cnt[i] en uno.
• Agregue new al total e incremente el count en uno.

Cuando el valor promedio se solicita en el tiempo t :

• Deje que i = piso ( t / dt ) mod ( n +1).
• Si i ≠ prev :
  • Reste la sum[i] del total y cnt[i] de la count .
  • Deje sum[i] = 0, cnt[i] = 0 y deje prev = i .
• Sea j = ( i - n ) mod ( n +1) = ( i +1) mod ( n +1).
• Deje w = frac ( t / dt ) = ( t / dt ) - piso ( t / dt ).
• Retorno ( total - w × sum[j] ) / ( count - w × cnt[j] ).

Answer 5

Lamentablemente, no hay. La razón por la que no es posible se debe a que solo debe tener en cuenta los que tienen un segundo de antigüedad, lo que significa que debe volver a calcular el resultado cada vez, lo que significa bucles ENORMES.

Si quisiera calcular los últimos 40,000 números, o todos ellos, sería más fácil, pero debido a que se basa en el tiempo, tiene que recorrer la lista completa cada vez.

Answer 6

No es posible prescindir de los números en un buffer o cola.

El motivo es simple: cuando expira un valor máximo (se sale de la ventana de 1 segundo), el nuevo máximo es otro número que llegó en el último segundo, por lo que debe tener un registro de los candidatos que podrían convertirse en el nuevo máximo.

Necesitar el promedio significa que todos los valores tienen un efecto cuando caducan, y no se puede descartar nada antes de que tenga un segundo de antigüedad.

La sugerencia de Sam Holder de utilizar una cola es buena, aunque es probable que necesite una especializada que pueda mantener su lista en dos órdenes simultáneamente: el orden en que se recibieron los números (hora de llegada) y ordenados de máximo a mínimo .

El uso de un objeto de nodo único con dos punteros seguidos y dos anteriores (un par temporalmente, y el otro en términos de tamaño) permitiría eliminar elementos de ambas listas simultáneamente, cuando un elemento caduca de la lista temporal, tiene acceso a los punteros para la lista de tamaños, porque están en el mismo objeto nodo.

El promedio se puede mantener manteniendo un total acumulado y un recuento continuo, restando elementos a medida que se eliminan y agregándolos a medida que se crean, por lo que no es necesario iterar sobre toda la lista cada vez para calcular el promedio.

Como se sugirió sutilmente en su comentario sobre la publicación de Sam Holder, sería más eficiente usar un montón máximo y un montón mínimo que usar una lista, nuevamente necesitaríamos usar un solo nodo con punteros para ambos montones y la lista, por lo tanto no tenemos que buscar elementos para eliminarlos, y puede ser necesario dedicar algún tiempo a considerar cómo eliminar elementos que no están en la parte superior del montón, manteniendo la garantía de las inserciones y eliminaciones de O (log n).

Answer 7

Para promedio, hay 3 casos a considerar:

1. Tus números son enteros. Mantenga un total acumulado y cuente, agregue nuevos valores al total, reste los valores antiguos del total y divida por el recuento según sea necesario. Esto es simple porque no tiene que preocuparse por la pérdida de precisión.
2. Sus números son coma flotante y requiere 0 pérdida de precisión: deberá iterar en toda la lista de un segundo para calcular un promedio
3. Sus números son coma flotante y puede vivir con cierta pérdida de precisión: opere como en el promedio entero, haciendo un recálculo completo cada 1000 valores más o menos.

Para min y max (solo relevante para # 1 y # 3 arriba):

• Mantenga los valores en un truco indexados por valor.
• También mantenga los valores en una lista doblemente vinculada ordenada por tiempo. Guarde el principio y el final de la lista.
• Quítelo del principio de la lista y agréguelo al final de la lista.
• Para cada valor nuevo: agréguelo al principio de la lista vinculada por tiempo. Elimine los valores según sea necesario desde el final de la lista vinculada por tiempo.

A medida que agrega y elimina valores hacia y desde la lista vinculada, realice las operaciones correspondientes en el tratamiento. Para obtener un mínimo y un máximo del tratamiento, simplemente busque las operaciones find_minimum y find_maximum en tiempo log (n). Cuando elimine elementos del extremo derecho de la lista vinculada en tiempo constante, también elimínelos del registro en tiempo de registro (n).

Los Treaps pueden encontrar su valor mínimo en tiempo de registro (n), encontrar su valor máximo en tiempo de registro (n) y encontrar un valor arbitrario en tiempo de registro (n). En general, cuanto más diferentes sean las formas en que necesite acceder a sus datos, mejor se verá una estructura de datos bien redondeada, como una trampa.

Answer 8

Si el promedio de los últimos valores N x[0] ... x[N-1] es m_1 ( x[0] es el último valor, x[N-1] el último valor considerado), entonces el promedio m_2 del valores empujando todo atrás por un índice y agregando el valor x es

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

En lugar de mantener los valores x_min / máximos x_min , x_min , mantenga en su lugar el índice de ubicación en la matriz x[i] con i_min e i_max . Luego, encontrarlos puede ser trivial a veces, pero cuando el último valor considerado contiene el mínimo y el máximo, se debe escanear toda la lista para establecer los nuevos límites.

Answer 9

Si los números vienen uno tras otro, use un cronómetro y un ciclo while para obtener cada número uno por uno durante un segundo y calcule min, max y 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;

A continuación, devuelve min, max y avg.

Answer 10

Utilice un buffer circular con cada elemento que tenga marca de tiempo y datos, teniendo la cantidad máxima de elementos por segundo como el tamaño del buffer circular.

A medida que cada elemento se inserta en la cabeza del búfer, verifique la caducidad en el otro lado del búfer, elimine el elemento.

Si el elemento eliminado es mínimo o máximo, tendrá que calcular nuevos min / max. Si no es así, actualizará min / max según las nuevas llegadas.

Para la media, mantén el total, mantén la cuenta y divide.

Answer 11

no puedes mantener una cola con tus números y sus tiempos de llegada, junto con los valores máximos y mínimos actuales en la cola (probablemente necesitarás contar el número de valores al mismo mínimo / máximo) y el valor total de todos números en la cola y recuento de elementos.

Luego, cuando llegue un número, agréguelo a la cola y ajuste el mínimo / máximo / valor y el recuento. Luego observe el otro extremo de la cola y elimine todos los elementos que no estén dentro de 1 segundo de la llegada del último número, y vuelva a ajustar el valor máximo / mínimo / recuento / total.

Entonces no es necesario que calcule nada en un instante, simplemente devuelva el material calculado previamente (es decir, lea el valor actual de min / max o total / count)

Como @yaman señaló que no se puede retener solo el mínimo y el máximo, como cuando se elimina uno, es posible que no se conozca el nuevo. en este caso, probablemente mantendría una segunda copia de todos los números en la lista, pero en lugar de ordenarla por el tiempo de llegada, ordenaría por valor. Luego, simplemente agrega y elimina cada número de esta lista, de modo que siempre sabrá los valores máximo y mínimo. Esto le ahorra tener que escanear todos los elementos en el búfer para encontrar el nuevo máximo / mínimo, a expensas de mantener 2 copias, pero las actualizaciones de esta lista deben ser baratas, como ya está ordenado.