Entwickler-Ecke

Sonstiges (Delphi) - schnelle suche in TStringlist


matze - Fr 05.03.04 14:23
Titel: schnelle suche in TStringlist
hallo !!

ich habe ein stringlist in der so an die 10000 Zeilen drinstehen. das sind alles dateipfade.
wie kann ich denn am besten diese liste nach einem begriff durchsuchen und alle zeilen in der dieser begriff vorkommen mir zurückgeben lassen ??

ich rödel im moment in einer for schleife durch die liste durch und prüfe mit pos ob der begriff vorkommt. das dauert aber ewig. ich bräuchte da ne schnellere lösung um die daten zu durchsuchen. gibt es da ne lösung ?? es muss ja nicht unbedingt ne stringliste sein.


Popov - Fr 05.03.04 17:49

Bei sowas habe ich mir angewöhnt direkt schon beim Einlesen alles AnsiUpperCase zu setzte. Das hat den Vorteil, daß man es schon mal später nicht machen muß, was noch langsammer ist, da man unter Umständen doppelt macht. Ist also schon alles groß, dann ist eine Quelle ausgemerzt.

Alternativ ein mal StringList.Text := AnsiUpperCase(StringList.Text) machen und schon spart man sich wieder AnsiUpperCase beim Prüfen.

Eine weitere Möglichkeit ist, wenn du nur ein bestimmten Begriff suchst, daß du POS nicht jeden String einzeln prüfst, sondern nur einen (z.B. POS('BLABLA', StringList.Text)).

Aber ich müßte schon etwas mehr wissen bevor ich ich weiter spekuliere.


matze - Fr 05.03.04 18:31

also es ist einfach ein stringlist in der ein haufen dateinamen inkl pfade drinstehen (in der form c:\blabla.txt).
der user tippt in ein editfeld einen begriff ein und bekommt us der stringliste alle pfade rausgesucht, bei dem der begriff vorkommt.
as simple as that !
nur die methode mit pos und der for-schleife ist elendig langsam !
um die sagen wir mal 10000 zeilen durchzuackern braucht die so um ne minute !! und das ist zu lang !


Delete - Fr 05.03.04 19:38

Hilft dir IndexOf ein bisschen?


matze - Fr 05.03.04 20:29

damit bekommt man aber nur das erste vorkommen dieses strings zurück !
geht es denn schnelle, wenn man die stringliste in ein array verlagert und das dann durchackert ?


AndyB - Fr 05.03.04 23:42

matze hat folgendes geschrieben:
geht es denn schnelle, wenn man die stringliste in ein array verlagert und das dann durchackert ?

Was denkst du steckt hinter TStringList ?


matze - Sa 06.03.04 09:33

oh stimmt ja.... :oops:
aber es muss doch irgendwie schneller gehen....

wie machen denn datenbanken das, dass sie so schnell in einer masse von zeilen suchen können ?


catweasel - Sa 06.03.04 10:22

Zitat:
wie machen denn datenbanken das, dass sie so schnell in einer masse von zeilen suchen können ?

Indem Datenbanken diese Listen Indizieren....


Du legst zu jedem Begriff der eingegeben wurde eine Liste an mit den Positionen der Einträge der STringlist in denen dieser Begriff vorkommt....
Damit dauert zwar das erste suchen genausolange wie beisher, aber jedes wiederholte Suchen erfolgt sehr viel schneller...
Damit das nicht ausufert könntest du das auf die letzten 10 Suchbegriffe beschränken oder so...

Sollten bestimmte Begriffe "Standard" sein und häufiger eingegeben werden könntest du auch deren Vorkommen beim einlesen in ein separates Feld speichern (Record definieren und ain array verwenden, anstelle von Stringlist) und müsstest nur einen entspechenden boolwert abfragen..
Eine Suche nach diesen Werten wäre schon von vornherein "schnell"...

Catweasel


matze - Sa 06.03.04 11:07

das ist bei meinem problem problematisch !!

das ganze soll nämlich eine suche werden, für MP3 files die auf dem rechner liegen. der user soll nach dem namen der MP3 datei suchen können. da hätte ein slcher index nicht wirklich sinn, weil der user ja meistens nicht immer nach genau ein un demselben begriff sucht.


Popov - Sa 06.03.04 11:41

Eine Suche dauert so lange wie sie dauert.

Was man aber machen kann (das ist allerdings nur ein optscher Trick), das ist eine ProgressBar einbauen. Dadurch wird es nicht schneller (sogar langsammer), aber der User sieht zumindest wie lange es noch dauert.

Eine weitere Möglichkeit wäre das Ganze schon vorher zu zerlegen. Gib die Suche nach einer schnelleren Möglichket auf und vereinfache die Suche. Ich weiß nicht ob permanent die 10000 Dateinamen eingelesen werden oder ob sie nur ein mal eingelesen werden und das war's dann fürs erste. Denn da kannst du mit Tricks arbeiten:

Trick1: Vor dem ersten Durchlauf sortierst du deine Liste alphabetisch (z.B. nach Dateinamen). Dann erstellst du in einem Array ein alphabetisches Index mit 26 Werten. In dem schreibst du A fängt bei 0 an, B bei 234, C bei 789, usw. Der Vorteil ist, daß du bei der Suche nach einem B Titel nicht alles durchsuchen mußt, sondern nur noch zwischen 234 und 788.

Trick2: Du erstellst eine einfache Record Klasse und fügst sie an deine Stringlist an. In einer so aufgebauten Liste hast du viel mehr Freiheiten. Zuerstmal weg mit dem Pfad. Den kannst du in das angehängte Objekt verbannen. In der Stringlist sind dann nur noch die Namen selbst zu finden. Ich tippe drauf, daß die Suche dann viel schneller geht, da man sich die Suche im Pfad ersparrt. Noch besser wäre es in dem angehängten Objekt nur einen Char mit dem ersten Buchstaben des Dateinamen anzubietet. Das müßte noch schneller gehen, denn hier würde man weder ein ganzen Pfad Prüfen, noch eine ganze Datei, sondern zuerst mal nur einen Buchstaben. Erst wenn der Buchstabe übereinstimmt wird die Suche erweitert.

Aber um dir richtig zu helfen müßte ich z.B. zwei Beispielpfade haben und Ifos nach was in den Pfaden gesucht werden soll. Weill so wird es nur eine Raterei. Bib also paar Beispiele und nach was gesucht werden soll. Dann kann man die optimalste Suche entwickeln.


matze - Sa 06.03.04 11:50

ok hier also mal ein ausschnitt aus der ´stringliste, die ich einmalig per rekursiver dateisucher erstelle:

Quelltext
1:
2:
3:
4:
C:\cd\MP3 CD\MP3's\Songs\## Artist - Dungeon Keeper 2 Theme.mp3
C:\cd\MP3 CD\MP3's\Songs\## Artist - I am the God of Hell Fire.mp3
C:\cd\MP3 CD\MP3's\Songs\## Artist - It's a life.mp3
C:\cd\MP3 CD\MP3's\Songs\## Artist - James Bond Theme.mp3

und der user such z.b. nach bond. dann soll natürlich das james bond theme erscheinnen, aber auch alle anderen MP3s bei denen das wort bond in dem dateinamen vorkommt


Popov - Sa 06.03.04 12:59

Also ich hab hier mal was geschrieben, stellte dann aber fest, daß die suche bei mir (AMD 1600+) bei 10000 Items gerade mal 0,5 Sekunden dauert. Ich hab es "nichtoptimiert" versucht und es waren so 1 Sekunde. Also ich weiß nicht was du falsch machst, aber die Suche in 10000 Items ist ein Klacks.

Aber ich will den Code nicht umsonst geschrieben haben. Was aber noch fehlt ist die Freigabe der angehängten Objekte. Mit dem Löschen des Items ist es nicht genug. Die angehöngten Objekte müssen separat freigegeben werden. In dem Code fehlt dieser Teil. Hier aber ein Beispiel wie man die Pfade zerlegen kann. Gesucht wird das Wort "Theme" und es wird in ListBox2 ausgegeben:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
type
  TMp3List = class
    Pfad: String;
    Kurzname: String;
  end;

var
  Liste: TStringList;

procedure TForm1.Button_StartClick(Sender: TObject);
var
  k, m: Integer;
begin
  // Liste generieren (10000) Eiträge

  with ListBox1 do begin
    Clear;

    for k := 1 to 2500 do begin
      Items.Add('C:\cd\MP3 CD\MP3''s\Songs\## Artist - Dungeon Keeper 2 Theme.mp3');
      Items.Add('C:\cd\MP3 CD\MP3''s\Songs\## Artist - I am the God of Hell Fire.mp3');
      Items.Add('C:\cd\MP3 CD\MP3''s\Songs\## Artist - It''s a life.mp3');
      Items.Add('C:\cd\MP3 CD\MP3''s\Songs\## Artist - James Bond Theme.mp3');
    end;

    Caption := IntToStr(Items.Count);
  end;

  // Liste übergeben - soll das Einlesen vom Datenträger simulieren.
  // Hier werden der Pfad, Dateiname und Musiktitel getrennt.

  Liste.Clear;
  with ListBox1 do for k := 0 to Items.Count - 1 do begin
    m := Liste.Add(ExtractFileName(Items[k]));
    Liste.Objects[m] := TMp3List.Create;
    TMp3List(Liste.Objects[m]).Pfad := Items[k];
    TMp3List(Liste.Objects[m]).Kurzname :=
      AnsiUpperCase(ExtractFileName(ChangeFileExt(Items[k], '')));
  end;
  Beep;
end;

procedure TForm1.Button_SucheClick(Sender: TObject);
var
  Suche: String;
  k: Integer;
begin
  Suche := AnsiUpperCase('Theme');
  ListBox2.Clear;

  with Liste do for k := 0 to Count - 1 do begin
    if Pos(Suche, TMp3List(Liste.Objects[k]).Kurzname) > 0 then
      ListBox2.Items.Add(TMp3List(Liste.Objects[k]).Pfad);
  end;

  Beep;
end;

initialization
  Liste := TStringList.Create;

finalization
  Liste.Free;

end.


Alternativ hab ich auch im Pfad gesucht:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
procedure TForm1.Button_Suche_LangClick(Sender: TObject);
var
  Suche: String;
  k: Integer;
begin
  Suche := 'Theme';

  ListBox2.Clear;

  with Liste do for k := 0 to Count - 1 do begin
    if Pos(AnsiUpperCase(Suche), AnsiUpperCase(
      TMp3List(Liste.Objects[k]).Pfad)) > 0 then
        ListBox2.Items.Add(TMp3List(Liste.Objects[k]).Pfad);
  end;

  Beep;
end;


Viel länger hat es nicht gedauert.


matze - So 07.03.04 11:13

jo danke erstmal bis hierher. ich werde jatzt mal ein bisschen rumprobiern.