Seite 1 von 1
Ringbuffer umsortieren
Verfasst: Fr Sep 06, 2013 8:37 am
von cloidnerux
Ich habe einen Ringbuffer, für die die nicht wissen was das ist: Ein Ringbufffer ist eine Datenstruktur, wo so neue Daten entweder auf den nächste freien Speicherplatz oder das älteste Element geschrieben werden, sodass immer nur eine bestimmte anzahl Elemente gespeichert werden.
Nun liegt es in der Natur der Sache, dass der Startindex irgendwo in dem Speicherbereich liegt:
Code: Alles auswählen
double buffer[BUFFER_LENGTH];
int startIndex;
...
buffer[startIndex] = element;
startIndex = (startIndex + 1) % BUFFER_LENGTH;
Nun habe ich aber nur sehr stark begrenzte Ressourcen(32-Bit µC) und muss mit den Daten aus dem Ringbuffer arbeiten. Das erfordert entweder das man den Index korrekt berechnet:
Code: Alles auswählen
for(int i = 0; i < BUFFER_LENGTH; i++)
{
buffer[(startIndex + i) % BUFFER_LENGTH];
}
was aber aufwendig ist, wegen der Addition und dem Modulo-Operator. Daher möchte ich den Buffer so umsortieren, dass der Start bei 0 liegt.
Nur was ist die beste, sprich schnellste Methode, die den wenigsten Speicher benötigt. Ein anlegen eines weiteren Arrays zum zwischenspeichern ist nicht möglich!
Re: Ringbuffer umsortieren
Verfasst: Fr Sep 06, 2013 9:40 am
von Xin
cloidnerux hat geschrieben:was aber aufwendig ist, wegen der Addition und dem Modulo-Operator. Daher möchte ich den Buffer so umsortieren, dass der Start bei 0 liegt.
Nur was ist die beste, sprich schnellste Methode, die den wenigsten Speicher benötigt. Ein anlegen eines weiteren Arrays zum zwischenspeichern ist nicht möglich!
Wenn Du den Buffer umsortierst hast Du BUFFERLENGTH Operationen, was deutlich teurer ist...
Code: Alles auswählen
for(int i = startindex; i < BUFFER_LENGTH; i++)
{
process( buffer[i] );
}
for(int i = 0; i < startindex; i++)
{
process( buffer[i] );
}
Wenn Du jetzt noch den [] rausnimmst, etwa
Code: Alles auswählen
auto it = &buffer[startindex];
auto end = &buffer[BUFFER_LENGTH];
for(; it < end; it++)
process( *it );
end = &buffer[startindex];
it = buffer;
for( ; it<end; it ++ )
process( *it );
sollte das deutlich schneller gehen?
Re: Ringbuffer umsortieren
Verfasst: Fr Sep 06, 2013 9:46 am
von cloidnerux
sollte das deutlich schneller gehen?
Nicht ganz. Ich benötige die Daten am stück, weil ich den Mittelwert über 32 Daten bilde. Bedeutet, an den Enden benötige ich die Daten vom Anfang.
Daher ist es ja nicht so einfach.
Das umsortieren macht das Problem einfacher.
Re: Ringbuffer umsortieren
Verfasst: Fr Sep 06, 2013 10:03 am
von Xin
cloidnerux hat geschrieben:sollte das deutlich schneller gehen?
Nicht ganz. Ich benötige die Daten am stück, weil ich den Mittelwert über 32 Daten bilde. Bedeutet, an den Enden benötige ich die Daten vom Anfang.
Daher ist es ja nicht so einfach.
Wieso brauchst Du die Daten am Stück? Du brauchst eine Routine, die 32 Daten addiert und die kann doch "process" heißen.
Du klärst vorher, wo die beiden Schleifen anfangen und enden sollen und addierst die Werte, teilst durch 32 und feddisch?
Und wenn Bufferlength 32 ist, gehst Du über den kompletten Buffer gehst, also nimm den Anfang und auch feddisch!?
Sowas? (ungetestet!)
Code: Alles auswählen
double sum = 0.;
bool swap = startindex + 32 > BUFFER_LENGTH ;
auto it = &buffer[startindex];
auto end = swap ? &buffer[BUFFER_LENGTH] : &buffer[startindex+32];
for(; it < end; it++)
sum += *it;
if( swap )
{
end = &buffer[startindex+32-BUFFER_LENGTH];
it = buffer;
for( ; it<end; it ++ )
sum += *it;
}
return sum / 32;
cloidnerux hat geschrieben:Das umsortieren macht das Problem einfacher.
Du sprachst von Schnelligkeit als Kriterium, nicht von Einfachheit.
Re: Ringbuffer umsortieren
Verfasst: Fr Sep 06, 2013 10:26 am
von cloidnerux
Wieso brauchst Du die Daten am Stück? Du brauchst eine Routine, die 32 Daten addiert und die kann doch "process" heißen.
Du verstehst mich nicht ganz. Ich habe in dem Ringbuffer Messwerte von einem ADC, der 10000 mal pro Sekunde einen Wert da rein schreibt. Bei einem Ereignis wird der Prozess des Datensammelns angehalten und ich lasse die gesammelten Daten durch einen FIR-Filter laufen.
Der nimmt immer 32 werte, verrechnet die und generiert daraus den neuen Wert an der aktuellen stelle, geht weiter und macht das mit dem nächsten 32 Werten:
Code: Alles auswählen
for(int i = 0; i < BUFFER_LENGTH - 32; i++)
{
for(int a = 0; a < 32 a++)
{
daten[i] += daten[i+a] * magic();
}
}
Ich muss das so in etwa mit allen Werten in Buffer machen, 32 Werte nehmen, verrechnen, speichern, weitergehen.
Wenn das einfach nur ein Array ist, ist das kein Problem. Aber dadurch, dass der Start irgendwo liegen kann, erscheint mir die Umsortierung sinnvoller.
Und wie gesagt, begrenzte Ressourcen, 32-Bit µC mit 48MHz und 32 kb ram und 256kb flash.
Re: Ringbuffer umsortieren
Verfasst: Fr Sep 06, 2013 10:54 am
von Xin
Ich denke, ich verstehe Dich und ich denke, dass was ich schrieb auch funktioniert.
Aber wichtig ist erstmal, dass du verstehst, was Du da tust und es funktioniert. Weiter optimieren kann man notfalls auch noch später.