Algoritmo per tracciare in modo efficiente il segnale infinito

0

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.

    
posta janesconference 13.09.2016 - 17:41
fonte

0 risposte

Leggi altre domande sui tag