C - Zeilenanfang einer Datei bestimmen

[Meillo]

So, jetzt auch mal ein bisschen Code von mir: 31636

Hm, wäre anstatt

Code: Alles auswählen

                while (strlen(matrix[row]) == linelen-1) {

nicht das hier richtig

Code: Alles auswählen

                while ((strlen(matrix[row]) == linelen-1) && (matrix[row][linelen-2] != '\n')) {

Das ist korrekt.

[lemak]

@Meillo
Warum nimmst du für int rows = 6; nicht statt 6 auch BUFSIZ steckt da eine Überlegung/Sinn hinter?
Wobei BUFSIZ sich ja auf I/O beschränkt :/

[Meillo]

Code: Alles auswählen

$ gcc 31636.c -Wall
$ ./a.out 
test
( 0/ 6 |  5/ 8): test
Das ist doch mein Ansatz in Perfektion :)
( 1/ 6 | 42/64): Das ist doch mein Ansatz in Perfektion :)
Wobei ich mich in keinster Weise auf die selbe Stufe stellen will.        
( 2/ 6 | 67/128): Wobei ich mich in keinster Weise auf die selbe Stufe stellen will.
^C

Sogar die Speicher-Vergrößerung machst Du -imo- wie bei einem C++ Vektor.
Cool - Was gute Planung so ausmachen kann.

Nicht dass dies der Ansatz gewesen wäre den ich für mich selbst gewählt hätte -- es ist meine Version von euren Planungen.

btw: Ist das ^C ein Tippfehler? Denn zum Beenden der Eingabe (ohne das Programm abzubrechen) verwendet man ^D.

[Meillo]

@Meillo
Warum nimmst du für int rows = 6; nicht statt 6 auch BUFSIZ steckt da eine Überlegung/Sinn hinter?
Wobei BUFSIZ sich ja auf I/O beschränkt :/

Ich habe ja hinzugeschrieben, dass die 6 kein realistischer Wert ist. Mit einer so kleinen Zahl tut sich halt was.

BUFSIZ hat damit nichts zu tun; ich will ja keine Datenmenge lesen oder schreiben.

rows sollte der geschätzten durchschnittlichen Zeilenanzahl entsprechen. Kleine Werte sparen Speicher, brauchen aber mehr realloc()s (schlechtere Laufzeit und durch Fragmentierung evtl. doch mehr Speicher). Große Werte reservieren oft unnötig viel Speicher.

[lemak]

Nicht dass dies der Ansatz gewesen wäre den ich für mich selbst gewählt hätte -- es ist meine Version von euren Planungen.

mello (mano) - welchen hättest du denn genommen...

btw: Ist das ^C ein Tippfehler? Denn zum Beenden der Eingabe (ohne das Programm abzubrechen) verwendet man ^D.

Nein ich habe das Programm mit STRG-C abgebrochen. das mach ich idR immer so.

[Danielx]

@Meillo:
Warum verdoppelst du eigentlich den Speicher immer und addierst nicht einen festen Wert dazu?

Gruß,
Daniel

[lemak]

imo ist dass das verfahren was einen guten Mittelweg der speicher Anforderung.
wenn ich mich nicht täusche macht das C++ od. Java bei Vektoren genauso. Die können ja auch zur Laufzeit -ähnlich wie Arrays- vergrößert und verkleinert werden.

[Meillo]

Nicht dass dies der Ansatz gewesen wäre den ich für mich selbst gewählt hätte -- es ist meine Version von euren Planungen.

welchen hättest du denn genommen...

Awk natürlich

Wenn in C, dann zeilenweise mit statischer Zeilenlänge. In 95% der Fällen reichen 1024 Zeichen aus. Also nehme man das Vierfache -- sind ja auch nur 4k Speichermenge. Dafür ist das Programm weitaus weniger komplex und viel schneller geschrieben.

Erst wenn der naive Ansatz nicht mehr ausreicht, sollte man kompliziertere Ansätze wählen. (Vgl. Thompson: ``When in doubt, use brute force.'')

btw: Ist das ^C ein Tippfehler? Denn zum Beenden der Eingabe (ohne das Programm abzubrechen) verwendet man ^D.

Nein ich habe das Programm mit STRG-C abgebrochen. das mach ich idR immer so.

Dann solltest du deine Regel mal ändern. Verwende wc mit einer Eingabe vom Terminal und vergleiche ^C mit ^D, dann weißt du weshalb.

@Meillo:
Warum verdoppelst du eigentlich den Speicher immer und addierst nicht einen festen Wert dazu?

Wie i schon bemerkt hat, ist das ein gutes und einfaches Verfahren. Es skaliert gut und erzeugt nur minimalen Overhead.

Welchen festen Wert würdest du denn wählen? Wenn ich verdopple bin ich nach 3,5 Schritten schon bei der nächsten Potenz, egal wo ich beginne. Der Verschnitt ist auch maximal die Hälfte des gebrauchten Speichers.

[Danielx]

Welchen festen Wert würdest du denn wählen?

Ich hätte jetzt mal ganz naiv 1024 genommen.

Der Verschnitt ist auch maximal die Hälfte des gebrauchten Speichers.

Allerdings kann der Verschnitt dann doch irgendwann, absolut gesehen, ziemlich groß werden.
Aber die Strategie hat schon was!

Keine Ahnung, wie da die optimale Strategie aussieht.

Gruß,
Daniel

[schorsch_76]

Welchen festen Wert würdest du denn wählen?

Ich hätte jetzt mal ganz naiv 1024 genommen.

Der Verschnitt ist auch maximal die Hälfte des gebrauchten Speichers.

Allerdings kann der Verschnitt dann doch irgendwann, absolut gesehen, ziemlich groß werden.
Aber die Strategie hat schon was!

Keine Ahnung, wie da die optimale Strategie aussieht.

Gruß,
Daniel

Um den absoluten Verschnitt relativ klein zu halten ist meiner Meinung lineares Wachstum besser. Mit quadratischem Wachstum, werden bei grossen Datenstrukturen weniger realloc's fällig als bei linearem Wachstum.

Bsp. 504 Zeichen lange Kette: 100 Byte Chunks (willkürlich gewählt)
100 Byte->200 Byte->300 Byte->400 Byte->500 Byte->600 Byte
=> 1x malloc + 5 x realloc : 96 Byte (16%) "Verschnitt"

Bei quadratischem Wachstum.
100 Byte->200 Byte->400Byte->800 Byte
=> 1 malloc und 3x realloc : 296 Byte(37%) Verschnitt.

Einen Nachteil muss man in Kauf nehmen. Je nach Anwendung muss man entscheiden wass wichtiger ist

Gruß

schorsch

[GoKi]

Amortisierte Kosten... hach eine herrliche Sache.
Und ich bin froh in C++ einfach die Datenstrukturen der STL benutzen zu können

[Danielx]

Man darf dabei aber auch nicht vergessen, dass deutlich mehr dynamischer Speicher allokiert werden kann (also z.B. mit malloc), als physikalisch verfügbar ist, denn der Speicher wird nur durch die Allokation erstmal nicht physikalisch belegt.
Der Kernel geht also davon aus, dass Programme den angeforderten Speicher oft gar nicht vollständig verwenden werden.
Windows macht das glaube ich auch so.

Gruß,
Daniel

[Duff]

Eine interessante Diskussion!

Würdet ihr die Datei denn zum Lesen und Schreiben öffnen oder aber dies über eine temporäre Datei lösen (oder und z.B. mit tmpfile())?

Ich habe in dem Beispiel immer einzelne Zeichenfolgen (char-Elemente), die ich dann mit bestimmten Wörtern vergleichen muss (ob ein matching stattgefunden hat) und anschließend eine entsprechende Atkion durchführen.

[Meillo]

Um den absoluten Verschnitt relativ klein zu halten ist meiner Meinung lineares Wachstum besser. Mit quadratischem Wachstum, werden bei grossen Datenstrukturen weniger realloc's fällig als bei linearem Wachstum.

Bsp. 504 Zeichen lange Kette: 100 Byte Chunks (willkürlich gewählt)
100 Byte->200 Byte->300 Byte->400 Byte->500 Byte->600 Byte
=> 1x malloc + 5 x realloc : 96 Byte (16%) "Verschnitt"

Bei quadratischem Wachstum.
100 Byte->200 Byte->400Byte->800 Byte
=> 1 malloc und 3x realloc : 296 Byte(37%) Verschnitt.

Kannst ja mal ausrechnen wieviele realloc()s du jeweils bei einer 5000 Zeichen langen Zeile brauchst. Und wie es wäre wenn die Zeile 50000 Zeichen lang ist.

Einen Nachteil muss man in Kauf nehmen. Je nach Anwendung muss man entscheiden wass wichtiger ist

Das stimmt. Die Entscheidung hängt auch davon ab wie gut man die erwarteten Eingabedaten abschätzen kann. (D.h. zum Beispiel wie oft Zeilen mit 50000 Zeichen vorkommen. Oder wieviel Prozent der Zeilen weniger als 80 Zeichen haben. Usw.)

[GoKi]

Kannst ja mal ausrechnen wieviele realloc()s du jeweils bei einer 5000 Zeichen langen Zeile brauchst. Und wie es wäre wenn die Zeile 50000 Zeichen lang ist.

Wobei das interessante hier der worst-case ist, wenn realloc jedes Mal die Liste umkopieren muss. Verdoppelt man die Größe, so ist sichergestellt, dass das Füllen des dynamischen Arrays (amortisiert) Kosten <= 3n verursacht.

[schorsch_76]

Das stimmt. Die Entscheidung hängt auch davon ab wie gut man die erwarteten Eingabedaten abschätzen kann. (D.h. zum Beispiel wie oft Zeilen mit 50000 Zeichen vorkommen. Oder wieviel Prozent der Zeilen weniger als 80 Zeichen haben. Usw.)

Das ist ja der Punkt. Bei einem Zeilen orientiertem Programm würde ich eh mit 1024 Zeichen Puffer arbeiten und wenn mal ne grössere kommt nen realloc durchführen.

Wenn ich mit Bildern arbeite, hab ich natürlich mehr Speicher den ich brauch. Da mach ich ja die Performance total kaputt, wenn ich jeweils nur 100 Byte mehr ranhole. Aber: Man kann ja bei Dateiorienterten Aufgaben auch fix die Grösse der Datei von der Platte holen, Speicher ranholen und dann reinladen.

Prinzipiell muss ich natürlich sagen, dass der quadratische Ansatz mit abschliessendem realloc auf die passende Grösse der beste Ansatz ist, wenn man von genug freiem, unfragmentierten Arbeitsspeicher ausgehen kann

Gehe ich davon aus, dass die Zeilplatform wenig RAM hat, und ich bsp. in 20% Schritten der erwarten Speichergrösse den realloc mache, hab ich maximal 20% Verschnitt. Muss die Kiste einen "echten" realloc machen, da nach dem aktuell genutzen Speicher nichts mehr frei ist, und ich nutze quadratisches Wachstum, muss die Kiste das doppelte des aktuellen Speichers dazu reservieren, umkopieren und dann den "alten" Speicher wieder freigeben. Hier kann auch das OS nicht zaubern

Gruß

schorsch

[cosmac]

Wenn ich mit Bildern arbeite, hab ich natürlich mehr Speicher den ich brauch. Da mach ich ja die Performance total kaputt, wenn ich jeweils nur 100 Byte mehr ranhole. Aber: Man kann ja bei Dateiorienterten Aufgaben auch fix die Grösse der Datei von der Platte holen, Speicher ranholen und dann reinladen.

Dann könnte ich aber auch mmap(2) in Erwägung ziehen.
Übrigens: ich find's toll, dass sich gleich mehrere Leute Gedanken um sowas machen; heutzutage gilt doch meist "man hat CPU und Speicher zum Sau füttern".

[TRex]

Es soll ja auch kleine Geräte wie Smartphones oder anderweitig verbaute Microcomputer geben, ich hab dieses Semester gleich zwei Fächer mit sowas.