Quale schema di algo / design devo tenere costantemente aggiornati i dati delle serie temporali limitate?

Question

Quale schema di algo / design devo tenere costantemente aggiornati i dati delle serie temporali limitate?

#1 da (5 voti)
#2 da (1 voti)

4

Sono un programmatore hobbista; mai lavorato professionalmente Non sto cercando nessuno per scrivere codice per me, ma ho bisogno di sapere come affrontare questo problema e, forse, idee per ulteriori ricerche. Questo problema è una conseguenza del progetto scientifico di mio figlio con cui ho voluto giocare.

La linea di fondo è: ho un sensore che alimenta oggetti dati a intervalli irregolari e imprevedibili (temperatura, pressione dell'aria, altre cose). Ogni nuovo "aggiornamento" alimenta un altro oggetto dati con tutte le informazioni pertinenti ... e ogni oggetto ha un timestamp. L'imprevedibilità è il nocciolo del problema e questo non cambierà. Poiché il mio codice raccoglie nuovi oggetti di dati a intervalli irregolari, ho bisogno di eseguire semplici operazioni aritmetiche sugli oggetti dati per gli ultimi n minuti. Devo eseguire queste operazioni aritmetiche in modo continuo su ogni nuovo "aggiornamento" di nuovi dati. Il sensore potrebbe emettere fino a 20 aggiornamenti al secondo ... o meno. L'utilizzo della CPU e della RAM è un problema delicato, ma voglio concentrarmi sul primo approccio al design operativo.

All'inizio pensavo a array o coda circolare, ma non va bene dato che non so quanti oggetti copriranno gli ultimi n minuti.

Successivamente, ho considerato una lista doppiamente collegata. Il problema con questo approccio è che dovrà consumare una CPU pesante ripetendo sull'intero elenco ogni nuovo "aggiornamento" al fine di rimuovere gli oggetti obsoleti dalla lista o dovrà consumare molta ram se non rimuovo i vecchi oggetti dalla lista ogni volta.

Mi chiedo quali schemi di progettazione (e strutture dati) possano soddisfare questo problema e quali altri elementi posso ricercare per saperne di più per risolvere questo problema.

Capisco che non sto dando molte informazioni qui, ma voglio rimanere semplice e credo di aver dato il succo del problema.

Apprezzo davvero qualsiasi aiuto. A proposito, sto usando C # e CLR per ora. Python potrebbe essere un'opzione migliore poiché questa è data-science'ish. Credo di poter scrivere e / o consumare una libreria / classe Python. Non sono molto fluente con Python.

UPDATE - 8/30

Ho pensato in risposta alle risposte di tutti - che sono grandi e apprezzo molto.

Sto pensando, utilizzare la classe ConcurrentQueue dalla libreria .NET come struttura dati principale. Non sapevo che fosse ridimensionabile fino a quando @amon non l'ha menzionato. Una coda sembra perfetta perché posso scorrere dalla coda della coda e dare un'occhiata al prossimo timestamp, usando un ciclo while (cioè, mentre il prossimo "peek" è al di fuori della n -minute time window allora dequeue). Poiché tutti gli oggetti dati devono necessariamente essere accodati in ordine temporale, questo dovrebbe funzionare se la testa è sempre la più vecchia e coda è sempre l'oggetto dati più recente. Ciò attenua la mia preoccupazione per l'utilizzo della CPU nel mantenere la coda "corrente" (cioè, contenente solo oggetti dati all'interno della finestra temporale n ).

Riguardo all'aggiornamento della vista dell'utente e al mitigamento dell'uso della CPU, potrei aggiornare la vista ogni x secondi come menzionato da @JohnWu. Probabilmente userò un Timer per Thread che aggiornerebbe gli oggetti dati sottostanti la vista dell'utente su un thread separato a intervalli fissi.

Se questo usa troppa CPU, indagherò sul salvataggio di pezzi di stato come discusso da @ErikEidt. Ma dal momento che non sto calcolando solo le medie, sarà un po 'complicato. Spero che quanto sopra abbia a che fare con problemi di risorse.

Volevo solo dire grazie per l'intuizione.

Il prossimo passo è imparare di più sul threading.

c# design-patterns python clr design-principles

posta LeeRoy 29.08.2017 - 00:59

fonte

2 risposte

Leggi altre domande sui tag c# design-patterns python clr design-principles

In che modo un database XML è diverso da (non è la specializzazione di) un database grafico? Identifica i metodi su OOP

score 5 · Answer 1

Cose a cui pensare:

Non presupporre automaticamente che un elenco collegato a doppio di 20 voci al secondo per 60 minuti (ad esempio 20x60x60 = 72.000) tasserà necessariamente la tua CPU a meno che tu non l'abbia provato.

Alcuni algoritmi potrebbero funzionare bene per te. Ad esempio, se si calcola una media, è necessario solo sottrarre / annullare i valori che sono invecchiati e inserire / rendere conto di quelli nuovi. Non è sempre necessario eseguire iterazioni sull'intero elenco di valori nella finestra temporale corrente.

Quindi, supponiamo che tu voglia calcolare il tempo medio nel tempo e che stai utilizzando un elenco collegato di valori di timestamp.

Oltre la lista stessa, mantieni due pezzi di stato per la media corrente, entrambi inizialmente zero, uno per la somma e uno per il conteggio.

Su nuovi dati in arrivo, aggiungi un elemento alla fine dell'elenco, regolando anche la somma per accumulare il nuovo valore temporaneo e incrementando il conteggio.

Quindi invecchi i vecchi valori passando dalla parte iniziale (vecchia) della lista fermandoli quando raggiungi una voce che non dovrebbe ancora essere invecchiata. Per ogni elemento che è invecchiato, rimuoverlo dall'elenco e sottrarre il suo valore temp dalla somma e decrementare il conteggio. (Per maggiore velocità e complessità, è possibile evitare di rimuovere ogni singolo elemento invecchiato e correggere la testa dell'elenco solo una volta, dopo aver trovato il nuovo inizio.)

Il calcolo è in gran parte completo ora e la media è la somma divisa per il conteggio. Esegui l'output fino all'oggetto successivo lungo la linea e attendi ulteriori aggiornamenti.

Il risultato netto è che quando arrivano nuovi dati, gestisci solo i nuovi dati e tutte le vecchie cose da invecchiare, ma non il resto dell'elenco, che è forse la maggior parte dell'elenco.

Potresti scoprire che il buffering del calcolo è appropriato, ad esempio, quando ricevi nuovi dati, pianifica un aggiornamento per un decimo di secondo da ora. Quindi tutti i valori ricevuti nel frattempo potrebbero essere elaborati tutti insieme.

Se sei preoccupato per la garbage collection per l'elenco, sposta le voci obsolete / rimosse in una lista libera separata e riutilizzate preferibilmente quelle per prime invece di allocare nuovi elementi per conservare gli aggiornamenti.

score 1 · Answer 2

Un approccio possibile, praticamente in qualsiasi linguaggio che li supporti, per usare una coda a doppio attacco. I metodi richiesti sono left e right push e pop più accesso in posizione, anche se se l'accesso non è possibile, c'è un problema.

Il mio approccio sarebbe:

Ogni volta che arriva una nuova lettura, spingerla, con i dati dell'ora su una estremità della coda e calcolare il timestamp più vecchio che è ora valido, (cioè Nuovo timestamp meno 300 secondi) .
Valori pop dall'altra parte della coda fino a quando il timestamp è maggiore o uguale alla soglia. Spingi l'ultimo valore sulla stessa estremità da cui proviene.
Chiama il codice di generazione del riepilogo in coda - questo è il posto dove l'accesso è utile altrimenti dovrai rollare la coda, cioè registrare il timestamp ad una estremità scoppiando, aggiungere il valore nel sommario e spingerlo a l'altra estremità poi ripeti fino a quando non torni a quella.

Se la tua velocità di arrivo dei dati è potenzialmente più veloce del tuo codice per quanto sopra, potresti dover disporre di una coda in entrata dove i valori vengono trattenuti fino a quando non vengono aggiunti come blocco.