sacar que promedio porcentajes para paises más los fechas ellos cuál cuentan contiguas conjunto con como celdas cantidad calificaciones analistas algorithm statistics

algorithm - que - Muestra el promedio de valores recibidos en los últimos X segundos



promedio.si celdas no contiguas (6)

Tengo una clase que distribuye un evento de Éxito y Fracaso y necesito mantener una estadística sobre el número promedio de fallas / número total de eventos en los últimos X segundos de esa clase.

Estaba pensando algo así como utilizar una lista circular vinculada y anexar un nodo de éxito o falla para cada evento. Luego cuente los números de nodos de falla frente a los nodos totales en la lista, pero esto tiene dos inconvenientes principales:

  1. Necesito escalar constantemente el tamaño de la lista hacia arriba / abajo para tener en cuenta el requisito de "últimos X segundos" (la cantidad de eventos por segundo puede cambiar)
  2. Necesito revisar constantemente la lista y contar todos los eventos (potencialmente costosos ya que probablemente tendré cientos de tales eventos por segundo)

¿Alguien sabe de otra forma de calcular los valores promedio de una lista de muestras recibidas en los últimos X segundos?

¿Cuán específicos son sus requisitos? Si se le permite pensar un poco, un simple algoritmo geiger-counter, también conocido como filtro digital de respuesta infinita al impulso (IIR) calcula un "promedio" móvil (dependiendo de cómo se defina "promedio"), tiene un mínimo memoria y solo toma algunas líneas de código.

Debe usar una frecuencia de muestreo (a-la MRTG). Supongamos que solo necesita una precisión de un segundo y para mantener el promedio de los últimos minutos, tendrá una tabla fija de 60 entradas que hace referencia a los últimos 60 segundos (incluida la actual). Y también mantener la entrada global actual.

Cada entrada consiste en un valor promedio y una cantidad de eventos. Cada entrada comienza en 0 para ambos valores.

Cuando recibes un evento nuevo, cambias la entrada actual y la global como esta:

average = ((number * average) + 1) / (number + 1) number = number + 1

En cada intervalo de muestreo, cambia la entrada global utilizando la entrada más antigua:

global.average = ((global.number * global.average) - (oldest.number * oldest.average)) / (global.number - oldest.number) global.number = global.number - oldest.number

Y restablece la entrada más antigua a 0 y comienza a usarla como la actual.

Por lo general, para este tipo de muestreadores hay una cosa adicional que normalmente especifica, y esa es la resolución de la muestra .

En su caso asumiendo su descripción, la resolución de la muestra puede ser de 1 segundo o 1 tilde.

Si la resolución que desea para la muestra es de 1 segundo, aquí hay una proposición de algoritmo que podría funcionar bastante bien.

  • crea una lista vinculada Los nodos de la lista son [timestamp, Success count, Failure count, previousNode]
  • almacenar una referencia al último nodo de la lista como lastNode y una referencia al primer nodo firstNode ( lastNode será la cola de la lista, y el firstNode es el último nodo agregado, la cabeza)
  • mantener en dos variables globales gSuccess, gFail, la suma de éxitos y fracasos en el último marco temporal de X segundos.

Cuando se recibe un nuevo evento:

  • Compare el evento [timestamp] con la marca de timestamp firstNode

    IF (eventTimestamp.TotalSeconds> firstNode.TotalSeconds)

    • Agregue un nuevo nodo a al comienzo de la lista (insertar antes de firsNode) con Succes and Failure count 0.
    • firstNode.Previous = newNode
    • firsNode = newNode;

    TERMINARA SI

    • Incrementar firstNode.Success o firstNode.Failure count por 1
    • * Incrementa gSuccess o gFail en 1

    (después de cada evento agregado) REMOVE_EXPIRED_NODES

  • MIENTRAS (lastNode! = Nil AND curentTime.TotalSeconds - lastNode.TotalSeconds> X)

    • gSuccess - = lastNode.Succes (disminuye gSuccess por nodo para eliminar Count de éxito)
    • gFail - = lastNode.Fail (disminuye gFail por nodo para eliminar Fail count)
    • Eliminar lastNode

    TERMINAR MIENTRAS

obtener gFail y gSuccess siempre debe ir precedido de REMOVE_EXPIRED_NODES.

Las ventajas de este enfoque:

  • Los contadores globales para Fail and Success no se vuelven a calcular de todos los eventos, sino que se agregan sucesos gradualmente incrementados, y se disminuyen cuando se eliminan los nodos de la lista que tienen más de X segundos.

  • usa una resolución de muestra de 1 segundo en lugar de almacenar una lista de todos los eventos (que pueden ser cientos por segundo, lo que garantiza que se realicen un total de 2 operaciones de lista por cada segundo (operaciones de adición y eliminación))

  • independientemente del número de eventos, el recuento de operaciones de lista por segundo en promedio es 2 (1 operación de adición, 1 operación de eliminación)

Sería más efectivo mantener dos listas separadas, una para los éxitos y otra para los fracasos. Las nuevas entradas siempre se anexan al final de la lista (es decir, se ordena aumentando las marcas de tiempo).

Ahora, cuando desee obtener el número de éxitos / fracasos en los últimos n segundos, cree una marca de tiempo para now() - n y trabaje en las listas. Una vez que encuentre una marca de tiempo que sea mayor que este valor, puede eliminar todos los elementos antes de la actual. La longitud de la lista le da el número de éxitos o falla.

Si necesita optimizar, vea si es más efectivo ordenar la lista disminuyendo la marca de tiempo (es decir, anteponiendo nuevos valores) y trabajar la lista hasta que encuentre un elemento que tenga una marca de tiempo más pequeña que su valor de comparación. Descartar esto y todos los siguientes miembros.

Es difícil decir de antemano qué escenario será más efectivo, así que tendrás que probarlo. OTOH si funciona lo suficientemente bien, no hay ninguna razón para optimizar ;-).

mantenerte eventos en una cola . Solo agréguele al final y elimine todos los eventos que sean demasiado antiguos desde el frente. Esto al menos eliminará el problema 1.

Puede usar una cola , que le permita agregar nuevos eventos al final de la cola, y eliminar los eventos caducados desde el inicio de la cola, suponiendo que los eventos se agreguen en orden cronológico. En Java, por ejemplo, puede usar una LinkedList ArrayDeque o una ArrayDeque , ambas implementan la interfaz Queue .

Si los eventos no se agregan en orden cronológico, se podría usar una cola de prioridad . Los elementos se ordenarían por sus marcas de tiempo, y el elemento de mayor prioridad (es decir, el siguiente elemento para su eliminación) sería el que tenga la marca de tiempo más pequeña. En Java, esta estructura de datos es proporcionada por PriorityQueue .

En lugar de contar los eventos periódicamente, podemos mantener dos contadores, uno para el número total de eventos y el otro para la cantidad de eventos exitosos. Estos contadores se actualizarán siempre que agreguemos o eliminemos eventos de la cola.