C programm, große .txt Datei durchsuchen, mit Prozent Fortschrittsanzeige

Th69

Für Prozentangaben sollte man aber mit Ganzzahlen rechnen (auch wenn man eine bestimmte Anzahl von Nachkommastellen anzeigen möchte) - ist dasselbe wie bei Geldwerten.

DocShoe

@Th69
Weiss nicht... hängt davon ab, wie lange der Vorgang dauert, wenn ich auf einen prozentualen Fortschritt schaue und da passiert längere Zeit nix, dann vermute ich, dass da iwas hängt. Prozentangaben mit Nachkommastellen finde ich da durchaus ok. Mann kann natürlich auch noch die Dauer anzeigen, die seit Start verstrichen ist, dann wäre ich auch mit ganzzahligen Prozentangaben glücklich.

Quiche Lorraine

@DocShoe sagte in C programm, große .txt Datei durchsuchen, mit Prozent Fortschrittsanzeige:

Weiss nicht... hängt davon ab, wie lange der Vorgang dauert, wenn ich auf einen prozentualen Fortschritt schaue und da passiert längere Zeit nix, dann vermute ich, dass da iwas hängt.

Naja, im schlimmsten Fall haben wir es hier mit einer 80 GByte großen Datei zu tun. Und alleine das ist schon eine Hausnummer.

Ich komme so für 1 Prozent auf cirka 850000 Schleifendurchgänge. Und pro Schleifendurchgang muss der max. 1000 Zeichen große String nochmals aufgesplittet und der String gesucht werden.

Ich frage mich da ob die lineare Datenstruktur da noch sinnvoll ist oder ob diese in eine Datenbank importiert werden sollte oder zumindestens in eine Datenstruktur ala B Baum konvertiert werden sollte.

DirkB

Jede Sekunde sollte auch reichen.

DocShoe

In welchem Format liegen denn die Daten vor? Ein Datensatz pro Zeile? Und wie lange dauert es denn, die komplette Datei zu durchsuchen? Soweit ich erkennen kann, wir die Datei zeilenweise eingelesen, wobei jede Zeile bis zu 300 Zeichen lang sein kann, ist das soweit richtig?
Oder hat die Datei noch eine interne Struktur, sodass man bestimmen kann, wie viele Datensätze die Datei hat und welchen Dateioffset ein bestimmter Datensatz hat. Bei 80GB könnte man über Parallelisierung nachdenken (wenn das nicht nur eine Übungsaufgabe ist => wozu programmierst du das?).

jasmin89

Danke für die Antworten.

@DocShoe: Danke für den Tipp. Ich gebe nun die Ausgabe nach jeder 10.000 Zeile aus, das funktioniert besser. Die Suche erfolgt nun schneller.
Die Daten liegen als .txt Datei vor. Datensatz pro Zeile sind ca. 752 Zeichen, das variiert aber. Ja die Datei wird Zeilenweise eingelesen.
Ich verwende bei der Suche von einer Zeile nur 300 Zeichen. Da nur diese für mich relevant sind- ich möchte nämlich einen bestimmten Ticker finden, dieser liegt in den ersten 300 Zeichen. Ich dachte halt da muss ich nicht alle Zeichen einer Zeile einlesen, da dies dann etwas schneller (vermutlich) ist.
Ich programmiere das als Hobby. Ich möchte einen Datensatz analysieren, und z.b ein Editor funktioniert bei dieser Dateigröße nicht. Deshalb wollte ich ein C-programm schreiben, achja und dabei lerne ich auch ein wenig programmieren
@wob: Gibt fgets auch die gelesene Länge zurück? Oder meinst du strln zu verwenden und mit einer int Variable diese dann immer zu addieren
Also: z.b long int length = strlen(puffer)+length;
Die 77273022464 sind die Dateigröße. fflush hat die Suche nicht so sehr ausgebremst, habe es getestet.
Ich verwende die Vergleichsfunktion SGA_stricmp da ich nicht alles in Großbuchstaben eingeben möchte. Der Datensatz enthält Wörter in Großbuchstaben, wenn ich z.b strcmp verwende und in der Konsole Kleinbuchstaben eingebe wird nichts gefunden.
@DirkB: Wieso hat denn float Nachteile gegenüber double, bezüglich Konvertierung. Verstehe nicht genau was du mit konvertierung meinst. Wenn ich nur float verwende, wird da was konvertiert?

DocShoe

Du hast da noch einen Denkfehler (der vermutlich keine große Rolle spielt): Du liest zeilenweise in einen 300 Byte großen Block ein, das heisst aber nicht, dass der Rest der Zeile ignoriert wird, wenn sie länger als 300 Zeichen ist. Der Rest der Zeile wird dann in folgenden fgets Aufrufen eingelesen, da wird nichts übersprungen.
Beispiel
Die Zeile ist 752 Zeichen lang und sie wird in 300 Byte Blöcken gelesen. Das resultiert in 3 Lesenoperationen:

Bytes 0-299 werden gelesen, Abbruch, weil die Puffergröße 300 Bytes sind, aber noch kein Zeilenende gelesen wurde
Bytes 300-599 werden gelesen, Abbruch, weil die Puffergröße 300 Bytes sind, aber noch kein Zeilenende gelesen wurde
Bytes 600-751 werden gelesen, Abbruch, weil fgets auf ein Zeilenende stößt

Edit: Der folgende Absatz stimmt nicht
Das Ganze birgt eine Gefahr: Der Puffer muss nicht nullterminiert sein, weil sein Inhalt vom Dateiinhalt abhängt und dein fgets Aufruf den ganzen Puffer beschreibt, inklusive des letzten Zeichens. Zur Sicherheit solltest du den Puffer um ein Byte vergrößern und das mit 0 besetzen, damit ist immer sichergestellt, dass der Puffer nullterminiert ist und gefahrlos mit den str... Funktionen benutzt werden kann. Also zB Puffergröße 301 Byte, das letzte Element mit 0 besetzen und max. 300 Byte lesen. Oder du benutzt die strn... Funktionen, die wiederum ihre Eigenheiten haben.

Zum anderen ein paar Stilmängel (obwohl ich mit bei C da nicht sicher bin):
Versuche Variablen so lokal wie möglich und so lokal wie möglich zu benutzen. Und sie sollten, falls möglich, schon bei der Definition initialisiert werden:
Statt

int main()
{
   FILE* f; // Definition ohne Initialisierung, Wert zufällig
   // diverses Zeugs
   f = fopen(...);
}

besser

int main()
{
   // diverses Zeugs
   FILE* f = fopen(...); // sofort initialisiert
}

Und eine weitere Überlegung:
Wenn die Datei häufig durchsucht werden soll, ist es vielleicht sinnvoll, eine Indexdatei zu erstellen, die die Dateioffsets jedes Zeilenbeginns enthält. Die wäre, grob überschlagen, etwa 880MB groß (80GB/752B sind etwa 110M Zeilen, pro Zeile ein 64bit Dateioffset). Dann könntest du die Indexdatei binär lesen, direkt an den Zeilenanfang jeder Zeile in der Datendatei springen und nur so viele Zeichen jeder Zeile lesen, wie tatsächlich für die Suche gebraucht werden. @Quiche-Lorraine hat das ja schon erwähnt

Was @DirkB vermutlich meint, ist dass aktuelle CPUs Fließkommazahlen als 8 Byte double in einem CPU Register unterbringen. Ein float ist nur 4 Byte groß, um damit zu arbeiten muss die CPU die Fließkommazahl erst von double nach float konvertieren. Dürfte in deinem Fall aber wohl keine Rolle spielen, da File I/O um Größenordnungen langsamer sind als die Konvertierung.

wob

@jasmin89 sagte in C programm, große .txt Datei durchsuchen, mit Prozent Fortschrittsanzeige:

@wob: Gibt fgets auch die gelesene Länge zurück?

Ach mist, tut es nicht.

Oder meinst du strln zu verwenden und mit einer int Variable diese dann immer zu addieren
Also: z.b long int length = strlen(puffer)+length;

Ich wollte den von mir erträumten Längen-Rückgabewert addieren. Sorry!

Die 77273022464 sind die Dateigröße.

Die solltest du einmalig am Anfang automatisch ermitteln (siehe https://www.c-plusplus.net/forum/post/2617554)

Ich verwende die Vergleichsfunktion SGA_stricmp da ich nicht alles in Großbuchstaben eingeben möchte.

schon klar, aber warum tolower UND toupper nacheinander? Wie unterscheidet sich das davon, wenn du alles nur in Kleinbuchstaben umwandeln würdest, ohne es vorher in Großbuchstaben gewandelt zu haben? Wenn du AbC suchst und daraus erst ABC machst, um dann abc daraus zu machen, wozu ist dann der Zwischenschritt mit toupper gut?

wob

@DocShoe sagte in C programm, große .txt Datei durchsuchen, mit Prozent Fortschrittsanzeige:

Das Ganze birgt eine Gefahr: Der Puffer muss nicht nullterminiert sein, weil sein Inhalt vom Dateiinhalt abhängt und dein fgets Aufruf den ganzen Puffer beschreibt, inklusive des letzten Zeichens. Zur Sicherheit solltest du den Puffer um ein Byte vergrößern und das mit 0 besetzen, damit ist immer sichergestellt, dass der Puffer nullterminiert ist

Siehe https://en.cppreference.com/w/c/io/fgets:

Reads at most count - 1 characters from the given file stream [...] If bytes are read and no errors occur, writes a null character at the position immediately after the last character written to str.

Das ist also sichergestellt, ohne dass du selbst mit -1 rumhantieren müsstest oder den Puffer vergrößern müsstest.

Th69

@DocShoe sagte in C programm, große .txt Datei durchsuchen, mit Prozent Fortschrittsanzeige:

@Th69
Weiss nicht... hängt davon ab, wie lange der Vorgang dauert, wenn ich auf einen prozentualen Fortschritt schaue und da passiert längere Zeit nix, dann vermute ich, dass da iwas hängt. Prozentangaben mit Nachkommastellen finde ich da durchaus ok. Mann kann natürlich auch noch die Dauer anzeigen, die seit Start verstrichen ist, dann wäre ich auch mit ganzzahligen Prozentangaben glücklich.

Du hast mich da mißverstanden. Bei einer Anzeige mit 2 Nachkommastellen würde man eben in Deziprozentwerten rechnen (so wie man Geldwerte auch in Cent oder sogar noch kleinere Werte - z.B. für Bankensysteme - berechnet).

DocShoe

@wob sagte in C programm, große .txt Datei durchsuchen, mit Prozent Fortschrittsanzeige:

Siehe https://en.cppreference.com/w/c/io/fgets:

Reads at most count - 1 characters from the given file stream [...] If bytes are read and no errors occur, writes a null character at the position immediately after the last character written to str.

Das ist also sichergestellt, ohne dass du selbst mit -1 rumhantieren müsstest oder den Puffer vergrößern müsstest.

Sieh man einer an, man lernt nicht aus

wob

@Th69 sagte in C programm, große .txt Datei durchsuchen, mit Prozent Fortschrittsanzeige:

Du hast mich da mißverstanden. Bei einer Anzeige mit 2 Nachkommastellen würde man eben in Deziprozentwerten rechnen (so wie man Geldwerte auch in Cent oder sogar noch kleinere Werte - z.B. für Bankensysteme - berechnet).

Aber warum "würde man [...] in Deziprozentwerten rechnen", was soll da der Vorteil sein? Verstehe ich nicht. Ich sehe da kein Problem mit einer float-Division. Du willst dem Anwender ja trotzdem 17,54% anzeigen und nicht 1754. Du müsstst dich also auch noch selbst darum kümmern, da ein Dezimaltrenner einzublenden. (das ist ja gerade nicht wie bei Geld, wo es fixe Minimaleinheiten wie eben z.B. Cent gibt).

Th69

Es ging ja darum, die Prozentzahl nur dann anzuzeigen, wenn sie sich geändert hat (und nicht bei jedem Schleifendurchlauf):

if (pct != current_pct)
{
  current_pct = pct;
  // output
}

Und bei Fließkommazahlen wäre dieser Vergleich bei jedem Schleifendurchlauf immer positiv.
Aber wo ich jetzt genauer darüber nachdenke, müßte fabs(pct - current_pct) >= 0.01 (bei 2 Nachkommastellen) als Bedingung genügen.

Würde mich trotzdem interessieren, ob die Umwandlung in Fließkommazahlen und deren Ausgabe nicht langsamer ist (bei so großen GB-Dateien), als die Verwendung einer optimierten Fixkommazahl-Ausgabe.

DirkB

@jasmin89 sagte in C programm, große .txt Datei durchsuchen, mit Prozent Fortschrittsanzeige:

@DirkB: Wieso hat denn float Nachteile gegenüber double, bezüglich Konvertierung. Verstehe nicht genau was du mit konvertierung meinst. Wenn ich nur float verwende, wird da was konvertiert?

Gerechnet wird bei Fließkommaoperationen in double.

printf nimmt bei Fließkommatypen auch mindestens double

Also Berechnung in double, Konvertierung nach float und wieder nach double für printf.

float hat nur bei sehr großen Arrays Vorteile gegenüber double.

SeppJ

Damit hier kein falscher Eindruck bei @jasmin89 aufkommt: Diese Rechentricks sparen höchstens ein oder zwei CPU-Takte, wenn überhaupt so viel. Takte, die völlig irrelevant sind, weil dein Programm die meiste Zeit entweder auf die Daten aus der Datei wartet, oder (bevor du dein Problem behoben hattest) darauf, dass deine Prozentausgabe auf der Konsole landet. Beides Operation, die um Größenordnungen länger dauern als ein paar float/double Berechnungen auf Teilen der CPU, die wahrscheinlich sowieso nichts besseres zu tun haben.

wob

@Th69 sagte in C programm, große .txt Datei durchsuchen, mit Prozent Fortschrittsanzeige:

if (pct != current_pct)

Du kannst ja auch schreiben if (pct >= current_pct + 0.01) - außerdem hat man vielleicht noch eine "ETA hat sich um mindestens 10 Sekunden geändert"-Bedingung.

Wenn du nutzlose Mikro-Optimierungen willst, kannst du auch next_update_pct = pct + 0.01; und if (pct >= next_update_pct)... schreiben.

jasmin89

Danke für die Hilfe. Ich konnte einige Tipps umsetzen.

@DocShoe: Danke für den Tipp. Habe den Debugger angeworfen und tatsächlich es werden immer 300 Byte Blöcke eingelesen. Das war mir so nicht bewusst. Dann wäre eine Lösung eine solche Indexdatei zu erstellen, damit ich nur z.b 300 Byte einlesen muss. Habe ich das richtig verstanden? Sonst eine andere Möglichkeit nur 300 Byte von einer Zeile einzulesen habe ich nicht? Ich habe probiert das Array um 1 Byte größer zu machen und das Array mit '\0' zu füllen. Aber es wird immer die gesamte Zeile, jeweils 300 Byte, eingelesen bis \n.

@wob: Du hast recht tolower UND toupper nacheinander macht nicht viel Sinn. Ich habe das ausgebessert.

SeppJ

Ist das mit den 300 Zeichen eine Anforderung (d.h. du willst nur die Treffer aus den ersten 300 Zeichen, und es könnte auch Treffer nach 300 geben, die du ausschließen möchtest), oder ist das eine voreilige Optimierung (d.h. du weißt es kommt nur in den ersten 300 Zeichen vor und denkst, das wäre irgendwie effizienter, wenn du das so machst)?

jasmin89

Das ist eine voreilige Optimierung, das was ich Suchen möchte kommt nur in den ersten 300 Zeichen vor. Ich dachte halt dass die Suche dann schneller wäre wenn ich nicht die Gesamte Zeile einlesen muss.

SeppJ

@jasmin89 sagte in C programm, große .txt Datei durchsuchen, mit Prozent Fortschrittsanzeige:

Das ist eine voreilige Optimierung, das was ich Suchen möchte kommt nur in den ersten 300 Zeichen vor. Ich dachte halt dass die Suche dann schneller wäre wenn ich nicht die Gesamte Zeile einlesen muss.

Dann spar dir das einfach. Du musst schließlich den Rest der Zeile auch einlesen, um das Ende der Zeile zu finden. Dateien sind bloß eine Folge von Zeichen, Zeilen haben keinerlei technische Bedeutung. Zeilen sind bloß eine Interpretation eines bestimmten Zeichens, da steckt aber nicht mehr dahinter, als dass das Zeichen Nummer 65 als 'A' interpretiert wird.

Man kann zwar mutmaßen, ob sich vielleicht Optimierungen dadurch ergeben, dass man sich eventuell ein paar Suchoperationen sparen kann, aber oft ist einfacher auch schneller. Mein Tipp daher, was du ausprobieren solltest: Datei blockweise lesen (gerne auch große Blöcke, die kleinste logische Einheit alter Festplatten ist 4kB, heutzutage bekommt man aber auch leicht 512kB in einem Rutsch) und die Blöcke durchsuchen. Aufpassen an den Rändern, dass man nichts verpasst, wenn der Suchbegriff genau auf einer Kante liegt. Beim Lesen möglichst stumpf und unformatiert lesen, also fread.

Was willst du am Ende haben? Gegebenenfalls könnte es dadurch schwieriger werden. Die Anzahl der Treffer ist einfach. Den Treffer selbst? Auch trivial. Die Zeilennummer der Treffer? Dann müsste man noch mitzählen, an wie vielen Zeilentrennzeichen man vorbei gekommen ist, auch einfach. Wenn du aber beispielsweise die ganze Zeile zu einem Treffer haben möchtest, wird es leider doch etwas kompliziert, weil dann das blockweise Lesen nicht mehr so einfach ist.