Un mio processo di nodo riceve un punto campione ogni mezzo secondo e voglio aggiornare la cronologia di tutti i punti campione che ottengo.
Il grafico dovrebbe essere un array che contiene la cronologia downsampled di tutti i punti da 0 al punto corrente.
In altre parole, la lunghezza massima dell'array dovrebbe essere l
. Se ho ricevuto più punti di campionamento di l
, voglio che l'array di grafici sia una versione scomposta in l
dell'intera cronologia.
Per esprimerlo con il codice (gli esempi sono in javascript ma la domanda è indipendente dal linguaggio):
const CHART_LENGTH = 2048
createChart(CHART_LENGTH)
onReceivePoint = function(p) {
// p can be considered a number
const chart = addPointToChart(p)
// chart is an array representing all the samples received, from 0 to now
console.assert(chart.length <= CHART_LENGTH)
}
Ho già una funzione di downsampling funzionante con array di numeri:
function downsample (arr, density) {
let i, j, p, _i, _len
const downsampled = []
for (i = _i = 0, _len = arr.length; _i < _len; i = ++_i) {
p = arr[i]
j = ~~(i / arr.length * density)
if (downsampled[j] == null) downsampled[j] = 0
downsampled[j] += Math.abs(arr[i] * density / arr.length)
}
return downsampled
}
Un modo banale per farlo ovviamente è salvare tutti i punti che ricevo in un array e applicare la funzione downsample
ogni volta che l'array cresce. Questo funzionerebbe, ma dato che questo pezzo di codice sarebbe stato eseguito in un server, probabilmente per mesi e mesi di fila, alla fine avrebbe reso l'array di supporto crescere così tanto che il processo sarebbe andato fuori memoria.
La domanda è: esiste un algoritmo per costruire l'array di grafici riutilizzando i contenuti precedenti del grafico stesso, per evitare di mantenere una struttura di dati in crescita? In altre parole, esiste una soluzione di complessità della memoria costante a questo problema?
Tieni presente che il grafico deve contenere l'intera cronologia dal punto di esempio n. 0 in qualsiasi momento, pertanto la creazione di grafici degli ultimi n punti non sarebbe accettabile.