rolling min e rolling max per C++ boost?

Question

Ho un codice che utilizza un accumulatore Boost per tracciare una media attraverso una finestra a rotazione - "media mobile". Oltre alla media mobile, vorrei monitorare il minimo e il massimo su questa stessa finestra a rotazione.

Esiste un modo per calcolare un minimo di rotazione e un massimo di rotazione con un accumulatore Boost? Non vedo un modo ...

Ho provato ad aggiungere tag min e max all'accumulatore usato per rolling_mean, ma questo non mi dà quello che voglio.

typedef accumulator_set<uint32_t, stats<tag::rolling_mean> > rollingMeanAcc_t; 

diventa

typedef accumulator_set<uint32_t, stats<tag::rolling_mean,tag::min,tag::max> > rollingMeanAcc_t; 

Tuttavia, il minimo e massimo disponibile qui sono calcolati sull'intero accumulatore, anziché limitata alla stessa finestra di laminazione come media.

Il Boost documentation dice che min e max sono calcolati attraverso tutti campioni, non limitato a una finestra a rotazione. Non sembrano fornire un modo per limitare o ponderare i campioni.

Vorrei essere in grado di segnalare media/min/max su una finestra a rotazione.

Attualmente sto utilizzando Boost versione 1.48.0. Ho esaminato la documentazione per l'ultima versione (1.54.0) e non vedo un rolling min/max implementato lì.

Ho trovato un modo non Boost per tracciare un sliding window minimum, ma questo non sembra essere quello che voglio. Non voglio rimuovere i valori solo perché sono più grandi/meno del precedente min/max, in quanto ciò renderebbe imprecisa la rolling_mean.

Answer 1

Non penso che un accumulatore possa eseguire un rolling min/max.

Il problema è piuttosto semplice: un accumulatore praticamente per definizione utilizza solo dati O (1) - non memorizza i dati in elaborazione. Può mantenere un minimo o un massimo con i dati O (1), poiché cambia semplicemente il minimo/massimo attuale quando un numero non rientra nell'intervallo del minimo/massimo attuale.

Per una finestra, tuttavia, è necessario essere pronti a fare l'opposto: quando il minuto corrente esce dalla finestra, deve trovare il nuovo minimo - il prossimo numero più piccolo nella finestra. Allo stesso modo per il massimo, ovviamente.

Ora, considerare cosa succede al minimo se (ad esempio) l'input è ordinato. Ogni volta che un oggetto viene rimosso dalla finestra, otteniamo un valore minimo diverso. In altre parole, l'accumulatore dovrebbe memorizzare tutti i dati nella finestra per mantenere correttamente il minimo corrente. Allo stesso modo, per il massimo con l'input ordinato in ordine decrescente.

In breve, non è possibile utilizzare un accumulatore per questo. È necessario memorizzare tutti i dati nella finestra.

Answer 2

Potrebbe esserci un algoritmo più intelligente (in effetti probabilmente lo è), ma in cima alla mia testa, vorrei semplicemente archiviare la finestra in un buffer circolare e calcolare il rolling min/max on-demand. Cache il risultato e imposta un flag dirty quando la finestra cambia. Ciò fornisce un'operazione di accumulo O (1) e un'operazione di estrazione O (1) ammortizzata con il caso peggiore di O (K), dove K è la dimensione della finestra.