Datenreihe aktualisieren besser Ringpuffer als Schleife in C++?

[T_55]

Hallo, ich steige langsam immer mehr in die Programmierung ein und habe eine Frage zum Aktualisieren von Datenreihen. zuerst mal den Code dann die Frage:

int array[50] = { 0 };
for(x=49; x>=1; x = x-1)
{
array[x]=array[x-1]
}
array[0]= NewValue;

Ok also es gibt ein Array mit 50 Feldern. Wenn ein neuer Wert (NewValue) kommt dann wird die Schleife ausgeführt und der neue Wert rückt in [0] und alle folgenden werden um eine Position nach hinten geschoben und der letzte verschwindet (im Code natürlich umgekehrt von hinten nach vorne).
Das war bisher meine Methode eine Datenreihe aktuell zu halten wenn neue Werte kommen. 50 Werte zu schreiben um 1 Wert zu aktualisieren ist wohl nicht so effektiv. Ich habe von Ringpuffern gelesen, dass diese eine bessere Alternative darstellen habe es aber nirgendwo richtig verstanden. Ich verstehe den Sinn und die Anwendung von Pointern. Leider aber nicht, wie das anhand meines Beispiels aussehen müsste??? Vielleicht gibt es ja noch was anderes besseres? Schlussendlich suche ich die Lösung die für das aktualisieren der Datenreihe die beste Performance im Programm bietet. Hat jemand eine Idee wie man die Datenreihe aktualisiert ohne alle 50 Werte einzelnd verschieben zu müssen und wie das im Code aussehen würde?

Gruß

 

[Hancock]

Also in deinem Fall: Führ eine Variable currentPos ein, welche auf das aktuell vorderste Element zeigt. Im Beispiel verwende ich ein Index, ein Pointer ist da nicht unbedingt praktischer:

int array[50]={};
unsigned int current_pos=0;
current_pos=(current_pos-1)%50;
array[current_pos]=NewValue;

Zuerst mach ich Platz für meine Variable, dazu zieh ich von der aktuellen Position eins ab, damit es ein Ringpuffer bleibt und ich nicht auf Werte außerhalb des Arrays zugreife, verwende ich Modulo (%).
Dann kann ich den Wert einfach an dem berechneten Index einfügen.

Falls du wirklich schnelle Implementationen für ein Ringpuffer suchst, gibt's auch noch komplizierte Tricks.

Aber da du in C++ programmierst, wie schnell ist denn std::queue und std::deque? Zu langsam?

 

[blöderidiot]

Ich habe von Ringpuffern gelesen, dass diese eine bessere Alternative darstellen habe es aber nirgendwo richtig verstanden

"Ja, gibts schon" Darfst Du boost nehmen? Dann findest Du hier ein Beispiel.

/edit: was Du willst, ist: push_front(param_value_type item);

 

[hroessler]

Hallo,
alternativ kannst dir auch mal einen Hashcontainer wie un/ordered_map in der STL anschauen.


Greetz
hroessler

 

[VikingGe]

Machen wir uns erst einmal klar, was da passiert:
- Die älteren 49 Elemente werden nach rechts geschoben
- Das älteste Element verschwindet dadurch
- Das neue Element wird an die freigewordene Stelle am Anfang des Arrays geschrieben.

Wie kann man sich das Verschieben der Werte nun sparen? Wenn das älteste Element sowieso einfach verschwindet, warum schreiben wir das neue Element nicht gleich an die Stelle, an der das älteste Element steht?

Dafür müssen wir uns natürlich irgendwie merken, welches das älteste oder jüngste Element im Array ist.
Was eignet sich dafür? Richtig, ein Index.

size_t youngestIndex = ...;

Um zu wissen, womit wir das ganze sinnvoll initialisieren können, müssen wir uns erst einmal ansehen, was denn passiert, wenn wir ein neues Element einfügen. Und dazu müssen wir wissen, wo das älteste Element steht:

Falls das jüngste Element am Anfang des Arrays steht (Index 0), ist die Sache einfach, dann steht das älteste Element am Ende (Index 49) - es wäre dasjenige, das bei deinem Code am Ende einfach verwschwindet. In dem Fall würden wir einfach an die Stelle 49 schreiben und youngestIndex auf 49 setzen.

Falls nun das jüngste Element an Stelle 49 steht, wo steht dann das älteste Element? Direkt davor, also an Stelle 48. Das ist das Element, welches bei deinem Code nach zwei Insertions verschwindet. Und so weiter.

Will heißen, um jetzt ein Element einzufügen, müssen wir eigentlich nur folgendes machen:

int array[50];
size_t youngestIndex = 0;

// Einfügen:
youngestIndex = youngestIndex > 0
  ? youngestIndex - 1  // Element vor dem aktuell jüngsten Element
  : 49;  // Ende des Arrays
array[youngestIndex] = newValue;

youngestIndex entspricht also genau dem, was bei dir noch Index 0 ist. Wenn du jetzt also auf den jüngsten Wert zugreifen willst, schreibst du

array[youngestIndex]  // statt array[0]

Wenn du auf das n-te Element zugreifen willst, gibt es aber ein Problem:

/* Alt: */  array[10]
/* Neu: */  array[youngestIndex + 10]  // :-(

Was ist, wenn youngestIndex[/code] jetzt 49 ist? Dann wäre der Index am Ende ja 59 - das Array hat aber nur 50 Elemente. Das korrekte Element steht aber an Index 9.

/* Neu: */  array[(youngestIndex + 10) % 50]

Modulo-Operator. Sollte dir ein Begriff sein - falls nicht, einfach googlen.

Und im Grunde war es das auch schon. Wenn man das ganze jetzt in eine schöne Klasse verpackt (nicht getestet):

Spoiler

template<typename ElementType, size_t Size>
class FixedRingBuffer {

public:

  void add(ElementType&& element) {
    this->_elements[this->advanceIndex()] = std::move(element);
  }
  
  void add(const ElementType& element) {
    this->_elements[this->advanceIndex()] = element;
  }

  Element& operator [] (size_t index) {
    return this->_elements[(index + this->_youngestIndex) % Size];
  }
  
  const Element& operator [] (size_t index) const {
    return this->_elements[(index + this->_youngestIndex) % Size];
  }

private:

  ElementType _elements[Size];
  size_t _youngestIndex = 0;

  size_t advanceIndex() {
    return this->_youngestIndex =
      this->_youngestIndex > 0
        ? this->_youngestIndex - 1
        : Size - 1;
  }

};

Oder eben mit STL-Containern, wie es die anderen vorgeschlagen haben.

 

[T_55]

Besten Dank für den Input, ich wusste gar nicht das es soviele Möglichkeiten gibt da muss ich mich jeweils nochmal reinarbeiten, als Newbie hab ich auf Anhieb jetzt nicht direkt alles verstanden muss ich gestehen.

Die 50 Felder waren erstmal ein Beispiel wahrscheinlich werden es bis zu 10000. Was für mich dann auch relevant wäre ist dann die Felder auch in richtiger Reihenfolge zu benutzen was ja bei meiner Newbie Schleifenlösung einfach durch den Index funktioniert.

Wenn man zum Beispiel festlegt die 10000 stehen immer aktuell zur Verfügung und man kann dann aus den aktuellsten x Feldern ([0] bis [x]) irgendwas berechnen zB einen Durchschnittswert oder so, dann muss doch auch irgendwas wie ein Index existieren... Klingt jetzt bestimmt sehr naiv alles, mein Skill hat noch Luft nach oben

 

[Magogan]

Der %-Operator ist als Rest der Integer-Division a/b definiert, bei -1/50=0 also nicht etwa 49, sondern -1, macht auch Sinn, da in C++ in Richtung 0 gerundet wird bei Integer-Division. Da musst du aufpassen, dass kein negativer Index für den Array-Zugriff herauskommt.

 

[Hancock]

Hast recht, mit dem Unterlauf geht's in die Hose. ([small]Wenn es ein 2^n Bereich gewesen wäre, hätte mich das unsigned-Verhalten gerettet[/small])

int array[50]={};
unsigned int current_pos=0;
if(current_pos==0)//Wrap around
current_pos=49;
else
current_pos--;
array[current_pos]=NewValue;

Wenn du einen Ringpuffer so verwendest, wie es 99 % der Programmierer machen (also am Ende einfügen), dann vereinfacht sich das, da dort die Modulooperation wieder sauber definiert ist:

current_pos=(current_pos+1)%50;
array[current_pos]=NewValue;

Also immer schauen, dass man den Index im validen Bereich behält.
Ergo:
Standardbibliothek nutzen, da geht am wenigsten schief .

Und was ich vergessen hab: http://fetter.org/optimization.html

 

[Miuwa]

Der universelle (aber nicht besonders effiziente) 1-Zeiler für Ringpuffer:

int getBufferIndex(int headIdx, int offset, int length) {
	assert(length > 0);
        assert(offset < length);
        assert(offset > -length);
	return  (((headIdx + offset) % length) + length) % length;
}

 

[kuddlmuddl]

Was ist das denn für eine unsinnige Implementierung eines Ringbuffers? Das sollte man erstmal in Frage stellen, bevor man den Quellcode "verbessert".
Du schreibst immer an die selbe Stelle und sorgst dafür, dass vorher alle Daten einmal Platz machen und sich weg-bewegen. Schreib doch die neuen Daten einfach immer nach dem letzten Eintrag, dann muss niemals etwas bewegt werden. Und wenn der Ring sich schließt, dh wenn du auf ein Feld nach dem letzen Feld schreiben willst fängst du wieder vorne an und überschreibst das erste Feld.

Ein Ziel solcher Buffer ist es mit konstaktem Zeit und Speicheraufwand (also Unabhängig von Maximalgröße und Füllegrad) Lesen, Schreiben und sogar verändern zu können. Dein Ringbuffer allerdings bewegt bei jeder Fülloperation den GESAMTEN Inhalt. Gehts noch schlimmer? ;-) Stell dir vor dein Array hat mehrere Tausend Felder und jeweils ernsthaft Speicher >1kb. Dann ist deine Anwendung ja permanent nur am Speicher bewegen...

So ein Ringbuffer ist eine feste Menge Speicher und wenn es zB 50 Felder groß ist und man das 51te Element einfügt wird dieses eben nicht an Stelle data[50] geschrieben sondern an Index 0, der bereits mit dem ersten Element befüllt wurde. (Index 50 gibts nicht, da nur Index 0 bis 49 gültig sind bei Größe 50).
Das 10te Element fügt man einfach hinter dem 9ten ein und die Elemente 1-9 werden natürlich garnicht angefasst.

Natürlich muss man sichertellen, dass der Buffer nicht bereits 'voll' ist wenn man weitere Daten hinzufügt. Voll meint hierbei aber natürlich, dass alle Daten des Buffers noch für weitere Verarbeitung warten und daher noch nicht überschrieben werden dürfen.



edit:
Bist du dir ganz sicher, dass du überhaupt einen Ringbuffer willst/brauchst?
Wieso nimmst du nicht einfach eine http://www.cplusplus.com/reference/deque/deque/
Ringbuffer sind was für µC oder wenn man wirklich weiß, was man tut und das sich durch den RB Performance steigern lässt.

 

[Miuwa]

@kuddlmuddle:
Falls das eine Antwort auf den Anfangspost sein soll würde mir den noch mal ganz in Ruhe den durchlesen. Er hat doch geschrieben, dass seine bisherige Datenstruktur (und nein, er hat nicht behauptet das wäre ein Ringpuffer) ineffizient ist und deshalb nach Alternativen gefragt bzw. wie man denn einen Ringpuffer als eine davon implementieren würde.