Effektives suchen/lesen in großen Datein



  • Hallo!

    Welches ist der performanteste Weg eine binäre Datei auf ihren Inhalt zu überprüfen?

    ich nehme an das fopen() die Datei vorher komplett buffert bevor ich den Stream benutzen kann oder? Und irgendwie habe ich Zweifel das fopen() da die effektivste Wahl ist.

    Was mache ich:
    Ich habe z.b. 100MB große Datein die jeweils mehrere wiederkehrende Header haben. Also jede Datei ist wie folgt aufgebaut:
    --- file ---
    [Header]
    [data]
    [Header]
    [data]
    ...
    -------------
    Die Daten können je nach beschreibung im Header länger oder kürzer sein.



  • Erstmal ist fopen nicht C++, sondern C. Zweitens, laut Referenz, buffert fopen den ganzen Stream (per Default).

    Um aber mal auf dein angefragtes Konzept zu sprechen zu kommen:
    Du kannst deine Datei in Chunks aufteilen (so wie du es gemacht hast) und schreisbt an jeden ChunkHeader die Größe. D.h. du musst jeweils nur den Header auslesen, und damit die Größe und kannst deinen Zeiger dann um eben X Bytes vorschieben und bist beim nächsten Chunk.

    PS: 100 MB sind noch nicht groß.



  • Wie sehen denn deine Zugriffe aus?
    Willst du die ganze Datei laden? Oder brauchst du nur den x-ten Eintrag aus einer Datei und dann wieder den y-ten Eintrag aus einer anderen Datei? (Index?)



  • Skym0sh0 schrieb:

    ErstmalDu kannst deine Datei in Chunks aufteilen (so wie du es gemacht hast) und schreisbt an jeden ChunkHeader die Größe. D.h. du musst jeweils nur den Header auslesen, und damit die Größe und kannst deinen Zeiger dann um eben X Bytes vorschieben und bist beim nächsten Chunk.

    Genau das hatte ich vor 🙂
    Ich würde sogar noch einen Schritt weiter gehen und einen Lookup Index-tree machen um entsprechende Querys durch den tree direkt auf den richtigen file + Byteoffset zu führen um nur den entsprechenden Datensatz zu Lesen.

    lagalopex schrieb:

    Wie sehen denn deine Zugriffe aus?
    Willst du die ganze Datei laden? Oder brauchst du nur den x-ten Eintrag aus einer Datei und dann wieder den y-ten Eintrag aus einer anderen Datei? (Index?)

    Sowohl als auch. Zum Teil werde ich wohl einmal von vorne bis hinten durchlaufen müssen. Aber ich möchte vorallem Querys effektiv bedienen die nur einen oder wenige Datensätze Lesen wollen.



  • Sowohl als auch. Zum Teil werde ich wohl einmal von vorne bis hinten durchlaufen müssen. Aber ich möchte vorallem Querys effektiv bedienen die nur einen oder wenige Datensätze Lesen wollen.

    Und warumbenutzt du nicht gleich eine Datenbank?

    Off-topic:

    Skym0sh0 schrieb:

    Erstmal ist fopen nicht C++, sondern C.

    Es ist einfach eine Funktion einer Bibliothek. Und nur weil sie im CßStandard festgeschrieben ist, kann sie trotzdem C++ sein, da C und C++ einen grossen Ueberlappungsbereich haben. http://www.cplusplus.com/reference/cstdio/fopen/



  • Das hängt von deinen Anforderungen ab.
    - brauchst du Zugriff auf alle Datenblöcke der Datei?
    - brauchst du wiederholten Zugriff auf bestimmte Datenblöcke der Datei?
    - musst du feststellen, ob bestimmte Datenblöcke in der Datei vorhanden sind?

    Meine erste Idee war, zunächst nur die Header zu lesen und die Datenblöcke zu überspringen. Das setzt voraus, dass der Header die Länge des zugehörigen Binärblocks enthält. Diese Header legst du in einem Vektor ab, den du dann durchsuchen kannst. Über die Headerinformationen kannst du an den Dateioffset des Datenblocks springen und von dort die Daten einlesen.

    Edit:
    Beim zweiten Mal Lesen ist mir aufgefallen, dass Skym0sh0 genau das vorgeschlagen hat 😃



  • knivil schrieb:

    Off-topic:

    Skym0sh0 schrieb:

    Erstmal ist fopen nicht C++, sondern C.

    Es ist einfach eine Funktion einer Bibliothek. Und nur weil sie im CßStandard festgeschrieben ist, kann sie trotzdem C++ sein, da C und C++ einen grossen Ueberlappungsbereich haben. http://www.cplusplus.com/reference/cstdio/fopen/

    Ja, und da scheiden sich die Geister. Manuelle Stringverwaltung per char* , malloc und free sind auch im C-Standard festgeschrieben und können in C++ benutzt werden, die Frage ist nur, sollte man das wirklich tun? Das berüchtigte C mit Klassen wird ja auch von C++ Compilern übersetzt, wo ziehst du da die Grenze? MMn sollte man soweit wie möglich die C++ Lösungen benutzen, es sei denn, es sprechen ernsthafte Gründe dagegen. Und der Erfahrung nach neigen Leute, die in C++ fopen benutzen, dazu auch andere sinnvolle C++ Sprachfeatures nicht zu benutzen, sondern die gefährlicheren C-Pendants.



  • Datenbanken sind zu Langsam und ich will eine exakt auf meine Wünsche zugeschnittene Struktur entwickeln. Nur so kann ich größtmögliche Performance sichern.

    DocShoe schrieb:

    Meine erste Idee war, zunächst nur die Header zu lesen und die Datenblöcke zu überspringen. Das setzt voraus, dass der Header die Länge des zugehörigen Binärblocks enthält. Diese Header legst du in einem Vektor ab, den du dann durchsuchen kannst. Über die Headerinformationen kannst du an den Dateioffset des Datenblocks springen und von dort die Daten einlesen.

    Richgtig. Der Aufwand zum finden des Xten Eintrags in einer Struktur mit Hauptheader + M Oberheadern mit je N Unterheadern ist
    Aufwand = X*(n*(2*Jump() + 2*Auswertungheader()) + Auswertungheader(Hauptheader)
    ist mir zu groß...

    Das hatte ich mir hier auf Papier schon einmal entworfen und durchgerechnet. Ich werde es auch implementieren um die Performance zu messen um zu zeigen das es mit dem IndexTree schneller geht.

    Aber ich weiß immer noch nicht wie ich jetzt z.b. einen Sprung in einer solchen Datei um X Bytes machen kann. Wie sieht der Befehl dafür aus? bzw wie heißt er? Den rest erledigt dann das Manual 🙂



  • fseek



  • cl90 schrieb:

    ich nehme an das fopen() die Datei vorher komplett buffert bevor ich den Stream benutzen kann oder?

    Nicht komplett. Du kannst aber die Puffergröße ändern, bzw. eigenen Speicher dafür bereit stellen.

    cl90 schrieb:

    Datenbanken sind zu Langsam

    Datenbanken sind für solche Zugriffe optimiert.

    Belli schrieb:

    fseek

    😃

    OMG eine Funktion die es auch in der C-Standardlibrary gibt.



  • DirkB schrieb:

    cl90 schrieb:

    Datenbanken sind zu Langsam

    Datenbanken sind für solche Zugriffe optimiert.

    Datenbanken bieten atomare Zugriffe, Crash-Recovery, Benutzerrechte und SQL-Queries,
    dafür zahlst Du aber auch locker den Faktor 1000 bei trivialen Anfragen.


Log in to reply