Speicher-effizientes Downsampling (Diagramm) eines wachsenden Arrays

Question

Ein Knotenprozess von mir erhält einen Abtastpunkt alle halbe Sekunde, und ich möchte das Verlaufsdiagramm aller Sample-Punkte aktualisieren, die ich erhalte. Das Diagramm sollte ein Array sein, das die Downsampling-Historie aller Punkte von 0 bis zum aktuellen Punkt enthält. Mit anderen Worten, die maximale Länge des Arrays sollte l sein. Wenn ich mehr Beispielpunkte als l empfange, möchte ich, dass das Diagramm-Array eine Downsample-to-l Version der gesamten Geschichte ist.

Um es mit dem Code ausdrücken:

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) 
} 

Ich habe bereits eine Arbeit mit Zahlen-Arrays Abwärtsabtastens Funktion:

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 
} 

Eine triviale Weise, dies zu tun offenbar die Punkte alles, was ich bekommen würde, Speichern in ein Array und wenden Sie die Funktion downsample immer wenn das Array wächst. Das würde funktionieren, aber da dieses Stück Code in einem Server laufen würde, möglicherweise für Monate und Monate in Folge, würde es schließlich dazu führen, dass das unterstützende Array so stark anwächst, dass der Prozess nicht mehr genügend Speicher hat.

Die Frage ist: Gibt es eine Möglichkeit, das Diagramm-Array zu konstruieren, die den vorherigen Inhalt des Diagramms selbst wieder verwendet, um zu vermeiden, dass eine wachsende Datenstruktur beibehalten wird? Mit anderen Worten, gibt es eine konstante Speicherkomplexitätslösung für dieses Problem?

Bitte beachten Sie, dass das Diagramm die gesamte Historie seit Beispielpunkt # 0 in jedem Moment enthalten muss, so dass das Chartieren der letzten n Punkte nicht akzeptabel wäre.

Answer 1

Der einzige Vorgang, bei dem die Daten nicht verzerrt werden und der mehrfach verwendet werden kann, ist die Aggregation einer ganzen Zahl benachbarter Proben. Wahrscheinlich möchten Sie 2.

Genauer gesagt: Wenn Sie feststellen, dass das Hinzufügen einer neuen Probe die Array-Grenzen überschreitet, gehen Sie folgendermaßen vor: Beginnen Sie am Anfang des Arrays und durchschnittlich zwei nachfolgende Proben. Dies reduziert die Array-Größe um 2 und Sie haben Platz, um neue Samples hinzuzufügen. Dabei sollten Sie die aktuelle Clustergröße c (die Anzahl der Samples, die einen Eintrag im Array ausmachen) im Auge behalten. Du fängst mit einem an. Jede Reduktion multipliziert die Clustergröße mit zwei.

Jetzt ist das Problem, dass Sie nicht mehr neue Proben direkt zum Array hinzufügen können, weil sie einen völlig anderen Maßstab haben. Stattdessen sollten Sie die nächsten c Stichproben zu einem neuen Eintrag berechnen. Es stellt sich heraus, dass es ausreicht, die Anzahl der Abtastwerte n im aktuellen Cluster zu speichern, um dies zu tun. Wenn Sie also ein neues Beispiel s hinzufügen, würden Sie Folgendes tun.

n++ 
if n = 1 
    append s to array 
else   
    //update the average 
    last array element += (s - last array element)/n 
if n = c 
    n = 0 //start a new cluster 

So ist die Erinnerung, die Sie tatsächlich benötigen die folgenden:

• die Geschichte Array mit vorgegebener Länge
• die Anzahl der Elemente in der Geschichte Array
• die aktuelle Clustergröße c
• Die Anzahl der Elemente im aktuellen Cluster n

Die Größe des zusätzlichen Speichers hängt nicht von der Gesamtzahl der Proben ab, daher O(1).