Schnelle Suche in einem großen Puffer?
-
Ich versuche mich gerade daran, den Inhalt einer Text-Datei auf bestimmte Schlüsselworte abzusuchen. So wird also erstmal der Inhalt in einen char-Buffer eingelesen, und nun wollte ich clever sein und setzte den Inhalt wiederum in einen AnsiString, um komfortabel über AnsiPos die gewünschten Schlüsselworte zu finden. Dies funktioniert soweit, allerdings mit einem Haken: Die Suche ist langsam. Dazu kommt noch, dass die Schlüsselworte mehrmals in dem Text vorkommen und ich deshalb weitersuchen muss - AnsiPos sucht allerdings nur das erste Vorkommen, daher extrahiere ich den Rest-String nach einem Fund mittels SubString und suche dort weiter. Das Resultat ist eine quälend langsame Angelegenheit und AnsiString spielt die Hauptrolle, dazu gesellt sich die Dateigröße, welche ohne Probleme 4MB überschreitet. Im Grunde ist also diese Suche aufgrund der miesen Geschwindigkeit ungeeignet.
Da ich also offensichtlich nicht allzu versiert mit C++ bzw. dem Builder bin, frage ich Euch um Rat, wie man hier eine schnelle und effiziente Suche realisieren kann. Sollte ich sie evtl. selber programmieren, also eine manuelle Suche ohne Nutzung spezieller Suchfunktionen wie AnsiPos?
Hier noch ein kurzer Ausschnitt des Code-Grundgerüsts, vielleicht erklärt sich ja jemand bereit, es zu ergänzen?
int fHandle, fLength, fBytesRead; char *buf; fHandle = FileOpen(OpenDialog->FileName, fmOpenRead); fLength = FileSeek(fHandle, 0, 2); FileSeek(fHandle, 0, 0); buf = new char[fLength+1]; fBytesRead = FileRead(fHandle, buf, fLength); FileClose(fHandle); // her her mit der Suche!Danke!
-
Tolles Grundgrüst ...
Du musst schon mal zeigen, wie du deine Suche implementiert hast.
-
Das Grundgerüst soll lediglich einen Startpunkt darstellen; die Daten stehen bereit und wollen nun durchsucht werden. Meine Suche war wie erwähnt zu langsam, selbst ein einziger AnsiPos-Aufruf in der Suchschleife führt zu einem massiven Geschwindigkeitseinbruch. Deshalb wollte ich den Code garnicht erst hier reinsetzen, da ich den Ansatz allein schon schlicht für untauglich halte.
Zum Ausschnitt:
Im Grunde wird die Datei, welche ein spezielles Layout hat, auf sieben verschiedene Worte (sTerms) untersucht. Wird eins gefunden, so wird ein bestimmter Teil, der danach folgt, in die Listbox eingetragen.void __fastcall TForm1::OpenDialogClick(TObject *Sender) { int fHandle, fLength, fBytesRead; char *buf; AnsiString *fCont; AnsiString sTerms[] = { "skyname", "material", "texture", // search terms "model", "noise1", "noise2", "message" }; int sTermPos=1, sMark; int sTermNum = sizeof(sTerms) / sizeof(sTerms[0]); if (OpenDialog->Execute()) { fHandle = FileOpen(OpenDialog->FileName, fmOpenRead); fLength = FileSeek(fHandle, 0, 2); FileSeek(fHandle, 0, 0); buf = new char[fLength+1]; fBytesRead = FileRead(fHandle, buf, fLength); FileClose(fHandle); fCont = new AnsiString; for (int i=0; i < sTermNum; i++) { // search all terms *fCont = AnsiString(buf); sTermPos=1; while (sTermPos > 0) { sTermPos = fCont->AnsiPos(sTerms[i]); // find the term if (sTermPos > 0) { // cut the previous data from the string *fCont = fCont->SubString(sTermPos + sTerms[i].Length() + 3, fCont->Length() - (sTermPos + sTerms[i].Length() + 2)); sMark = fCont->AnsiPos('"'); // find the next quotation mark and .. if (ListBox1->Items->IndexOf(fCont->SubString(1, sMark-1)) == -1) { // only add when not listed yet ListBox1->Items->Add(fCont->SubString(1, sMark-1)); // ..copy the data inbetween into the listbox ListBox1->Update(); } *fCont = fCont->SubString(sMark+1, fCont->Length()-sMark+1); // cut the string again to avoid false positives } } } delete [] buf; delete fCont; } }
-
Hi,
vielleicht wäre es eine Idee, die Worte aus der Textdatei einzeln in einen Binärbaum einzulesen. Anschließend suchst Du in Deinem Baum nach den Schlüsselworten.
Klar, das einlesen dauert auch erst einmal etwas Zeit, danach kannst Du aber im Baum sehr schnell suchen. Die Effizienz hängt aber sehr stark vom Autor des Textes ab. Je größer sein Wortschatz ist, umso besser ist auch die Baumverteilung. Bei einem kleinen Wortschatz kann der Baum relativ schnell ungleichmäßig werden, kann man aber durch Erzeugung einer Grundstruktur eventuell vorbeugen...
Vielleicht hilft Dir die Idee.
VG Pixfreak
-
Im Grunde hat es sich erledigt. Ich habe gestern noch testweise eine Suchfunktion gebastelt, welche ohne Umwege den char-Puffer untersucht. Ist, warum auch immer, wesentlich effizienter und somit genau das was ich hier brauche. Dennoch danke für die Antowrt
-
Zeig doch mal, ggf. lernen wir auch noch was.
-
Joa kein Problem.
Einen kleinen Haken hat die Suche noch, ich weiß nicht genau warum: Das zwote if-statement in der zwoten for-Schleife enthalt einen auskommentierten Check, der eigentlich sicherstellen soll, dass bei einem Match vor dem eigentlichen Suchwort ein Anführungszeichen steht, um false positives zu vermeiden (alle Suchworte in der Datei stehen in Anführungszeichen). Wenn ich diesen Check wieder in den Code implementiere bekomme ich aber kurz nach dem Start der Suche einen Ausnahmefehler (Access Violation) und werde vom Editor in die dstring.h geworfen - ich bin mir nicht sicher warum. Alternativ könnte ich die Anführungszeichen direkt in die Suchbegriffe integrieren, nur schneidet AnsiString diese wieder ab, soweit ich das mit meinen Kenntnissen beurteilen kann. Gibt es eine Möglichkeit, Strings mit Anführungszeichen zu speichern?Ansonsten funktioniert die Suche und ist bei weitem schneller als die AnsiString-Methode, vlt. hatte ich bei der aber nur etwas verkehrt gemacht.
void __fastcall TForm1::ScanMapClick(TObject *Sender) { int fHandle, fLength, fBytesRead; char *buf; AnsiString sTerms[] = { "skyname", "material", "texture", "model", "noise1", "noise2", "message" }; int sTermPos=1; int sTermNum = sizeof(sTerms) / sizeof(sTerms[0]); AnsiString s; if (ScanMapDialog->Execute()) { if (!FileExists(ScanMapDialog->FileName)) return; fHandle = FileOpen(ScanMapDialog->FileName, fmOpenRead); fLength = FileSeek(fHandle, 0, 2); FileSeek(fHandle, 0, 0); buf = new char[fLength+1]; fBytesRead = FileRead(fHandle, buf, fLength); FileClose(fHandle); ProgressBar1->Max=sTermNum; StopScanProcess=false; for (int i=0; i < sTermNum; i++) { // start the search SearchNameLabel->Caption = sTerms[i]; SearchNameLabel->Update(); sTermPos=1; for (int j=0; j < fLength; j++) { if (buf[j] == sTerms[i][sTermPos]) { // check if all chars found & if the char in front of it is a quotation mark if (sTermPos++ == sTerms[i].Length() /*&& j-sTerms[i].Length()>-1 && buf[j - sTerms[i].Length()] == char(34)*/) { j += 4; do { // get all chars until reaching a quotation mark s = s + buf[j++]; } while (buf[j] != char(34)); if (ListBox1->Items->IndexOf(s) == -1) { // add it to the Listbox if not already there ListBox1->Items->Add(s); ListBox1->Update(); } s=""; sTermPos=1; } } else sTermPos=1; Application->ProcessMessages(); if (StopScanProcess) { delete [] buf; return; } } ProgressBar1->Position=i+1; } ProgressBar1->Position = ProgressBar1->Max; SearchNameLabel->Caption = "Progress"; delete [] buf; } }
-
[Edit]
Hat sich erledigt, war ein Semantikfehler in der Suche. Danke für's Vorbeischauen
[/Edit]Ich würde gern nochmal auf mein Problem mit dem Check (Zeile 35) aufmerksam machen. Hier nochmal ein Ausschnitt mit dem betreffenden Code:
if (sTermPos++ == sTerms[i].Length()) if (buf[j - sTerms[i].Length()] == char(34)) { ... }Nachdem ein komplettes Match in der Suche festgestellt wird (Zeile 1), wird in Zeile 2 noch getestet, ob VOR dem Suchwort im Puffer ein Anführungszeichen steht, um von vornherein false positives zu vermeiden. Führe ich den Code so aus, bekomme ich aber einen Ausnahmefehler (Access Violation) mit Verweis auf die dstring.h Zeile 150 (ThrowIfOutOfRange(idx);). Allerdings bin ich zu dem Schluss gekommen, dass der Index, mit dem hier auf den Puffer zugegriffen wird, nie "out of range" sein kann.
Ein kleiner Test bestätigte dies:
if (sTermPos++ == sTerms[i].Length()) if (buf[j - sTerms[i].Length()] != char(35)) { ... }Hier habe ich den Vergleich leicht geändert, "==" wurde zu "!=" und char(34) zu char(35). Und dieser Code funktioniert!
Und so habe ich festgestellt, dass der Ausnahmefehler nur dann ensteht, wennbuf[j - sTerms[i].Length()] == char(34)
false ergibt. Solange true rauskommt, gibt es keinen Fehler.
Ich wäre sehr dankbar, wenn jemand eine Erklärung dazu hätte!
-