Ringbuffer umsortieren

[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!

[Xin]

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?

[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.

[Xin]

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;

Das umsortieren macht das Problem einfacher.

Du sprachst von Schnelligkeit als Kriterium, nicht von Einfachheit.

[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.

[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.