Shift von Array werten?
-
TactX schrieb:
Umkopieren ist schlecht. Mach lieber einen Ringpuffer.
kommt auf die grösse des ringbuffers an.
beim ringbuffer hat man zwar kein umkopieren, dafür sind die zugriffe langsamer...
-
Hmmm, wo da wohl der break-even liegt? Bei 2 oder 3 Elementen? *scnr*
-
@SkySurfer: wenn du alle Werte im Speicher um sizeof(int) verschieben willst, dann nimm doch memmove
int array[20]; /* array wird hier mit Daten gefüllt */ memmove(&array[1], array, sizeof(int)*19);@Oermel: keine Ahnung, was du da versuchst zu erklären, aber das ist 100% falsch, zumal du keinen Speicher freigeben kannst, denn du nicht mittels *alloc-Family angefordert hast.
-
TactX schrieb:
Hmmm, wo da wohl der break-even liegt? Bei 2 oder 3 Elementen? *scnr*
die frequenz der zugriffe ist der knackpunkt.
-
musst du ein standard array nehmen? Also wirklich die werte verschieben? Ansonsten schreib dir einen ringbuffer struct. Anstatt die Werte zu shiften schiebst du einen startzeiger nach links. Das spart rechenzeit. Musst halt nur immer prüfen wann du an den grenzen bist und den zeiger halt hinten wieder einordnen. So hat es nach aussen hin den anschein als würdest du die Werte shiften.
-
vista schrieb:
TactX schrieb:
Hmmm, wo da wohl der break-even liegt? Bei 2 oder 3 Elementen? *scnr*
die frequenz der zugriffe ist der knackpunkt.
Erklär mal.
-
TactX schrieb:
vista schrieb:
TactX schrieb:
Hmmm, wo da wohl der break-even liegt? Bei 2 oder 3 Elementen? *scnr*
die frequenz der zugriffe ist der knackpunkt.
Erklär mal.
bei der buffer-kopier variante ist das schreiben langsam, das lesen schnell.
je grösser der buffer ist, desto langsamer sind die schreibzugriffe.
beim ringbuffer sind beide zugriffszeiten ziemlich ausgewogen, die buffer-grösse spielt keine rolle.
beim ringbuffer verliert man die zeit durch lesezugriffe, die man beim 'kopierbuffer' gespart hat.
wenn man z.b. selten schreibt und oft liest, dann ist buffer-kopieren besser.
erst recht, wenn man es etwas beschleunigt, z.b. man nimmt einen 3mal so grossen speicherbereich und muss dann seltener umkopieren...
-
ich würde nicht sagen das beim ring puffer die Zeit die man beim kopieren spart anhängen muss.... denn ich kann ausgehend vom aktuellen Zeiger doch genau berechnen auf welches element ich zugreifen muss. Das heißt auch das Lesen klappt in O(1) der Ring puffer braucht halt nur entsprechend implementierungsaufwand. Natürlich sollte ich den wirklichen anfang des arrays kennen und nicht nur den aktuellen welcher zurück geliefert wird. ein Umkopieren der Elemente dauert immer O(n) da ich ja jedes einzelne element umkopieren muss, beim ring muss ich nur den zeiger weiter schieben, und wenn ich auch auf ein element wahlfrei im puffer zugreifen will kann ich mir solange ich die größe des Arrays kenne und den anfang immer noch mit nur einen schritt berechnen wo ich hin zu greifen habe. Oder sehe ich da jetzt was falsch?
-
@ Fedaykin: Wie könnte so eine Ringpuffer Struktur aussehen? Kann mir da grade nichts darunter vorstellen. Hast du zufällig ein Beispiel parat?
Gruß SkySurfer
-
prinzip eines ringbuffers:
#define BUFFSIZE 100 char memory[BUFFSIZE]; int idx = 0; void write (char byte) { memory[idx++] = byte; // ein byte speichern if (idx == BUFFSIZE) // am ende des arrays angekommen? idx = 0; // ja, dann vorne wieder anfangen }