FIFO-Array, gibt es soetwas?

[Alter Mann]

Hallo,

ich habe ein kleines Problem: Ich brauche eine sehr schnelle Möglichkeit Bytes
innerhalb eines Array zu verschieben. So etwas wie:

Delphi-Quellcode:

procedure AddByte(aByte : Byte; Dest : TByteArray);
var
  I : WORD;
begin
  for I := Low(Dest) to High(Dest) -1 do
   Dest[I] := Dest[I+1];
  Dest[High(Dest)] := aByte;
end;

Gibt es da etwas?

Danke

[p80286]

Mach es doch umgekehrt, eine Anfangsadresse, eine Endadresse (16Byte). Da mußt Du nichts verschieben (DOS.Keyboard queue)

Gruß
K-H

[Amateurprofi]

Zitat von Alter Mann:

Hallo,

ich habe ein kleines Problem: Ich brauche eine sehr schnelle Möglichkeit Bytes
innerhalb eines Array zu verschieben. So etwas wie:

Delphi-Quellcode:

procedure AddByte(aByte : Byte; Dest : TByteArray);
var
  I : WORD;
begin
  for I := Low(Dest) to High(Dest) -1 do
   Dest[I] := Dest[I+1];
  Dest[High(Dest)] := aByte;
end;

Gibt es da etwas?
Danke

Vielleicht so? (nicht getestet)

Delphi-Quellcode:

procedure AddByte(aByte : Byte; Dest : TByteArray);
begin
   Move(Dest[Low(Dest)+1], Dest[Low(dest)], High(dest)-Low(Dest));
   Dest[High(Dest)] := aByte;
end;

[Aphton]

Falls du immernoch an der Suche dran bist, kuck dir mal deinen ursprünglichen Thread an.

[BUG]

Zitat von p80286:

Mach es doch umgekehrt, eine Anfangsadresse, eine Endadresse (16Byte). Da mußt Du nichts verschieben (DOS.Keyboard queue)

p80286 hat recht: Ein Ringbuffer löst dein Problem viel besser als ein einfaches Array.

[Namenloser]

Wenn es wichtig ist, dass alles in einem Block direkt hintereinander im Speicher liegt (bei Ringbuffer nicht gegeben), fiele mir folgendes ein:

Code:

Anfangszustand (FIFO-Array mit Länge 4):
  Äußerer Puffer: |[1][2][3][4][ ][ ][ ][ ][ ][ ][ ][ ]|
  FIFO-Array:       [1][2][3][4]

5 wird hinten ans FIFO-Array angefügt:
  Äußerer Puffer: |[1][2][3][4][5][ ][ ][ ][ ][ ][ ][ ]|
  FIFO-Array:          [2][3][4][5]

6 wird hinten ans FIFO-Array angefügt:
  Äußerer Puffer: |[1][2][3][4][5][6][ ][ ][ ][ ][ ][ ]|
  FIFO-Array:             [3][4][5][6]

...

12 wird hinten ans FIFO-Array angefügt:
  Äußerer Puffer: |[1][2][3][4][5][6][7][8][9][10][11][12]|
  FIFO-Array:                               [9][10][11][12]

Wenn jetzt noch was angefügt wird, dann müssen wir zuerst
einmalig die hintersten vier Stellen nach vorne kopieren:
  Äußerer Puffer: |[9][10][11][12][5][6][7][8][9][10][11][12]|
  FIFO-Array:       [9][10][11][12]

13 wird hinten ans FIFO-Array angefügt:
  Äußerer Puffer: |[9][10][11][12][13][6][7][8][9][10][11][12]|
  FIFO-Array:          [10][11][12][13]   

...

Das reduziert die Anzahl der Kopiervorgänge, wenn der äußere Buffer entsprechend groß ist, erheblich.

[Furtbichler]

Hübsch.
Mir fällt bei Queue immer eine linked list ein. Ohne groß nachzudenken, müsste eine einfachverkettete Liste ausreichen.

Aber die Problemstellung ist hier eine andere (hab den anderen Thread gelesen),

[sx2008]

Also ich würde mal überlegen, ob nicht eine Double-Ended-Queue alle Wünsche erfüllen kann.
Intern würde man die Dequeue als Ringspeicher mit einem dynamischen Array organisieren.
Es gibt einen "Top" und "Bottom"-Index mit denen man jeweils das obere und untere Ende der Queue markiert.
Sollte der Ringpuffer überlaufen, weil der Top-Index den Bottom-Index überholt, wird der Ringpuffer in der Grösse verdoppelt und die Daten kopiert.

Es gibt folgende Methoden:
PUSH und POP für das Einfügen oder Entnehmen eines Elements am hinteren Ende der Deque.
PUT und GET für das Einfügen oder Entnehmen am vorderen Ende der Deque.
FIRST und LAST für das Lesen des ersten oder letzten Elementes, ohne es zu entfernen.
Auuserdem gibt es noch das Property Count für den aktuellen Füllstand und das Property Capacity für die Grösse des Ringpuffers.

Damit das für Bytes noch etwas effizienter wird, kann man bei den Methoden Pop und Get noch die Anzahl der Bytes mitgeben, die man auslesen möchte.

Das wäre doch mal eine schöne Herausforderung für Delphiprogrammierer mit fortgeschrittenen Kenntnissen.