Frage wegen BinaryReader / Threads

[blubbla]

Hallo,

habe folgendes Problem (unter C#):

Ich muss in einem Binärfile ein bestimmtes Suchmuster finden.

Die Dateien sind ca. 4 - 10 Mbyte gross, zu finden ist eine eindeutige Zeichenfolge von ca. 10 bytes.

Bis jetzt speichere ich das Suchmuster einfach in einem byte-Array, lese das Binärfile mit einem BinaryStreamReader aus und prüfe mit einer for-Schleife, ob das Suchmuster vorliegt.

Sieht dann ca. so aus:

for (int i = 0; i < (fs.Length); i++)

            {

                baseP = br.BaseStream.Position;

                for (int y = 0; y < muster.Length; y++)

                {

                    if (br.ReadByte() == (muster[y]))

                    {

                        matchFound = true;

                    }

                    else

                    {

                        matchFound = false;

                        br.BaseStream.Position = (baseP + 1);

                        break;

                    }

                }

                if (matchFound == true)

                {                  

                    return matchFound;

                }


            }

Das dauert in einer 4 Mbyte großen Datei ca. 10 Sekunden. Würde nun gerne mit Threads arbeiten, damit ich das noch a bisserl beschleunigen kann.

Jetzt meine Frage: Wie gehe ich im Hinblick auf Threads mit dem Lesezugriff auf Dateien um? Wenn ich einfach 2 Threads starte, von dem der Erste den Bereich von 0 - Länge/2 und der Zweite den Bereich Länge/2+1 - Ende durchsuchen soll, gibts logischerweise öfter mal ne Exception. Soll ich einfach eine Art Semaphor programmieren, damit ein Prozess exklusiven Lesezugriff auf die Datei hat und ansonsten wartet, oder gibts da eine einfache und schnelle Möglichkeit in C#? Oder anders gesagt, hätte jemand eine andere Idee wie ich in großen Binärfiles nach Bytemustern suchen kann?

[Pointerman]

Moin!

Wenn ich mich nicht stark taeusche sollte das Lesen aus einer Datei Problemlos zeitgleich funktionieren. Warum sollte dabei auch gesperrt werden, es werden ja keine Zeichen "weggelesen".

D.H. solltest Du gleichzeitig mit 2 Readern auf die Datei zugreifen koennen.

Eine Vermutung ist noch, dass es schneller sein koennte, die Datei erst komplett zu Laden und dann zu verarbeiten, da das Lesen einzelner Bytes sehr langsam ist.

Je nach Dateigroesse koenntest Du dann auch einfach grosse Bloecke einlesen, aber wenn es bei den 10MB bleibt solltest Du das nicht brauchen.

Ausserdem solltest Du in Deiner Aeusseren Schleife, die ueber den ganzen Stream marschiert noch pruefen, ob ein Treffer gefunden wurde. Wenn naemlich im Worst Case Dein Suchwort ganz zu Anfang steht, suchst Du trotzdem fleissig weiter im restlichen Stream.

[blubbla]

Hi,

also erstmal danke für die Tips. Paralleles Lesen geht wirklich problemlos wie du sagtest, hab mich da bei einer Exception verschaut .

Im Moment funktioniert es zwar, es dauert aber trotzdem noch einige Zeit, besonders natürlich wenn das Suchmuster am Ende der Datei steht.

Meinst du mit "Datei erst komplett laden" dass ich das Binärfile per Memorystream in den Arbeitsspeicher schreibe, bevor ich die Suche beginne?

Habe gerade erfahren dass die Dateien doch bis zu 16 MB gross werden können, und das dauert auch mit Threads im Moment noch ca. 15 - 20 Sekunden.

[LadyPreis]

generell kann das komplette Einlesen einer Datei in den Arbeitsspeicher das ganze schon sehr beschleunigen. Hatte das gleiche Problem bei einem früheren Projekt. Generell solltest du dabei aber nicht außer acht lassen, dass dein Programm natürlich dann sehr hungrig nach Ressourcen ist; vor allem wenn du das ganze mit mehreren Datein parallel machst

[Bubble]

Das dauert in einer 4 Mbyte großen Datei ca. 10 Sekunden. Würde nun gerne mit Threads arbeiten, damit ich das noch a bisserl beschleunigen kann.

Bevor mehrere Threads bemüht werden, wäre es besser, das verwendete Sucherverfahren durch ein schneller arbeitendens auszutauschen.

[Pointerman]

Bubble hat schon völlig recht, dass ein anderes Suchverfahren Beschleunigung bringen könnte.

Es wird ja immer wieder gerne behauptet, dass unnötiges Multithreading Programme unnötig kompliziert macht. Stimmt im Grunde auch, aber gerade bei diesem Problem, bei dem ja keine Lese-/Schreibkonflikte auftreten können, könnte man schon drüber nachdenken.

Ja, ich meinte schon, dass Du die Datei ganz in den Speicher laden könntest. Der Zugriff auf einzelne Bytes ist einfach zu langsam. Bevor ich da auf Multithreading setzten würde, erstmal die Daten in größeren Blöcken laden. Ich habe mal ein Programm geschrieben, bei dem große Mengen Rohdaten anfielen und dann nach der Messung offline bearbeitet werden sollten. Da hat es sehr geholfen die Daten Blockweise einzulesen und zu verarbeiten, da es sehr viel schneller war als Byte für Byte. In Teilen und nicht ganz, weil Auslagern auch wieder kostet.

Nach Nutzen/Aufwand geordnet würde ich folgendes vorschlagen:

1. Blockweise/komplettes Laden der Dateien

2. Besserer Such Algorithmus

3. Multithreading

Du solltest dabei natürlich nach jedem Schritt testen, ob die Geschwindigkeit reicht. Man ist ja faul...

[VaNaTiC]

@Pointerman + @Bubble:

Welches Suchverfahren funktioniert denn für zufällige, beliebige und unsortierte Vorkommen bestimmter Daten?

@blubbla:

1) Du hast eine i-Schleife *und* eine y-Schleife?!

2) Wenn ich mich recht erinnere ist das Verändern des FilePointers mittels Stream.Position total ineffizient! Sowas muss man in einem Mem-Puffer machen.

3) Wenn dann wäre es besser nicht mit ReadByte 1 Byte zu lesen und mit dem Muster zu vergleichen, sondern mit ReadBuffer(), aber da das Muster sicherlich auch beim 2ten Byte starten könnte, wäre das hin- und herschaufeln zu komplex.

4) Also ist wie Lady bereits sagte das im Memory lesen und vergleichen schneller.

5) Prinzipiell brauch Dein Algorithmus nur eine Schleife und einen Merker:

Du durchläufst den Puffer der Datei von vorn und prüfst (von mir aus byteweise) das Puffer mit Muster[Merker], wenn das passt, dann Merker++, bis Merker=Muster.Länge (das wäre bereits fertig).

Wenn der Mustervergleich an der Merker-Stelle aber nicht passt, dann Merker=0 und weiter mit i-Schleife.

Schöner wäre es natürlich, wenn Du einen Speichervergleich machst, aber der wird it zunehmender Muster-Größe ineffizient. Deshalb ist ein Byteweises vergleichen besser.

[Pointerman]

@VaNaTiC

Welches Suchverfahren funktioniert denn für zufällige, beliebige und unsortierte Vorkommen bestimmter Daten?

Wenn ich mich beim schnellen Schauen nicht geirrt habe diese:

Boyer-Moore-Algorithmus

und

Algorithmus_von_Knuth-Morris-Pratt

Zu Punkt 1. Deiner Anmerkungen an blubbla:

Da passiert im Grunde nichts anderes, als in dem, von Dir in Punkt 5 beschriebenen Verfahren. Wenn das aktuelle Zeichen nicht mit dem Muster uebereinstimmt, wird aus der "y"-Schleife herausgeprungen, ansonsten wird weiter verglichen.

Bearbeitet 30. November 2009 von Pointerman

[VaNaTiC]

Stimmt Pointerman, da hätt ich selbst drauf kommen können (Boyer-Moore hab ich selber schonmal mit Delphi gemacht), aber von Strings- auf Byte-Daten konnt ich nicht abstrahieren

Mordsmäßig viel Zeit spare ich mir damit wahrscheinlich trotzdem nicht, da ich nur die Suchmuster-Vergleiche etwas reduziere, da ich weiter springe als nur bis zum nächsten Zeichen.

Im Prinzip ist das trotzdem nicht korrekt.

Entweder ich durchlaufe die i-Schleife von 0 bis Dateilänge-1 oder nur solange bis Positionszeiger kleiner/gleich Dateilänge, aber nicht beides. Das ist nicht gut und außerdem nicht schön.

[Pointerman]

Eigentlich ist Dateilaenge -1 auch nicht richtig. Es muesste Dateilaenge-muster.Length-1 sein.

Den Fehler an der y-Schleife kann ich immernoch nicht finden. Er sucht dann ja darin nicht bis zum Dateiende, sondern nur bis zum Ende des Suchstrings (und das nur, wenn er nicht vorher bemerkt, dass es nicht das Suchwort ist).

Das sollte, nach der Anpassung der aeusseren Schleife korrekt sein.

Wie ich in meiner ersten Antwort im Thread geschrieben habe, sollte er ausserdem in der aeusseren Schleife Pruefen, ob das Suchwort gefunden wurde, damit er nicht komplett durchlaufen muss.

[VaNaTiC]

*Eine* Muster-Schleife ist nicht zwingend falsch, sie ist nur doppelt-gemoppelt und deshalb unnötig, aber speziell in diesem Beispiel ist nicht die y-Schleife falsch, sondern das Durchlaufen auf Basis des Dateizeigers, den ich innerhalb der y-Schleife um eins inkrementiere ohne dabei die i-Schleife zu beachten. Und das passiert, weils doppelt-gemoppelt ist

[Pointerman]

Hast natürlich recht, an der Position rumdrehen, ohne i zu verändern ist natürlich Käse und würde Ärger verursachen.

An sich war die Idee aber nicht so schlecht, weil dann die länge des Suchwortes nicht wieder neu durchsucht werden muss. Allerdings dürfte dann die Position nicht so wie im code weitergesetzt werden, weil ja das letzte gefundene (erste falsche) Zeichen ja der Beginn eines Suchworttreffers sein könnte.

Das mit dem Doppeltgemoppelt habe ich aber immernoch nicht verstanden. Man läuft durch die Datei und prüft jeweils, ob das Suchwort an der Position enthalten ist. Was soll an der Überprüfung mit einer Schleife denn doppelt sein?

[VaNaTiC]

Ich hab mir einfach vorgestellt, dass dies mit nur einer Schleife und Merken von Positionen übersichtlicher ist.

[blubbla]

Hallo,

habe des mittlerweile so umgestellt, dass ich die Binärdatei zuerst in einen Memorystream lese und dann in diesem Stream nach dem Muster suche. Das ganze ist jetzt so schnell dass praktisch keine Wartezeit spürbar ist, danke für den Tip . Die Threads hab ich jetzt ganz rausgelassen.

Wegen Algorithmus nochmal: Bei meiner obigen Methode überprüft er doch nach jedem Schleifendurchlauf, ob der Ausdruck gefunden wurde, und wenn ja verläßt er die Funktion komplett. Für meinen Bedarf reichts jetzt im Prinzip aus, wenn ich Zeit könnte man ja auch nen richtigen Algorithmus implementieren