Konzeptfrage: **schnelles** Suchverfahren in Strings gesucht

[juergen]

Hallo zusammen,

bis jetzt hatte mir das Suchen innerhalb xList-Abkömmlingen über pos gereicht. Auch bei 30.000 Einträgen ist das Ganze noch ziemlich flott.
Nun nutzen die Anwemder mein Tool anders wie geplant :stupid: und lesen sich alle Dateien aller möglichen Partitionen in eine TStringList ein....
(zw. 100.000 - 600.000 Einträgen!!!)

Hier genügt das oben genannte Suchverfahren aus zeitlichen Gründen nicht mehr.

Jetzt habe ich schon einiges gelesen, u.a. über Boyer-Moore mit teilweise auch widersprüchlichen Anwendungsempfehlungen.
Man kann da sehr viel lesen.
Durch die Komplexität fällt es mir schwer zu erkennen, welches Verfahren für meine Anforderungen nun zu empfehlen ist. :oops:
Hier bräuchte ich Eure Ratschläge.

Meine Vorgaben sind:
- es wird immer nur mit 1 Suchwort gesucht
- gefunden werden sollen dann alle Vorkommen (Suchwort=ich wird auch in nicht gefunden)
- die zu durchsuchenden Strings sind Dateinamen von Dateien
- jeder Treffer muss in eine Listbox "landen"
- ab dem 3. Buchstaben wird erst angefangen zu suchen

Meine Fragen:
1.) welche Datenhaltung ist hier zu empfehlen? Im Moment findet diese in 2 TStringList statt (1 TStringList für Pfad + Dateiname, in der 2. TStringList stehen nur die Dateinamen, die zu durchsuchen sind).
2.) welcher Such-Algorithmus ist zu empfehlen?
3.) Gelesen hatte ich auch oft von sortierten (?) Array. Spielt das hier überhaupt eine Rolle? Die Daten in der TStingList sind nach Dateiname sortiert. Das Suchwort kann ja überall vorkommen.

Vielen Dank schon mal für Eure Unterstützung!

[Bernhard Geyer]

Wenn du etwas mit JNI und Java oder .NET anfangen kannst/willst -> Lucene

[himitsu]

Da du innerhalb der Strings suchen willst, macht sortiert oder unsortiert keinen Unterschied.

Zitat:

- jeder Treffer muss in eine Listbox "landen"

Ich befürchte auch, das hier eher ein größerer Flaschenhals entsteht, als daß das Suchverfahren (Pos, Boyer-Moore und Co.) seine Auswirkungen zeigt.

In D2007 dürfte doch auch schon das bessere "Pos" aus dem FastCodeProjekt enthalten sein,
oder wurde FastCode erst in D2009 integriert?

schau einfach mal, ob sowas in deinem Delphi drinnen ist.

Delphi-Quellcode:

(* ***** BEGIN LICENSE BLOCK *****
 *
 * The function Pos is licensed under the CodeGear license terms.
 *
 * The initial developer of the original code is Fastcode
 *
 * Portions created by the initial developer are Copyright (C) 2002-2004
 * the initial developer. All Rights Reserved.
 *
 * Contributor(s): Aleksandr Sharahov
 *
 * ***** END LICENSE BLOCK ***** *)
function Pos(const substr, str: RawByteString): Integer; overload;
asm
       push  ebx

[scrat1979]

... gibt es bei Listboxen nicht auch

Delphi-Quellcode:

ListBoxName.BeginUpdate;
[...]
ListBoxName.EndUpdate;

... vielleicht kitzelt das noch was raus!

[juergen]

Guten Morgen!,
schon mal Danke an der Stelle für die Antworten! :dp:
@ Bernhard Geyer
Ich bin froh dass ich ein ganz klein wenig mit Delphi zurecht komme. Andere Sprachen kommen mir da nicht ins Haus! :stupid:
@ himitsu
die Unit aus dem FastCodeProject verwende ich schon. :mrgreen:
(ich glaube nicht dass das schon in D 2007 drin war, die Verwendung der FastPos-Funktion brachte meßbaren Tempozuwachs, aber ich werde heute Abend mal nachschauen)

Zitat:

Zitat von himitsu

Ich befürchte auch, das hier eher ein größerer Flaschenhals entsteht, als daß das Suchverfahren (Pos, Boyer-Moore und Co.) seine Auswirkungen zeigt.[/delphi]

I.d.R. werden nur wenige Dateien gefunden, die den Suchkriterien entsprechen (zw. 10 ... 200)
Das sollte für die Listbox kein Zeitproblem darstellen.

@scrat1979
Update-Funktionen verwende ich schon, dürften hier aber auf Grund der geringen Anzahl der Datensätze keine große Rolle spielen.


Zu meiner 1. Fragen:
- bietet sich hier vllt. ein Array an als wirklich schnellere Alternative zu einer TStringList?

[alzaimar]

So wie ich das sehe, willst du eine Liste durchgehen und jeden Eintrag per 'Pos' o.ä. durchsuchen.
Das bringt nicht viel, egal wie schnell das Pos ist, da die Strings ziemlich kurz sind und da die optimierten Algorithmen noch nicht richtig greifen.

Die schnellen String-Matching-Algorithmen spielen ihre Stärken erst bei langen Strings aus.
Du könnstes also deine Liste anstatt in 600.000 einzelnen Strings in einem einzigen sehr langen String vorhalten. Das Suchen würde also dann nur in einem String stattfinden.

Zufällig ( :mrgreen: ) habe ich da etwas für Dich. Ich hab das mal benötigt, um in einer Adressliste mit 1 Mio Einträgen in Echtzeit ('while you type') passende Adressen zu suchen. Ich breche allerdings nach 500 Einträgen ab, weil sonst eine merkliche Verzögerung eintritt. Je länger der Suchtext, desto schneller das Teil.

Zaubern kann es allerdings auch nicht.

[hoika]

Hallo,

weisst du denn überhaupt schon, wo es klemmt ?

Es gibt für Delphi auch FreeWare-Profiler.

600.000 Strings könnten auch zum Swappen auf die Platte führen (könnten).

Das würde ich erst mal durch einen Test ausschließen.


Heiko

[juergen]

Hallo zusammen,

@alzaimar,
vielen Dank für deine Unit! :thumb: :-D
Ich komme allerdings erst am Wochenende dazu mir das näher anzuschauen *Spannung wächst* :mrgreen:
Dein Ansatz alles in 1 String zu packen hört sich sehr interessant an. Bin mal gespannt wie die Ergebnisse sein werden.

@hoika,
ich glaube nicht das es irgendwo "klempt".
Falls jemand andere Erfahrungen mit TStringList und Pos gemacht wäre es natürlcih sehr interessant zu wissen.
Auf meinem Rechner benötige ich für die Suche mit 3 Zeichen in 133.700 Dateinamen ca. 560 ms. Bei 4 Zeichen Suchtext sind es nur noch 52 ms.
Ich denke hier wird einfach das Limit der Hardware und der Kombination von TSringList und Pos erreicht sein, oder?
Bei den Anwendern dauert es wohl deshalb länger, weil die Dateinamen länger sind (kommen vom Server und da sind viele Dateien selbstsprechend benannt)
und weil die Harware da nicht ganz so schnell ist.
Swappen auf Festplatte: kann natürlich sein, da werde ich bei nächster Gelegenheit mal ein Auge auf den Speicherverbrauch werfen
Danke!

Edit
@himitsu,
du hattest Recht, in D 2007 wird schon das pos aus dem FastCode-Projekt verwendet. Gut zu wissen!
Habe gerade gesehen, dass ich die FastPos-Unit hier aus der DP nutze! FastPos


Allen eine Gute N8!

[juergen]

Hallo zusammen,

@alzaimar,
für heute bist du mein Held!!! :oops:

Meine Messungen haben folgende Ergebnisse geliefert.

gemessen in einer VM, mit 5.000.000(!) Strings, jeder String 64 verschiedene Zeichen lang, das gesuchte Wort steht im letzten String)
Zeichenlänge des Suchtextes----------TSringList & DPPos---------alzaimar Methode
3-------------------------------------------------4,117 sek--------------------1,955 sek
6-------------------------------------------------4,290 sek--------------------1,420 sek
9-------------------------------------------------4,329 sek--------------------1,092 sek
12------------------------------------------------4,329 sek--------------------0,892 sek
15------------------------------------------------4,359 sek--------------------0,820 sek

(wie funktionieren hier eigentlich Tabs oder Leerzeichen :gruebel: )

gemessen in einer VM, mit 600.000 Strings, jeder String 64 verschiedene Zeichen lang, das gesuchte Wort steht im letzten String)
Zeichenlänge des Suchtextes----------TSringList & DPPos---------alzaimar Methode
3-------------------------------------------------493,882 ms--------------------236,456 ms
6-------------------------------------------------515,048 ms--------------------171,228 ms
9-------------------------------------------------520,652 ms--------------------123,753 ms
12------------------------------------------------517,234 ms--------------------111,681 ms
15------------------------------------------------500,202 ms--------------------92,171 ms

Da das Suchwort nur 1x im letzten String vorkommt, hat das "Adden" der Listbox das Messergebnis kaum beeinflusst.



Ich werde bei mir auch eine Begrenzung auf 200 Einträge in die Listbox einbauen, bzw. werde einen Checkbox setzen
wo man dann optional auch alle Einträge einfügen lassen kann.


Also nochmals vielen Dank alzaimar, die Steigerungen sind schon enorm!

[himitsu]

Zitat:

Zitat von juergen

(wie funktionieren hier eigentlich Tabs oder Leerzeichen :gruebel: )

nimm das [code]-Tag

Zitat:

Zitat von juergen

Ich werde bei mir auch eine Begrenzung auf 200 Einträge in die Listbox einbauen, bzw. werde einen Checkbox setzen
wo man dann optional auch alle Einträge einfügen lassen kann.

dort hab ich es auch begrenzt und als Letztes dann einen Eintrag eingemacht ... wenn man diesen auswählt/anklickt, dann wird alles eingefügt.
http://www.delphipraxis.net/internal...=976287#976287