Calcolo del numero di messaggi al secondo in una finestra a rotazione?

Question

I messaggi arrivano nel mio programma con una risoluzione in millisecondi (da zero a un paio di centinaia di messaggi al millisecondo).

Mi piacerebbe fare qualche analisi. In particolare, voglio mantenere più finestre di rotolamento dei conti dei messaggi, aggiornati come messaggi sono disponibili in. Ad esempio,

• di messaggi nella all'ultimo secondo
• # dei messaggi in last minute
• # dei messaggi in ultima mezz'ora diviso di messaggi nella ultima ora

non posso mantenere un semplice conteggio come "1.017 messaggi in all'ultimo secondo", dal momento che non si sa quando un messaggio è più vecchio di 1 secondo e quindi non dovrebbe più essere nel conteggio ...

Ho pensato di mantenere una coda di tutti i messaggi, cercando il messaggio più giovane che è più vecchio di un secondo, e deducendo il conteggio dal indice. Tuttavia, sembra che sarebbe troppo lento, e mangerebbe un sacco di memoria.

Cosa posso fare per tenere traccia di questi conteggi nel mio programma in modo da poter ottenere in modo efficiente questi valori in tempo reale?

Answer 1

Questo è più semplice gestito da un buffer ciclico.

Un buffer ciclico ha un numero fisso di elementi e un puntatore ad esso. È possibile aggiungere un elemento al buffer e, quando lo si fa, si incrementa il puntatore all'elemento successivo. Se superi il buffer a lunghezza fissa, inizi dall'inizio. È un modo efficiente in termini di tempo e spazio per memorizzare gli "ultimi N" articoli.

Ora nel tuo caso potresti avere un buffer ciclico di 1.000 contatori, ognuno dei quali contando il numero di messaggi durante un millisecondo. L'aggiunta di tutti i 1.000 contatori ti dà il conteggio totale durante l'ultimo secondo.Ovviamente è possibile ottimizzare la parte di reporting aggiornando in modo incrementale il conteggio, ovvero deducendo il conteggio del numero che si sovrascrive quando si inserisce e quindi si aggiunge il nuovo numero.

Si può quindi avere un altro buffer ciclico che ha 60 slot e conta il numero aggregato di messaggi in interi secondi; una volta al secondo, si prende il conteggio totale del buffer millisecondo e scrivere il conteggio al buffer avere la risoluzione di secondi, ecc

pseudocodice Qui C-like:

int msecbuf[1000]; // initialized with zeroes 
int secbuf[60]; // ditto 
int msecptr = 0, secptr = 0; 
int count = 0; 
int msec_total_ctr = 0; 
void msg_received() { count++; } 
void every_msec() { 
    msec_total_ctr -= msecbuf[msecptr]; 
    msecbuf[msecptr] = count; 
    msec_total_ctr += msecbuf[msecptr]; 
    count = 0; 
    msecptr = (msecptr + 1) % 1000; 
} 
void every_sec() { 
    secbuf[secptr] = msec_total_ctr; 
    secptr = (secptr + 1) % 60; 
} 

Answer 2

Ho pensato di mantenere una coda di tutti i messaggi, cercando il messaggio più giovane che è più vecchio di un secondo e deducendo il conteggio dall'indice. Tuttavia, sembra che sarebbe troppo lento, e mangerebbe un sacco di memoria.

Un'idea migliore sarebbe mantenere un elenco collegato dei messaggi, aggiungendo nuovi messaggi alla testa (con un timestamp) e spuntandoli dalla coda mentre scadono. O anche non farli scoppiare - basta tenere un puntatore al messaggio più vecchio che è arrivato nel tempo desiderato, e avanzarlo verso la testa quando scade quel messaggio (questo ti permette di tenere traccia dei tempi di moltiplicazione con una lista).

È possibile calcolare il conteggio quando necessario camminando dalla coda alla testa, o semplicemente memorizzare il conteggio separatamente, incrementandolo ogni volta che si aggiunge un valore alla testa e diminuendolo quando si avanza la coda.

Answer 3

Si desidera exponential smoothing, altrimenti noto come media mobile ponderata esponenziale. Prendi un EWMA del tempo dall'arrivo dell'ultimo messaggio e poi dividi quel tempo in un secondo. È possibile eseguire diversi di questi con pesi diversi per coprire intervalli di tempo più lunghi in modo efficace. In effetti, stai usando una finestra infinitamente lunga, quindi non devi preoccuparti dei dati in scadenza; i pesi riducenti lo fanno per te.

Answer 4

La finestra di visualizzazione a rotazione può solo aggiorna così velocemente, diciamo che vuoi aggiornarlo 10 volte al secondo, quindi per 1 secondo di dati, avrai bisogno di 10 valori. Ogni valore conterrebbe il numero di messaggi visualizzati in quell'1/10 di secondo. Consente di chiamare questi bin di valori, ogni contenitore contiene 1/10 di un secondo di dati. Ogni 100 millisecondi, uno dei bin viene scartato e un nuovo bin è impostato sul numero di messaggi che sono stati visualizzati in quei 100 millisecondi.

Avresti bisogno di un array di contenitori da 36 K per contenere informazioni utili per un'ora sulla velocità dei messaggi se si desidera mantenere una precisione di 1/10 di secondo per l'intera ora. Ma sembra eccessivo.

Ma penso che sarebbe più ragionevole avere la precisione mentre l'intervallo temporale aumenta.

Forse si mantengono 1 secondo di dati accurati a 100 millisecondi, 1 minuto di dati accurati al secondo, 1 ora di dati accurati al minuto e così via.

Answer 5

Per l'ultimo millisecordo, mantenere il conteggio. Quando la slice millisecord passa a quella successiva, reimpostare il conteggio e aggiungere il conteggio a un array di buffer a rotazione millisecondo. Se mantieni questo cummulativo, puoi estrarre il numero di messaggi al secondo con una quantità fissa di memoria.

Quando una porzione di 0,1 secondi (o qualche altro piccolo valore vicino a 1 minuto) viene eseguita, riassumere gli ultimi 0,1 * 1000 elementi dall'array di buffer a rotazione e posizionarli nel buffer di rotolamento successivo. In questo modo si mantiene il buffer di laminazione millisecord piccolo (1000 articoli per la ricerca massima 1s) e anche il buffer per la ricerca al minuto (600 articoli).

È possibile eseguire il trucco successivo per interi minuti di intervalli di 0,1 minuti. Tutte le domande poste possono essere interrogate sommando (o usando cummulativo, sottraendo due valori) alcuni numeri interi.

L'unico svantaggio è che l'ultimo valore sec cambia ogni ms e il valore minuto solo ogni 0,1 secondi e il valore dell'ora (e le derivate con il% nell'ultima mezz'ora) ogni 0,1 minuti. Ma almeno tieni a bada l'uso della memoria.