Hi,

ich habe eine beliebige Datei und muß in dieser eine bestimmte byte-folge finden... bei einer 1mb datei geht das ja noch recht schnell wenn ich einfach byte für byte durchgehe und suche.. aber wie kann man sowas performant bei einer 500mb großen datei machen?

Die datei komplett in den RAM laden ist denke ich eher ungünstig ab einer gewissen größe.. also müßte man immer block weise lesen und dann diesen block durchsuchen.. da muß man dann aber beachten das die gesuchten bytes evtl genau zwischen zwei blöcken liegen etc..

Hat da jemand eine andere performante idee?

Aya~

PS: Ich brauchte das ganze in C++.. aber das sollte im grunde keinen unterschied machen.


Moderiert von Narses: Topic aus Sonstiges (Delphi) verschoben am Fr 06.03.2009 um 15:37

Bei so großen dateien würde ich auch über einen Buffer lesen. Wenn man "in die Nähe" des Endes des Buffers kommt, muss man halt ein neues Stück lesen, und dabei ggf. das noch nicht untersuchte alte Bufferstück übernehmen.

Also Buffer lesen, Buffer überprüfen bis Buffergröße-Bytemustergröße, Rest an den Anfang kopieren, Buffer mit neuen Daten aus dem Stream befüllen. Das bis zum Ende der Datei.

Wie groß ist denn die Bytefolge? Wenn die etwas länger ist (d.h. z.B. 10 Bytes oder mehr), dann dürfte das Boyer-Moore-Verfahren eine deutliche Verschnellerung bedeuten. Das sit zwar eigentlich für die Stringsuche gedacht, funktioniert aber auch ganz gut (d.h. eigentlich noch besser) bei beliebigen Bytestreams.

Und ich würde mir das FastCode Projekt einmal anschauen, gerade für CompareMem oder ähnliche Probleme gibt es dort schnelle Implementierungen, da kannst du dir vielleicht auch etwas abschauen oder benutzen.
www.fastcode.dk/fast...stcodeproject/60.htm
Und die Implementierungen selbst:
www.fastcode.dk/fast...deCompareMemUnit.pas

Gausi hat folgendes geschrieben :

Wie groß ist denn die Bytefolge? Wenn die etwas länger ist (d.h. z.B. 10 Bytes oder mehr), dann dürfte das Boyer-Moore-Verfahren eine deutliche Verschnellerung bedeuten. Das sit zwar eigentlich für die Stringsuche gedacht, funktioniert aber auch ganz gut (d.h. eigentlich noch besser) bei beliebigen Bytestreams.

Sind 17byte, werd mir das Boyer-Moore mal anschauen, danke

jaenicke hat folgendes geschrieben :

Und ich würde mir das FastCode Projekt einmal anschauen, gerade für CompareMem oder ähnliche Probleme gibt es dort schnelle Implementierungen, da kannst du dir vielleicht auch etwas abschauen oder benutzen. www.fastcode.dk/fast...stcodeproject/60.htm Und die Implementierungen selbst: www.fastcode.dk/fast...deCompareMemUnit.pas

Werd ich auch mal anschauen, danke~

Aya

Gausi hat folgendes geschrieben :

Also Buffer lesen, Buffer überprüfen bis Buffergröße-Bytemustergröße, Rest an den Anfang kopieren, Buffer mit neuen Daten aus dem Stream befüllen. Das bis zum Ende der Datei.

Ich würde stattdessen ja MMFs nehmen und mein View immer length(view)-length(needle) weiterschieben. Das dürfte schneller sein als manuelles einlesen und/oder umkopieren (und sparsamer, was Speicher angeht).

Wie wäre der Ansatz wie beim Shell-Sort ?

Du teilst den Buffer in verschiedene Hälften ein und suchst eben in diesen nach einer bestimmten Bytereihenfolge ?

MfG