Ich habe eine große binäre Datei (viele Gigabyte, also laden sie nicht in den Speicher), die ich nach allen Vorkommen der Zeichenfolge "icpf" suchen möchte.
Ich habe versucht, dafür std::search zu verwenden, wurde aber gerade dadurch gebissen, dass std::search nur für Vorwärts-Iteratoren funktioniert, nicht für Eingabe-Iteratoren.
Bietet die Standardbibliothek dafür eine schnelle Alternative? Oder muss ich die Suche manuell codieren (entweder in Chunks zu einem Zeitpunkt lesen, dann std::search auf diesen, oder ignore alles bis ein 'i' und dann manuell die nächsten drei Zeichen überprüfen)?
Bietet die Standardbibliothek dafür eine schnelle Alternative?
Obwohl die C ++ - Standardbibliothek Möglichkeiten zum Suchen von Text-Streams bietet, bietet sie keine vergleichbaren Algorithmen für binäre Streams.
Oder muss ich die Suche manuell codieren (entweder in Chunks zu einem Zeitpunkt lesen, dann
std::searchauf diesen, oder alles bis zu einem'i'ignorieren und dann manuell die nächsten drei Zeichen überprüfen)?
Das Codieren des "Überspringens und Suchen" -Ansatzes könnte schwierig sein, da es einfach ist, eine Lösung zu programmieren, die Einträge überspringt. Wenn Sie beispielsweise in einer Datei, die "icpf" enthält, nach "icpicpf" suchen, wird ein einfaches Programm, das jeweils ein Zeichen verarbeitet, "icpf" suffix nicht finden, nachdem "icpi" Präfix verworfen wurde.
Wenn Sie das selbst programmieren wollen, sollten Sie Knuth implementieren -Morris-Pratt-Algorithmus . Es gibt viele Implementierungen online verfügbar, und es funktioniert ordnungsgemäß auf Streams, da es ein Zeichen auf einmal berücksichtigt und nie zurückgeht.
Die schnellste Methode besteht darin, die gesamte Datei in den Speicher zu laden und dann den Speicher zu durchsuchen.
Die nächstbeste Alternative ist, die Festplatte in Bewegung zu halten. Vielleicht haben Sie einen Thread, der Datenblöcke in einen Puffer liest, und einen anderen Thread, der den Puffer durchsucht.
Wenn Sie in der Liste nach unten gehen und große Datenblöcke in einen Puffer einlesen, ist die Suche im Puffer eine gute Technik, obwohl sie nicht so effizient ist wie die vorherigen Methoden.
Sie könnten Zeile für Zeile mit std::getline und std::string lesen. Dies ist nicht so schnell wie das Lesen von Blöcken, da die Eingabefunktion nach dem Newline-Zeichen sucht (und Speicher in std::string zuweist).
Im schlimmsten Fall liest man wahrscheinlich Zeichen für Zeichen. Der Funktionsaufwand ist schlecht für das Lesen einzelner Zeichen (normalerweise ist der Aufwand für das Lesen eines großen Datenblocks gleich).
Nein, es gibt keine standardmäßige C ++ - Bibliotheksfunktion zum Durchsuchen von Dateien. Einige Betriebssysteme verfügen über Dienstprogramme zum Durchsuchen von Dateien. vielleicht kannst du einen davon benutzen.
Bearbeiten 1:
Der Engpass ist die Eingabe der Daten. Sobald Sie die Daten in einen Puffer bekommen haben, gibt es viele effiziente Suchalgorithmen anstelle der rohen Gewalt (Suche nach dem ersten Buchstaben, dann Suche nach den nächsten Buchstaben usw.).
Suchen Sie im Internet nach "String Search Algorithm".
Ich kenne keine reine Standard-Bibliothekslösung, aber der Kernel implementiert bereits Prefetching, daher sollte es möglich sein, mmap() die Datei zu bekommen, um die benötigten Vorwärts-Iteratoren zu erhalten: (Fehlerbehandlung weggelassen)
Es ist ein kleiner Vertrauensvorschuss, der darauf beruht, dass Ihr Kernel das Laden, Prefetching und Verwerfen der Lazy korrekt durchführt. Auf der anderen Seite, wenn Sie jemandem damit vertrauen können, wären es wahrscheinlich Kernel-Entwickler.
Disclaimer: Ich habe das nicht wirklich auf einer Multi-Gigabyte-Datei getestet.