realloc, aber wie?

Im Bad Case hast du für benötigte 2ⁿ+1 Bytes 2ⁿ⁺¹ Bytes belegt

Das ist fast Faktor 2 zuviel.

Leprechaun

DirkB schrieb:

Und am Ende dann nochmal realloc mit der richtigen Größe.

Davon würde ich abraten. Realloc muss eventuell den gesamten Bereich umkopieren. Das kann relativ viel Zeit kosten. Grundsätzlich sollte man bestrebt sein, die Anzahl der reallocs zu minimieren.

volkard

OkkaPapa schrieb:

=> bei jeder neuen Entität ein realloc mit Anzahl+1 (vermutlich nicht schneller als doppeltes Lesen??)?

Das kann unglaublich lahm sein. Schlimmstenfalls macht realloc den Speicherbereich immer nur um 1 größer und muss immer umkopieren, was dann imme teurer wird…

OkkaPapa schrieb:

=> Ein realloc mit Anzahl+10%, erneutes mitzählen und dann evt. wieder realloc?

Gut.

OkkaPapa schrieb:

=> Ein realloc mit Anzahl*2, erneutes mitzählen und dann evt. wieder realloc?

Auch gut.

OkkaPapa schrieb:

=> oder noch was anderes??

FileMapping, wenn möglich.
Oder verkettete Liste von 64k großen Arrays.

OkkaPapa schrieb:

Was ist ist erfahrungsgemaß der beste Kompromiss zw. Laufzeit und Speicher?

realloc mit Anzahl*2

Leprechaun schrieb:

DirkB schrieb:

Und am Ende dann nochmal realloc mit der richtigen Größe.

Davon würde ich abraten. Realloc muss eventuell den gesamten Bereich umkopieren. Das kann relativ viel Zeit kosten. Grundsätzlich sollte man bestrebt sein, die Anzahl der reallocs zu minimieren.

Ich glaube kaum, dass realloc beim verkleinern kopieren muss..
Zudem ist es das letzte.

Leprechaun

DirkB schrieb:

Ich glaube kaum, dass realloc beim verkleinern kopieren muss..

Realloc kann ganz einfach aus der Sequenz malloc-memcpy-free bestehen.

Uhm ... nur mal so als Denkenanstoß, das mit dem realloc kannst du dir auch komplett sparen.
Was ich meine? Halt Volkrad schon beschrieben, Datei read-only einmappen, und dann mit memchr (oder memcmp) nach '\r', '\n' oder "\r\n" suchen, je nachdem, was dein Sentinel ist. Wenn du die Daten sequentiell abarbeitest, sparst du dir so sämtliches Speichergefummel und Stalls. Allerdings muss deine Datenverabeitung dann auch mit diesem Sentinel und nicht mit '\0' arbeiten können, sonst ließt du ganz leicht in Speicher, in den du nicht lesen sollst.

Wenn du allerdings alle Zeilen zu jeder Zeit anfassen musst, dann wäre es wahrscheinlich immer noch intelligenter, die Datei in den Speicher zu mappen und dann die Zeilenumbrüche zu zählen.

Ach, der letzte Teil war nicht drin.
Und nachdem du dann die Zeilenumbrüche hast, erstellst du zwei Arrays, eines mit der Adresse innerhalb des Mappings, an dem eine Zeile anfängt, und eines, in dem für den String mit dem gleichen Index die Länge drinsteht.

Wer macht sich denn heute noch solche Gedanken?
DOS gibt es doch nicht mehr, oder?
Wenn man sich darüber Gedanken macht, dann dürft man keine Klassenbibliothek verwenden...

SeppJ

volkard schrieb:

OkkaPapa schrieb:

Was ist ist erfahrungsgemaß der beste Kompromiss zw. Laufzeit und Speicher?

realloc mit Anzahl*2

Hattest du mir nicht mal erklärt, wieso der Faktor 2 bei dieser Fragestellung einer der schlechtest möglichen Faktoren ist?

volkard

SeppJ schrieb:

volkard schrieb:

OkkaPapa schrieb:

Was ist ist erfahrungsgemaß der beste Kompromiss zw. Laufzeit und Speicher?

realloc mit Anzahl*2

Hattest du mir nicht mal erklärt, wieso der Faktor 2 bei dieser Fragestellung einer der schlechtest möglichen Faktoren ist?

Weiß nicht. Weil man immer (inclusive ein wenig Verwaltungsdaten) ein jota über der Zweierpozenz landet? Das würde führen zu (Anzahl+32)*2-32 oder so. Leider ist Wissen übers benutzte System nötig.
Seit x64 bin ich da ein wenig lockerer, fürchte ich. Allokierten aber nicht angefaßten Speicher zähle ich meistens als Nullkosten und was O(1) wäre gleich auch.