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

jasmin89

Hallo,

ich habe folgende Frage. Ich habe einen sehr großen Datensatz ca. 80GB. Ich habe mir ein C Programm geschrieben um diese Daten zu analysieren. Unter analysieren verstehe ich dass ich aus diesen Datensatz bestimmte Daten suchen möchte. Ich gebe z.b. "great" ein und das Programm liefert mir einen eindeutigen Ticker mit dem ich great zuordnen kann. Anhand diesen Tickers kann ich die Daten eindeutig zuordnen.

Ich möchte nun so eine Prozentanzeige programmieren das mir sagt wieviel Prozent der Datei untersucht wurde -also das mir den aktuellen Suchfortschritt anzeigt. Dafür dividiere ich die Position des aktuellen filepointers durch die Größe der Datei. Das Problem ist, dass durch diese Anzeige die Suche extrem langsam wird. Hat jemand einen Tipp für mich wie ich diese Prozentanzeige programmieren könnte damit diese Prozentanzeige die eigentliche Suche nicht zu stark ausbremst? Diese Berechnung, bremst die Suche sehr stark aus:

 float pct =  ((float)(uintptr_t)ftello64(f) / 77273022464)*100;
      printf("%3f%%\r %s",pct, gefunden[count].string);
      fflush (stdout);

Hat jemand einen besseren Tipp um eine solche Prozentanzeige zu implementieren, also die schneller funktioniert. Mir geht es also nur um die Obige Berchnung der Variable pct.

Hier ist nur ein Teil von meinem Code:

/******************************************************************************

*******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <ctype.h>
#include <unistd.h>
#include <stdint.h>

#define BUF 1000
#define BUF_FORSEARCH 300

/* Anpassen nach Bedarf... */
const char trennzeichen[] = ".;,:\"\' ";

typedef struct
{
  char string[BUF_FORSEARCH];

} Gefunden;

Gefunden gefunden[5] = { "A" };

//Statt strcmp wird diese Funktion verwendet. Diese Funktion ist case insensitive
int SGA_stricmp(const char *a, const char *b) {
  int ca, cb;
  do {
     ca = * (unsigned char *)a;
     cb = * (unsigned char *)b;
     ca = tolower(toupper(ca));
     cb = tolower(toupper(cb));
     a++;
     b++;
   } while (ca == cb && ca != '\0');
   return ca - cb;
}

void auswahlCheck ()
{
  char auswahl[BUF];
  int auswahl_integer = 0;
  printf
    ("M(\x94)chten Sie nur die ersten drei Spalten auslesen [1] oder alle Spalten auslesen [2]\n");

  if (scanf ("%[1-2]", auswahl) == 1)
    {
      auswahl_integer = atoi (auswahl);
      fflush (stdin);
    }

  else
    {
      printf ("Fehlerhafte Eingabe, entweder [1] oder [2] ausw(\x84)hlen\n");
      exit (1);
    }
}


int main ()
{
  FILE *f;

  unsigned long long int position;
  char searchstring[BUF];
  char puffer[BUF], puffer_bak[BUF];

  char *wort;
  int permno = 0, permno_alt = 0, count = 0;

// Datei für weitere verarbeitung Öffnen

  f = fopen ("daten.txt", "r");
  if (f == NULL)
    {
      printf ("Fehler bei fopen()...");
      return EXIT_FAILURE;
    }

  // Funktion um zu überprüfen ob die Eingabe richtig ist
  auswahlCheck ();


  printf ("Wonach suchen Sie in CRSP Datenbank: \n");
  scanf ("%s", searchstring);

  // Zeile wird eingelesen und von f und in puffer gespeichert
  while (fgets (puffer, BUF_FORSEARCH, f) != NULL)
    {
      // Suche wird mit Taste y unterbrochen
      if (count > 1000)
    {
      if (kbhit())
	{
	  int key = getch ();
	  if (key == 'y')	// Bei y Tastenanschlag abbruch der Suche
	    {
	      break;
	    }
	}
      count = 0;
    }

      count++;

      strcpy (puffer_bak, puffer);	// String wird von puffer nach puffer_bak kopiert

      wort = strtok (puffer, ";");	// Wort enthält PERMNO Nummer

      permno = atoi (wort);

      int count1 = 0;

       float pct =  ((float)(uintptr_t)ftello64(f) / 77273022464)*100;
      printf("%3f%%\r %s",pct, gefunden[count].string);
      fflush (stdout);

      // Jeweils die erste gefundenen Zeile wird in Konsole angezeigt
      while (wort != NULL)
	{

	  if (SGA_stricmp (wort, searchstring) == 0)
	    {

	      if (permno != permno_alt)
		{

		  position = ftello64(f);
		  strncpy (gefunden[count1].string, puffer_bak,sizeof (gefunden[count1].string));
		  printf ("%s\n", gefunden[count1].string);
		  //count1++;
		  printf ("%llu \n", position);
		}
	      permno_alt = permno;

	    }

	  wort = strtok (NULL, trennzeichen);
	}

    }
}

DocShoe

Gib den Fortschritt halt nicht bei jeder Iteration aus. Du kannst ja die Dateigröße zB. durch 1000 teilen, und jedes Mal, wenn du ein Promille gelesen hast machst du die Ausgabe. Oder du überlegst dir ein anderes Kriterium.

wob

Du brauchst auch nicht ftell zu benutzen, du weißt ja, wie weit du bereits gelesen hast, d.h. du kannst ja einfach die gelesene Länge addieren (die dir fets zurückgibt). Ich weiß aber nicht, ob das relevant viel bringt, aber möglich wäre es (messen!)

Und wo kommt bei dir das 77273022464 her?

Außerdem den Fortschritt nicht ständig bei jeder Zeile aktualisieren (das flush ist ja möglicherweise auch teuer).

Und generell: trenne das Suchen in der Datei von sämtlicher Benutzereingabe. Was soll auswahlCheck tun? 0 Parameter, kein Rückgabewert.

Warum braucht es tolower UND toupper in deiner Vergleichsfunktion? (das hier meine ich: ca = tolower(toupper(ca));)

DirkB

@jasmin89 Es ist nicht die Berechnung, sondern die Ausgabe, die das Programm verlangsamt.

Ausgabe nur, wenn sich der Wert geändert hat.

hustbaer

@DirkB Nachdem er sie mit float rechnet, wird sich der Wert ziemlich oft ändern

wob

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

@DirkB Nachdem er mit float rechnet, wird sich der Wert ziemlich oft ändern

Wer ist "er"? OP heißt @jasmin89, da würde ich per Default "sie" annehmen.

cyborg_beta

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

Wer ist "er"? OP heißt @jasmin89, da würde ich per Default "sie" annehmen.

Jeder greift mal ins Klo.

Th69

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

Und wo kommt bei dir das 77273022464 her?

Das ist (wohl) die fest-kodierte Größe der Datei:
@jasmin89 sagte in C programm, große .txt Datei durchsuchen, mit Prozent Fortschrittsanzeige

Ich habe einen sehr großen Datensatz ca. 80GB.

@jasmin89: Die Größe der Datei kann man mit fseek (bzw. fseeko64) sowie der schon von dir verwendeten Funktion ftell (bzw. ftello64) ermitteln: Find the size of a file in bytes in C (unter Unix/Linux auch mittels (f)stat).

DirkB

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

@DirkB Nachdem er mit float rechnet, wird sich der Wert ziemlich oft ändern

Eins nach dem Anderen.

Vielleicht reichen ja auch 5 Nachkommastellen bei Prozentangaben aus.

Und float bringt auch eher Nachteile gegenüber double, da ja noch Konvertierungen dazwischen erfolgen

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).