Effiziente Algorithmus- / Datenstruktur zur Berechnung gleitender Durchschnitte

9

Derzeit entwickle ich ein grafisches LCD-System zur Anzeige von Temperaturen, Durchflüssen, Spannungen, Leistung und Energie in einem Wärmepumpensystem. Die Verwendung eines grafischen LCD bedeutet, dass die Hälfte meines SRAM und ~ 75% meines Blitzes von einem Bildschirmpuffer und Zeichenfolgen verbraucht wurden.

Ich zeige derzeit Min / Max / Durchschnittswerte für Energie an. Um Mitternacht, wenn der Tageswert zurückgesetzt wird, prüft das System, ob der Verbrauch für den Tag über oder unter dem vorherigen Minimum oder Maximum liegt, und speichert den Wert. Der Durchschnitt wird berechnet, indem der kumulierte Energieverbrauch durch die Anzahl der Tage dividiert wird.

Ich möchte den Tagesdurchschnitt der letzten Woche und des letzten Monats (der Einfachheit halber 4 Wochen) anzeigen, dh einen gleitenden Durchschnitt. Derzeit umfasst dies die Verwaltung eines Array von Werten für die letzten 28 Tage und die Berechnung eines Durchschnitts über das gesamte Array für monatlich und die letzten 7 Tage für wöchentlich.

Anfangs habe ich dies mit einem Array von Floats gemacht (da die Energie in der Form "12,12 kWh" vorliegt), aber dies war mit 28 * 4 Bytes = 112 Bytes (5,4% des SRAM). Es macht mir nichts aus, nur einen Dezimalpunkt der Auflösung zu haben, also habe ich uint16_t verwendet und die Zahl mit 100 multipliziert. Dies bedeutet, dass 12.12 als 1212 dargestellt wird und ich für Anzeigezwecke durch 100 dividiere.

Die Größe des Arrays beträgt jetzt 56 Bytes (viel besser!).

Es gibt keine triviale Möglichkeit, die Zahl auf ein uint8_t zu reduzieren, das ich sehen kann. Ich könnte den Verlust einer Dezimalstelle ("12,1 kWh" anstelle von "12,12 kWh") tolerieren, aber der Verbrauch ist häufig höher als 25,5 kWh (255 ist der höchste Wert, der durch eine vorzeichenlose 8-Bit-Ganzzahl dargestellt wird). Der Verbrauch war noch nie unter 10,0 kWh oder über 35,0 kWh, daher könnte ich möglicherweise 10 von den gespeicherten Zahlen abziehen, aber ich weiß, dass wir eines Tages diese Grenzwerte überschreiten werden.

Ich habe dann Code getestet, um 9-Bit-Werte in ein Array zu packen. Dies ergibt einen Bereich von 0-51,2 kWh und verwendet insgesamt 32 Bytes. Der Zugriff auf ein solches Array ist jedoch ziemlich langsam, insbesondere wenn Sie alle Werte durchlaufen müssen, um einen Durchschnitt zu berechnen.

Meine Frage lautet also: Gibt es eine effizientere Methode zur Berechnung eines gleitenden Durchschnitts mit drei Fenstern - Lebensdauer, 28 Tage und 7 Tage? Effizienz bedeutet weniger SRAM-Nutzung, jedoch ohne die Strafe für großen Code. Kann ich vermeiden, alle Werte zu speichern?

Cybergibbons
quelle
Möchten Sie einen gleitenden Durchschnitt über bestimmte Fenster berechnen oder würde eine Schätzung / Annäherung des Durchschnitts ausreichen?
Asheeshr
Ich möchte einen gleitenden Durchschnitt über ein 7-Tage- und 28-Tage-Fenster.
Cybergibbons
Sie könnten eine Auflösung von 0,2 kWh verwenden (dividieren und mit Faktor 5 multiplizieren) und Sie erhalten immer noch einen Bereich von 0 bis 51,2 kWh in 8 Bit
Ratschenfreak
Möglicherweise werden Zeichenfolgen und andere Konstanten in externem RAM oder externem Flash abgelegt. Siehe "Was kann ich tun, wenn mir der Flash-Speicher oder der SRAM ausgehen?" .
David Cary

Antworten:

2

Wenn Ihre Daten eine geringe Standardabweichung aufweisen, besteht eine Methode darin, Werte über das Fenster zu summieren und dann den Mittelwert von der Summe zu subtrahieren, während der neue Wert addiert wird.

Dies würde gut funktionieren, wenn es keine Ausreißer gibt , was dazu führen würde, dass der Gesamtfehler im Laufe der Zeit gegen Null tendiert.

//Pseudocode

count=0
while new_reading and count<7:
    sum += new_reading        //Calculate the sum of first 7 values
    count++

while new_reading:            //Loop till new readings available
    avg = sum / 7             //Calculate average
    sum -= avg                //Subtract average from sum
    sum += new_reading        //Add next reading to sum
    print avg
asheeshr
quelle
2

Sie können eine andere Methode verwenden, Sie behalten den aktuellen Durchschnitt bei und tun dies dann

average = (weight1*average+weight2*new_value)/(weight1+weight2);

Es ist kein echter gleitender Durchschnitt und hat eine andere Semantik, aber es kann trotzdem Ihren Anforderungen entsprechen

Für eine effizientere Berechnungsmethode für Ihre Lösung mit 9 Bits pro Wert können Sie die 8 höchsten Bits der Werte in einem Array behalten und die niedrigstwertigen Bits trennen:

uint8_t[28] highbits;
uint32_t lowbits;

Um einen Wert festzulegen, müssen Sie ihn aufteilen

void getvalue(uint8_t index, uint16_t value){
    highbits[index] = value>>1;
    uint32_t flag = (value & 1)<<index;
    highbits|=flag;
    highbits&=~flag;
}

was zu 2 Verschiebungen führt, ein UND und ein ODER und ein Nicht

Um den Durchschnitt zu berechnen, können Sie verschiedene Bit-Tricks verwenden, um ihn zu beschleunigen:

uint16_t getAverage(){
    uint16_t sum=0;
    for(uint8_t i=0;i<28;i++){
        sum+=highbits[i];
    }
    sum<<=1;//multiply by 2 after the loop
    sum+=bitcount(lowbits);
    return sum/28;
}

Sie können eine effiziente parallele Bitanzahl für die verwendenbitcount()

Ratschenfreak
quelle
1
Können Sie mir näher erläutern, wie ich auf diese Weise den Durchschnitt von 7 und 28 Tagen berechnen kann?
Cybergibbons
Ich habe diesen Ansatz bereits zum Glätten von verrauschten Analogwerten verwendet, und er war sicherlich ziemlich effektiv. Ich brauchte jedoch nicht viel Präzision, da die resultierenden Werte durch einen sehr groben Quantisierer geleitet wurden. Ich brauchte auch keine historischen Durchschnittswerte.
Peter Bloomfield
Dies erlaubt keine Berechnung des Durchschnitts für ein bestimmtes Fenster.
Asheeshr
@Cybergibbons Sie können verschiedene Gewichte verwenden, um das Fenster zu approximieren, damit alte Werte früher oder später unbedeutend werden, oder 7 Tage für das 7-Tage-Fenster und diesen gleitenden Durchschnitt für den 28-Tage-Durchschnitt
beibehalten
1

Wie wäre es, nur die Differenz zum vorherigen Wert zu speichern? In der Elektronik gibt es ein ähnliches Konzept namens Delta Sigma-Wandler, das für DA / AD-Wandler verwendet wird. Es beruht auf der Tatsache, dass die vorherige Messung ziemlich nahe an der aktuellen liegt.

Jippie
quelle
Eine weitere interessante Idee. Leider bin ich mir nicht sicher, ob der Energieverbrauch immer so sein wird, da es sich um ein Wärmepumpensystem handelt und ein Tag 30 kWh, der nächste 10 kWh dauern könnte. Ich muss wirklich Daten sammeln und sehen.
Cybergibbons
0

Warum können Sie die Werte nicht einfach addieren, sobald Sie sie erhalten haben? Ich meine also, Sie erhalten den Wert für Tag 1, teilen ihn durch 1 und speichern ihn und die 1 irgendwo. Dann multiplizieren Sie die 1 mit dem Wert und addieren sie zum nächsten Wert und teilen beide durch 2.

Diese Methode würde einen gleitenden Durchschnitt mit zwei oder drei Variablen erzeugen, wie ich mir vorstellen kann. Ich würde Code schreiben, aber ich bin neu im Stackexchange. Bitte nehmen Sie Kontakt mit mir auf.

Aditya Somani
quelle
Ich verstehe nicht, wie dies mit dem 7-Tage- und 28-Tage-Fenster umgeht?
Cybergibbons
Behalten Sie den Überblick über die vorherigen und nächsten Werte und addieren und subtrahieren Sie sie weiterhin von Ihrem laufenden Durchschnitt ...
Aditya Somani
1
Dann bin ich wieder in der Lage, mich an 27 Tage Geschichte zu erinnern, sicher?
Cybergibbons
Ich habe nachgedacht und du hast recht. Das macht meine Antwort technisch also falsch. Ich investiere etwas mehr Zeit und Geduld. Vielleicht etwas aus der Box. Ich werde dich wissen lassen, wenn mir etwas einfällt. Wir machen so etwas oft an meinem Arbeitsplatz. Lass mich herumfragen. Entschuldigung für die Verwirrung.
Aditya Somani
0

Gibt es eine effizientere Methode zur Berechnung eines gleitenden Durchschnitts mit ... 28 Tagen und 7 Tagen? ... müssen Sie sich an 27 Tage Geschichte erinnern ...?

Sie könnten nah genug dran sein, um 11 statt 28 Werte zu speichern, vielleicht so etwas wie:

// untested code
// static variables
uint16_t daily_energy[7]; // perhaps in units of 0.01 kWh ?
uint16_t weekly_energy[4]; // perhaps in units of 0.1 kWh ?

void print_week_status(){
    Serial.print( F("last week's total energy :") );
    Serial.println( weekly_energy[0] );
    int sum = 0;
    for( int i=0; i<4; i++ ){
        sum += weekly_energy[i];
    };
    Serial.print( F("Total energy over last 4 complete weeks :") );
    Serial.println( sum );
    int average_weekly_energy = sum/4;
    int average_daily_energy = average_weekly_energy/7;
    Serial.print( F("Average daily energy over last 4 weeks :") );
    Serial.println( average_daily_energy );
}
void print_day_status(){
    Serial.print( F("Yesterday's energy :") );
    Serial.println( daily_energy[0] );
    Serial.print( F("average daily energy over the last 7 complete days: ") );
    int sum = 0;
    for( int i=0; i<7; i++ ){
        sum += daily_energy[i];
    };
    int average = sum/7;
    Serial.println( average );
}

Mit anderen Worten, anstatt jedes Detail eines jeden Tages in den letzten 27 Tagen zu speichern, (a) 7 oder so Werte detaillierter täglicher Informationen für die letzten 7 oder so Tage speichern und (b) 4 oder so "zusammengefasst" speichern. Werte der Gesamt- oder Durchschnittsinformationen für jede der letzten 4 oder so Wochen.

David Cary
quelle