Example of average over the last X seconds

Question

I have a class that dispatches a Success and Failure event, and I need to maintain statistics on the average number of failures / total number of events for the last X seconds of this class.

I thought of something like using a circular linked list and adding node success or failure for each event. Then count the number of failure nodes compared to the common nodes in the list, but this has two main drawbacks:

• I need to constantly scale the size of the list up / down to accommodate the “last X second” requirement (the number of events per second may vary).
• I need to constantly iterate over the list and count all events (potentially expensive, since I will probably have 100 such events per second)

Does anyone know of a different way of calculating averages from a list of samples obtained in the last X seconds?

Answer 1

You must use the sampling rate (a-la MRTG). Let's say you only need one second of accuracy and to maintain the average over the last minute, you will have a fixed table of 60 records relating to the past 60 seconds (including the present). And also save the current global record.

Each record consists of an average value and the number of events. Each entry starts at 0 for both values.

When you receive a new event, you change the current and global record as follows:

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

, :

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

reset 0 .

Answer 2

queue, , , . , Java LinkedList ArrayDeque, Queue.

, . , (.. ) , . Java PriorityQueue.

, , , , . , .

Answer 3

Queue. , . , , 1.

Answer 4

, , .

, , 1 , 1 .

, , 1 , , .

• . [ , , , Node]
• node lastNode, node firstNode (lastNode , firstNode - node, )
• gSuccess, gFail, X .

:

• [timestamp] firstNode timestamp

  IF (eventTimestamp.TotalSeconds > firstNode.TotalSeconds)

  • node a ( firsNode) Succes Failure count 0.
  • firstNode.Previous = newNode
  • firsNode = newNode;

  END IF

  • firstNode.Success firstNode.Failure count by 1
  • * gSuccess gFail 1

  ( ) REMOVE_EXPIRED_NODES

• WHILE (lastNode!= nil AND curentTime.TotalSeconds - lastNode.TotalSeconds > X)

  • gSuccess - = lastNode.Succes( gSuccess node, ).
  • gFail - = lastNode.Fail( gFail node, ).
  • lastNode

  END WHILE

gFail gSuccess REMOVE_EXPIRED_NODES.

:

• Fail Success , , X .

• 1 ( , 2 ( + ))

• , 2 (1 , 1 )

Answer 5

? , , , (IIR), "" ( , "" ), .

Answer 6

: . (.. ).

, / n , now() - n . , , . .

, , , (, ) , , , . .

, , . OTOH, , ; -).