StringList schnell nach mehreren Strings durchsuchen

[argonix]

Hallo!
Für das ASAI-Projekt ist es nötig, dass ich eine StringList sehr schnell nach vielen Stichworten durchsuchen kann. Ich würde das So machen:

Delphi-Quellcode:

function SeekStrings(List: TStringList;strs: TStringList): TStringList;
var i,j,k: integer;
tmp: TStringList;
begin
tmp:=TStringList.Create;
for i:=0 to strs.Count-1 do begin
k:=0;
for j:=0 to List.Count-1 do begin
if pos(strs[i],List[j])>0 then Inc(k);
end;
tmp.Add(IntToStr(k));
end;
Result:=tmp;
end;

Code nicht getestet!
List ist die zu durchsuchende StringList, strs enthält die Wörter nach denen gesucht wird und tmp am Ende die Anzahl an vorkommen dieser Wörter. Nun meine Frage: Kann man das irgendwie schneller lösen? In dieser Form würde die Funktion zu viel Zeit brauchen, vor allem bei vielen Wörtern.

P.S.: Ich hoffe, das ist das richtige Forum für diese Frage.

[xZise]

Was hälst du davon einzurücken?

Delphi-Quellcode:

function SeekStrings(List: TStringList;strs: TStringList): TStringList;
var
  i,j,k: integer;
  tmp: TStringList;
begin
  tmp:=TStringList.Create;
  for i:=0 to strs.Count-1 do begin
    k:=0;
    for j:=0 to List.Count-1 do begin
      if pos(strs[i],List[j])>0 then
        Inc(k);
    end;
    tmp.Add(IntToStr(k));
  end;
  Result:=tmp;
end;

Entferne mal die "IntToStr" Zeile Ich glaube dass die einzige Zeitbenötigende Zeile ^^

Ansonsten:
.IndexOf('String') durchsucht eine Liste nch den String (caseinsensetive).

[Klaus01]

Zitat von xZise:

.IndexOf('String') durchsucht eine Liste nch den String (caseinsensetive).

Laut der Hilfe ist es, wenn ich es richtig gelesen haben, caseSensitive und nur wenn ein Schalter auf
false gesetzt wird, ist es CaseInSensitive.

Zitat von DelphiHilfe:

Call IndexOf to obtain the position of the first occurrence of a string that matches S.
A string matches S if it is identical to S or, if CaseSensitive is False, if it differs only in case.

Grüße
Klaus

[jbg]

Zitat von Klaus01:

if CaseSensitive is False

Nur ist dieser "Schalter" per Vorgabe auf False eingestellt, der Abwärtskompatibilität zuliebe.

Im Quellcode von InnoSetup habe ich letzten einen gehashte StringListen-Implementierung gesehen. Da geht der Vergleich gleich viel schneller.

[peschai]

Hallo,

oder wie wärs hiermit? (extra für dich!)
Ansatz über Zeiger mit dem Nachteil daß eine große Liste extra Memory braucht, aber schnell sein dürfte ...

Delphi-Quellcode:

function SeekStrings(List: TStringList;strs: TStringList): TStringList;
var
  i,j,k,m: integer;
  s1:String;
  s2:String;
begin
  { Safety }
  Result := Nil;
  if not Assigned(List) or not Assigned(strs) then exit;
  i := 0;
  j := 0;
  k := 0;
  m := 0;
  s1 := '';
  s2 := '';

  { Action }
  s1 := List.Text+#0; //Liste ine eine Zeichenkette für ZeigerWandern umwandeln:
  { Nachteil platz, Vorteil Speed }

  m := Length(s1)-1; // Bytelänge dieses Textes ohne unseren #0 abschluss
  if (m>0) then // gibt's überhaupt was zu tun ?
    begin
      Result:=TStringList.Create; // Ergebnisliste vorbereiten
      for j:=0 to strs.Count-1 do // für alle zu suchende Wörter
        begin
          i := 1 ;
          k := 0;
          s2 := strs[j]+#0; // Suchwort für pChar Zeiger vorbereiten
          While (AnsiStrPos(@s1[i],@s2[1])<>NIL) do // s2 suchen ab position s1[i]
            begin
              inc(k); // fündig also Zähler erhöhen
              inc(i,Length(s2)-1); // Offset für nächste Suchposition
              if (i>m) then // security damit i keine exception lösen kann
                break;
            end;
          if (k>0)
            then Result.Add(s2+'='+IntToStr(k));
        end;
      { Falls nichts gefunden }
      if (Result.Count<1) then
        FreeAndNil(Result)
    end;
end;

[Horst_]

Hallo,

ist das wirklich soviel schneller? Die Listenelemente sind doch schon ein array mit Pointer. Ob der anfängliche Aufwand sich rechnet?

Delphi-Quellcode:

function SeekStrings(List: TStringList;strs: TStringList): TStringList; 
var 
  i,j,k: integer;
  TmpStr : String;
  tmp: TStringList; 
begin 
  tmp:=TStringList.Create; 
  for i:=0 to strs.Count-1 do begin 
    k:=0; 
    TmpStr := strs[i];
    for j:=0 to List.Count-1 do begin 
      if pos(TmpStr,List[j])>0 then 
        Inc(k); 
    end; 
    tmp.Add(IntToStr(k)); 
  end; 
  TmpStr := '';
  Result:=tmp; 
end;

Wie so oft hilft das FastCode Project
http://fastcode.sourceforge.net/ dort
http://fastcode.sourceforge.net/chal...ntent/Pos.html
Pos_JOH_IA32_6 ist über alle Plattformen das schnellste ~ 3 fach.

Und natürlich die längere Liste in der aüßeren schleife.

Gruß Horst

[shmia]

Zitat von peschai:

Delphi-Quellcode:

  s1 := List.Text+#0; //Liste ine eine Zeichenkette für ZeigerWandern umwandeln:
  { Nachteil platz, Vorteil Speed }

Das Anhängen von #0 kann man sich sparen, da grundsätzlich jeder AnsiString mit einem #0 endet.

Delphi-Quellcode:

   s2 := strs[j]+#0; // Suchwort für pChar Zeiger vorbereiten 
   While (AnsiStrPos(@s1[i],@s2[1])<>NIL) do // s2 suchen ab position s1[i]

So sieht's besser aus:

Delphi-Quellcode:

  s2 := strs[j]; // aktuelles Suchwort
  While (AnsiStrPos(@s1[i], PChar(s2))<>NIL) do // s2 suchen ab position s1[i]

Man könnte noch weiter optimieren, wenn man anstatt @s1[i] einen Zeigen vom Typ PChar verwendet.

[Horst_]

Hallo,

für eine Wörtersuche empfiehlt sich die Datenstruktur trie (Thesaurus, Wörterbücher nutzen dies)
http://www.student.uni-kl.de/~stried...00000000000000 und viele andere.
Dazu musst Du jedes Wort aus einem Satz untersuchen und kannst nicht mit pos arbeiten.
Eventuell funktioniert auch eine gute Hash-funktion.

Gruß Horst

[argonix]

Vielen Dank für die vielen Antworten! Ich probiere alle mal aus, mal sehen, welches Verfahren am schnellsten ist!

[Horst_]

Hallo,

Für wörtersuche gibt es von Hagen Reddmann schon was schnelles hier im Forum:
http://www.delphipraxis.net/internal...+dawg&start=15

Es sucht, ob ein Eintrag in 200000 worten vorkommt (das ist ja Dein Anliegen) und vieles mehr.
Aber Obacht, es ist shareware, also: Hagen fragen.

Gruß Horst
P.S.:
Er scheint von Delphi7 nicht begeistert