Algorithmus Warteschlange Ringpuffer wirklich fehlerfrei

Barista

Top Contributor
Ich hatte Bedarf an einer Warteschlange, aufgebaut mit einem Array als Ringpuffer.

Wegen Speicher und Performance wollte ich keine vorgefertigte Java-Collection verwenden, weil da für primitive Typen meist Wrapper-Objekte notwendig sind.

Klar, dass man zuerst mal eine Suchmaschine benutzt.

Bei den gefundenen Lösungen hat mich gestört, dass keine oder zu wenig Tests dabei waren.

Ausserdem, selbst gekocht schmeckt besser.


Das Problem beim Ringpuffer ist, dass man anhand der beiden Indexwerte zum Hinzufügen und zum Entnehmen nicht erkennen kann, ob bereits ein Überlauf erfolgte oder ob der noch kommt.

Nach einigem Rumprobieren bin ich auf dem Nachhauseweg auf folgende Lösung gekommen:

Ich führe beim Array-Zugriff immer ein Modulo auf den jeweiligen Index aus.

Dadurch bleibe ich sicher in den Array-Grenzen.

Ich lasse den Hinzufüge-Index über die Array-Grenze laufen, ist kein Problem wegen dem Modulo beim Zugriff.

So ist der Hinzufüge-Index immer größer als der Entnehm-Index.

Wenn auch der Entnehm-Index die Array-Grenze (0 bis Array-Größe - 1) verlässt, reduziere ich beide Indexe auf den Array-Bereich (Modulo).

Ich bewege mich also auf dem Zahlenstrahl ein Stück weiter, bleibe aber aufgrund des Modulo im Bereich des Arrays.

Das hat auf Anhieb geklappt und alle Tests waren grün.

In der Code-Coverage konnte ich sehen, dass einige Codezeilen zum Abfragen und Reduzieren nie benutzt wurden, die konnte ich entfernen.

Den alten Code (Zwischenstand) habe ich mit ins Repo eingecheckt.

Ich nehme an, dass meine Tests recht gut sind.

Es bleibt aber immer noch die Angst, dass ein Fehler drin ist.

Ich wäre sehr dankbar, wenn jemand einen Fehler entdeckt oder mir einen Hinweis gibt, wie ich die Fehlerfreiheit beweisen kann.

Danke
 

mihe7

Top Contributor
wie ich die Fehlerfreiheit beweisen kann.
Mit einem formalen Korrektheitsbeweis, der aber alles andere als trivial ist.

Das Problem beim Ringpuffer ist, dass man anhand der beiden Indexwerte zum Hinzufügen und zum Entnehmen nicht erkennen kann, ob bereits ein Überlauf erfolgte oder ob der noch kommt.
Nehmen wir mal head und tail für die Indizes. Wenn Du als Invariante nimmst, dass für einen leeren Puffer head == tail gilt, musst Du dafür sorgen, dass head != tail gilt, wenn der Puffer nicht-leer ist.

Gehen wir von einem leeren Puffer mit n Elementen aus, gilt head == tail und ganz offensichtlich (head+n) % n == tail. Damit das nicht passiert, darfst Du max n-1 Elemente einfügen. Dann entsteht ein Überlauf, wenn (head + 1) % n == tail.

Sprich: Du musst einfach für ein Element mehr Platz schaffen.

Alternativ kannst Du als Invariante nehmen, dass im Fall von head == tail der Puffer entweder leer oder voll ist. Dann musst Du den Fall auf andere Weise unterscheiden, z. B. mit einem boolean oder indem Du die Zahl der Elemente speicherst.

Mehr fällt mir dazu spontan auch nicht ein.
 

Barista

Top Contributor
Gehen wir von einem leeren Puffer mit n Elementen aus, gilt head == tail und ganz offensichtlich (head+n) % n == tail. Damit das nicht passiert, darfst Du max n-1 Elemente einfügen. Dann entsteht ein Überlauf, wenn (head + 1) % n == tail.

Ja, so müsste ein Beweis aufgebaut sein.

Sprich: Du musst einfach für ein Element mehr Platz schaffen.

Das trifft nicht zu, alle Speicherplätze sind verwendbar.

Alternativ kannst Du als Invariante nehmen, dass im Fall von head == tail der Puffer entweder leer oder voll ist. Dann musst Du den Fall auf andere Weise unterscheiden, z. B. mit einem boolean oder indem Du die Zahl der Elemente speicherst.

Durch die Modulo-Operation hat die Einfüge-Position einen Merker für den Überlauf.

Es wäre schön, wenn man den Beweis der Korrektheit automatisiert prüfen könnte, also dass er nach Programmänderungen immer noch eingehalten ist. Dies geht sicher nur mit statischer Codeanalyse.

Vielen Dank
 

httpdigest

Top Contributor
Dinge werden sehr viel einfacher, wenn man nicht eine read- und write-Position speichert, sondern eine read-Position und die Länge/Anzahl der aktuellen Elemente. Das verhindert, dass man den durch die Modulo-Operation mehrdeutigen Fall read==write (mod n) (voll oder leer?) bekommt.
Java:
import java.util.*;
public class IntRingBuffer {
  private int read;
  private int len;
  private final int[] arr;
  public IntRingBuffer(int capacity) {
    this.arr = new int[capacity];
  }
  public int capacity() {
    return arr.length;
  }
  public boolean isEmpty() {
    return currentSize() == 0;
  }
  public boolean isFull() {
    return currentSize() == capacity();
  }
  public int currentSize() {
    return len;
  }
  public int freeSize() {
    return capacity() - currentSize();
  }
  public boolean add(int v) {
    if (isFull())
      return false;
    arr[(read + len++) % capacity()] = v;
    return true;
  }
  public int get() throws NoSuchElementException {
    if (len == 0)
      throw new NoSuchElementException();
    return arr[read];
  }
  public int take() throws NoSuchElementException {
    if (len == 0)
      throw new NoSuchElementException();
    int res = arr[read];
    read = (read + 1) % capacity();
    len--;
    return res;
  }
}
 
Zuletzt bearbeitet:

mihe7

Top Contributor
Das trifft nicht zu, alle Speicherplätze sind verwendbar.
Natürlich sind alle Speicherplätze verwendbar, aber nicht mit zwei Indizes, da head == tail sowohl in einem leeren als auch in einem vollen Puffer gilt.

Durch die Modulo-Operation hat die Einfüge-Position einen Merker für den Überlauf.
Der Modulo dient für einen anderen Überlauf, nämlich den über die Arraygrenze. Der Überlauf des Puffers wäre gegeben, wenn in einen vollen Puffer eingefügt werden würde und hat mit dem Modulo nichts zu tun. Die Situation lässt sich mit zwei Indizes nicht von einem leeren Puffer unterscheiden, wenn alle Speicherplätze verwendet werden; wohl aber mit einem Index und der Zahl der Elemente im Puffer.
 

temi

Top Contributor
Java:
  public boolean add(int v) {
    if (isFull())
      return false;

Ich war immer der Ansicht, dass ein Ringpuffer gar nicht "voll" sein kann, weil er ja, wie der Name "Ring" schon aussagt, den ältesten Inhalt wieder überschreibt?
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
schegga_B AES-Algorithmus in javax.crypto Allgemeine Java-Themen 3
M Laufzeit des Prim Algorithmus Allgemeine Java-Themen 3
O Newton Algorithmus Java Allgemeine Java-Themen 1
CptK Backpropagation Algorithmus Allgemeine Java-Themen 6
N Google Authenticator Algorithmus (SHA1) Allgemeine Java-Themen 1
gotzi242 Schatzsuche mithilfe eines O(log n) Algorithmus Allgemeine Java-Themen 2
Zrebna Quicksort-Algorithmus - zufälliges Pivot wählen Allgemeine Java-Themen 6
L Klassen Algorithmus für das folgende Problem entwickeln? Allgemeine Java-Themen 30
M Probleme mit Negamax-Algorithmus Allgemeine Java-Themen 29
F Q - Learning Algorithmus Bug Allgemeine Java-Themen 4
M Salesman Problem - Bruteforce Algorithmus Allgemeine Java-Themen 23
M Minmax Algorithmus Verständnisproblem Allgemeine Java-Themen 2
H Rundreise frage (Algorithmus) Allgemeine Java-Themen 18
F KMP-Algorithmus Allgemeine Java-Themen 9
S Algorithmus welcher True-Werte in einem Array findet und auswertet. Allgemeine Java-Themen 5
U Methoden Algorithmus MergeSort String [ ] array sortieren programmieren Allgemeine Java-Themen 17
P MinMax Algorithmus Allgemeine Java-Themen 0
J Abhängigkeit zwischen Rechenzeit und Speicherbedarf in einen Algorithmus Allgemeine Java-Themen 7
K Djikstra-Algorithmus Allgemeine Java-Themen 1
T Minimax/Alphabeta Algorithmus hängt sich auf (?) Allgemeine Java-Themen 2
M Algorithmus zum Zahlen einteilen Allgemeine Java-Themen 8
O Best Practice Hilfe bei Algorithmus gesucht Allgemeine Java-Themen 10
S Algorithmus um Objekte auf einer Flaeche mit gleichem Abstand anzuordnen..? Allgemeine Java-Themen 20
S Rucksackproblem und genetischer Algorithmus Allgemeine Java-Themen 9
L Abbruch des Algorithmus Allgemeine Java-Themen 8
D Input/Output Ausgleichen chemischer Reaktionsgleichungen mit dem Gauß-Algorithmus Allgemeine Java-Themen 2
Messoras A*-Algorithmus integrieren Allgemeine Java-Themen 3
S Buchscan 3D Dewarp Algorithmus - Ansätze Allgemeine Java-Themen 1
B Verteilungs-/Vergabe-Algorithmus mit abhängigen Score-Werten Allgemeine Java-Themen 3
Androbin "Shunting Yard"-Algorithmus Allgemeine Java-Themen 6
B Algorithmus - Project Euler Problem 18 Allgemeine Java-Themen 2
N Algorithmus zum bewerten von mathematischen Funktionen Allgemeine Java-Themen 11
O Algorithmus Optimierung Allgemeine Java-Themen 3
Joew0815 Algorithmus - Zahlenfolge in 4 ähnliche Teile aufteilen Allgemeine Java-Themen 0
O Tag Cloud Algorithmus Idee gesucht Allgemeine Java-Themen 2
A Implementierung eines Algorithmus (Farthest Insertion zur Lösung des TSP) in O(n²) Allgemeine Java-Themen 2
C Eclipse Probleme bei selbst erstelltem Algorithmus Allgemeine Java-Themen 2
H Graph-Algorithmus gesucht Allgemeine Java-Themen 21
N Algorithmus durch Workflow Allgemeine Java-Themen 7
M tree-based diff Algorithmus (Code-Vergleiche) Allgemeine Java-Themen 3
S Uhrzeit Algorithmus sale Allgemeine Java-Themen 11
N A*-Algorithmus Allgemeine Java-Themen 5
A Suche Algorithmus zum Erstellen eines planaren Graphen Allgemeine Java-Themen 5
F Methoden Algorithmus zur Gegnerfindung (Turnier) Allgemeine Java-Themen 9
T Algorithmus Graph Allgemeine Java-Themen 10
J Algorithmus gesucht (Stringtransformation) Allgemeine Java-Themen 4
B Algorithmus Krankenhausbelegung Allgemeine Java-Themen 17
S Algorithmus von Dijkstra Allgemeine Java-Themen 2
alex_fairytail OOP Banknoten Algorithmus Teil 2 Allgemeine Java-Themen 13
2 ArrayList aktualisieren Algorithmus Allgemeine Java-Themen 11
alex_fairytail Methoden Banknoten Algorithmus Allgemeine Java-Themen 10
R Codehinweise: Algorithmus Größenvergleich von n Zahlen Allgemeine Java-Themen 5
SuperSeppel13 WTF?! Algorithmus-Geschwindigkeitstest Allgemeine Java-Themen 2
L Algorithmus für kürzesten Weg mit Wegpunkten Allgemeine Java-Themen 21
C Algorithmus Problem in Minesweeper Allgemeine Java-Themen 5
S Algorithmus um Labyrinth zu erzeugen Allgemeine Java-Themen 6
V Problem mit A* Pathfinder-Algorithmus Allgemeine Java-Themen 2
S Algorithmus um nächst folgende Primzahl zu berechnen Allgemeine Java-Themen 7
S Algorithmus Problem. Rechtecke effizient auf Spielfeld anordnen. Allgemeine Java-Themen 7
C Algorithmus-Hilfe Allgemeine Java-Themen 20
J Algorithmus Längenkombinationen? Allgemeine Java-Themen 7
M Kombinationen über rekursiven Algorithmus berechnen? Allgemeine Java-Themen 10
L Algorithmus für Poker-Hände Allgemeine Java-Themen 7
chik 2 return werte für Greedy-Algorithmus (gelöst) Allgemeine Java-Themen 3
D Abstruse Probleme mit eigenem replace Algorithmus Allgemeine Java-Themen 11
P RC4 Algorithmus Allgemeine Java-Themen 3
D RSA Verfahren - Erweiterter Euklidischer Algorithmus Allgemeine Java-Themen 4
C IBAN und Bic Validieren (Algorithmus) Allgemeine Java-Themen 10
P Problem mit A*-Algorithmus Allgemeine Java-Themen 12
M Wörter Algorithmus Allgemeine Java-Themen 7
M Algorithmus für automatische Zeilenumbrüche Allgemeine Java-Themen 12
K Postleitzahlen Algorithmus Allgemeine Java-Themen 12
G Problem mit Algorithmus Allgemeine Java-Themen 3
T Hilfe bei einem Algorithmus Allgemeine Java-Themen 2
S Stemming-Algorithmus gesucht (z.B. Porter) Allgemeine Java-Themen 2
RoliMG präfix zu infix algorithmus Allgemeine Java-Themen 6
Z A*-Algorithmus - Probleme mit offener/geschlossener Liste Allgemeine Java-Themen 7
S Javaimplementierung des MD5 Algorithmus Allgemeine Java-Themen 2
E Container-Pack-Algorithmus Allgemeine Java-Themen 4
G k nearest neighbor algorithmus Allgemeine Java-Themen 7
C HASH Algorithmus 2 Strings ergeben das Selbe. Allgemeine Java-Themen 2
P Page Rank Algorithmus implementieren Allgemeine Java-Themen 7
T Problem RSA-Algorithmus in Java? Allgemeine Java-Themen 2
minzel Hash-Algorithmus Allgemeine Java-Themen 9
Y komprimierung mittels Huffman-Algorithmus, bit-shifting. Allgemeine Java-Themen 2
K Algorithmus Allgemeine Java-Themen 10
C Algorithmus für Array Allgemeine Java-Themen 9
I Verschlüsselung mit Pwd. - User soll Algorithmus wählen Allgemeine Java-Themen 4
J fällt euch ein Algorithmus ein? Allgemeine Java-Themen 4
S Algorithmus für Sudoku Allgemeine Java-Themen 17
N Euklidischer Algorithmus in Java und keine Terminierung. Allgemeine Java-Themen 7
F Algorithmus für Sortierung gesucht Allgemeine Java-Themen 15
T Algorithmus verbessern Allgemeine Java-Themen 10
U Suche Algorithmus zur bestimmung des längsten Wegs Allgemeine Java-Themen 3
U Ford-Fulkerson Algorithmus gesucht Allgemeine Java-Themen 1
U Dijkstra Algorithmus gesucht Allgemeine Java-Themen 4
D Algorithmus für die Erkennung fehlerhafter Eingaben Allgemeine Java-Themen 4
I hash-algorithmus Allgemeine Java-Themen 9
1Raini Java Warteschlange Allgemeine Java-Themen 21
M Warteschlange mit Priorität Allgemeine Java-Themen 6

Ähnliche Java Themen

Neue Themen


Oben