IndexOf case sensitive / Performance verbessern

[frieder2008]

Hallo Leute,

folgende zwei 'Probleme' habe ich, wo ich gerade hänge bzw. wo mein Delphi am Ende ist:

1) Ich vergleiche zwei Stringlisten (mit Tokens) miteinander und zähle die verschiedenen Tokens darin. Das mache ich bisher so (und klappt wunderbar):

Delphi-Quellcode:

      for iii:=0 to tokenlist.Count -1 do
        begin
          occurindex:= tokenlistges.indexof(tokenlist[iii]);
          if occurindex >=0 then
            tokenlistges.Objects[occurindex]:= TObject(Succ(Integer(tokenlistges.Objects[OccurIndex])))
            else tokenlistges.AddObject(tokenlist[iii],TObject(1));
        end;

Aber: Leider zählt mein Code so case insensitive, sprich "Das" und "das" werden zusammengenommen. Gibt es eine Möglichkeit, IndexOf case sensitive zu stellen (D5!)? - Oder hat jemand eine Idee, wie ich das alternativ umsetzen könnte? (Ich habe es mit einer verschachtelten Routine und CompareAnsiStr probiert, aber dann zählt er "Das" korrekt und "das" wird für jeden Fund in die Liste (tokenlistges) eingetragen, anstatt einen entsprechenden Eintrag zu hochzuzählen..)

2) Zweite Sache: Ich bastle gerade an einem Textanalyseprogramm mit verschiedenen Routinen. Funktionieren tut alles soweit, aber die Performance lässt vor allem bei großen Textmengen (>1 Mio Wortformen/Tokens) sehr zu wünschen übrig. Gibt es eine Möglichkeit, mit der ich die Performance verbessern kann, an einer der folgenden Stellen:

- Textfiles laden
- jedes Textfile für sich in eine Token-String-List konvertieren (Extractstrings..)
- Tokens des Textfile mit den Tokens weiterer Textfiles in einer Liste zählen
- Frequenzliste in Listview ausgeben

* Ich arbeite derzeit v.a. mit Stringslists; gibts da evtl. eine schnellere Lösung o.ä.?
* Oder ließen sich die Textfiles irgendwie vorverarbeiten/vorspeichern, so dass sie schneller gelesen werden können?
* Ein anderes Programm, das das schon kann, was ich gerade baue, arbeitet anscheinend viel mehr mit der Festplatte (zumindest zeigt das die Leuchte); bei mir tut sich im Vergleich dazu gar nix, aber es dauer gerade bei großen Textmengen ewig.. Ist es etwa schneller, mit der Platte anstatt mit dem Arbeitsspeicher zu schaffen?!? - Wenn ja, wie?

Danke für Eure Mühe und viele Grüße zum WE,
frieder

[Luckie]

Wie wäre es damit:

Delphi-Quellcode:

UpperCase(occurindex) := tokenlistges.indexof(UpperCase(tokenlist[iii]));

[Bernhard Geyer]

zu: Schon probiert mit einer Sortierten Liste zu arbeiten (.Sorted := True). Ansonsten solltest du dich mal mit B-Trees auseinandersetzen.

[frieder2008]

danke; aber Luckies Vorschlag kapier' ich nicht: Uppercase konvertiert mir doch beides in Großbuchstaben, sprich, es ist dann erst recht case insensitive, oder?

[himitsu]

IndexOf verwentet intern CompareStrings und diese Funktion nutzt AnsiCompareText ... also CaseInsensitive.

Leite die Klasse (TStringList?) ab und überschreib CompareStrings (dieses ist virtual) mit einer eigenen Funktion.

Delphi-Quellcode:

function {TStrings}.CompareStrings(const S1, S2: string): Integer;
begin
  Result := AnsiCompareStr(S1, S2);
end;

[frieder2008]

Uff, sorry, da komme ich als relativer Anfänger nicht mit, weil noch nie Klassen abgeleitet, geschweige denn Methoden überschrieben. Ich habe versucht, mich dazu ein bisschen einzulesen, aber ich verstehe nicht, wie ich die Funktion (in dem Fall comparetext) überschreiben soll.

Delphi-Quellcode:

type
  TFstringlist = class(Tstringlist);
  private
  function CompareStrings(const S1, S2: string): Integer; override;
  end;

So krieg ich eine Fehlermeldung, weil Comparestrings der Basisklasse nicht bekannt sei..

[himitsu]

also bei mir geht das (selbst mit der "falschen" Sichbarkeit > Private) :gruebel:

Delphi-Quellcode:

Uses Classes;

Type
  TMyStringsList = Class(TStringList)
  Protected
    Function CompareStrings(Const S1, S2: String): Integer; Override;
  End;

Function TMyStringsList.CompareStrings(Const S1, S2: String): Integer;
  Begin
    Result := AnsiCompareStr(S1, S2);
  End;

ach ja, falls es wen interessiert, es wurde natürlich in der Basisklasse deklariert:
(ist also bei allen Nachkommen von TStrings so änderbar)

Delphi-Quellcode:

TStrings = Class(TPersistent)
Protected
  Function CompareStrings(Const S1, S2: String): Integer; Virtual;

[frieder2008]

Sorry, ich kriegs einfach nicht hin: Die Fehlermeldung bleibt "Comparestrings" sei nicht in der Basisklasse.

Delphi-Quellcode:

unit frisstrings;

interface

uses classes;

Type
  TMyStringsList = Class(TStringList)
  Protected
    Function CompareStrings(Const S1, S2: String): Integer; Override;
  End;

implementation

Function TMyStringsList.CompareStrings(Const S1, S2: String): Integer;
  Begin
    Result := AnsiCompareStr(S1, S2);
  End;

end.

[himitsu]

Welche Delphi-Version nutzt du denn?

[Hawkeye219]

Hallo,

Zitat:

Zitat von himitsu

Welche Delphi-Version nutzt du denn?

D5 laut seinem Eröffnungsbeitrag - CompareStrings wurde mit Delphi 6 eingeführt.

Gruß Hawkeye

[frieder2008]

Hm, aber in D5 sind die Funktionen so organisiert: Stringlist -> indexof -> Find -> AnsiCompareText -> und dort (Sysutils):

Delphi-Quellcode:

function AnsiSameStr(const S1, S2: string): Boolean;
begin
  Result := CompareString(LOCALE_USER_DEFAULT, 0, PChar(S1), Length(S1),
    PChar(S2), Length(S2)) = 2;
end;

Wo könnte ich denn da via Überschreiben eingreifen?

[himitsu]

in D7 sind Find und IndexOf auch als Virtual ... falls es das bei dir ebenfalls ist, dann am Besten wohl Finde überschreiben

Delphi-Quellcode:

public
  function Find(const S: string; var Index: Integer): Boolean; override;

[Luckie]

Zitat:

Zitat von frieder2008

es ist dann erst recht case insensitive, oder?

Ich dachte das wolltest du?

[himitsu]

nee, es ist per Standard so, aber er will es nicht so :angel:

[Satty67]

Ist eine Funktion dafür zu langsam?

Delphi-Quellcode:

  function IndexOf_CS(aStrings: TStrings; aToken : String):Integer;
  var
    i : Integer;
  begin
    Result := -1;
    for i := 0 to aStrings.Count do
      if aStrings[i]=aToken then begin
        Result := i;
        Break;
      end;
  end;

  // dann
  // occurindex:= tokenlistges.indexof(tokenlist[iii]);
  occurindex := IndexOf_CS(tokenlistges, tokenlist[iii]);

PS: "Str1 = Str2" hab' ich auch schon mit CompareStr() verglichen. Im CPU-Fenster sieht man auch, das unterschiedlicher Code generiert wird, aber bei 170.000 vergleichen war (zumindest mit meiner Messmethode) kein signifikanter Unterschied feststellbar. Zumindest bei D5, kann später optimierter sein.

War wohl Jmp/Test vs. LongJmp falls ich mich recht erinnere.

[frieder2008]

Hi Satty67,

danke für die Funktion, hast nur den Count überstrapaziert (..-1),

Delphi-Quellcode:

function IndexOf_CS(aStrings: TStrings; aToken : String):Integer;
  var
    i : Integer;
  begin
    Result := -1;
    for i := 0 to aStrings.Count -1 do
      if aStrings[i]=aToken then begin
        Result := i;
        Break;
      end;
  end;

aber sonst läuft das sogar schneller! als das Stringlist.IndexOf

- Und genau dazu hätte ich auch nochmal eine grundlegende Frage: Das hier ist jetzt nicht das erste mal, dass ich eine selbstgebastelte Funktion habe, die schneller läuft wie eine von der VCL bereitgestellte Routine. Anders gesagt: Dann lohnt es sich offenbar, im Zweifelsfall sich die VCL-Routine zu nehmen und abzuspecken; spricht da was aus Profi-Sicht dagegen?

- Grundlegend ist die Frage deshalb für mich, weil ich nicht 170.000, sondern ~ 2.000.000 Vergleiche durchführen (bzw. Wörter in Texten analysieren) muss. Und da wirds bei entsprechender Größe (>1 Mio) derzeit noch viel zu langsam. Könnte mal unten jemand durchgucken, wo man evtl. durch Tricks oder alternative Routinen Zeit sparen könnte? DANKE!

- Schließlich: Hilft es, anstatt mit StringLists mit anderen Objekten zu arbeiten? Oder Prozess-Priorität für Prog erhöhen (Nachteile?)?

1) Jede Datei in Stringlist laden:

Delphi-Quellcode:

textinhalt.LoadFromFile(path + filelist.Items.Strings[i])

2) Bestimmte Zeichen rauslöschen: " und ' wie hier:

Delphi-Quellcode:

  repeat
    i:= ansicharpos('"', s);
    if i<>0 then s[i]:= ' ';
  until i=0;

3) Geladenes File bzw. Stringlist.text in Tokens auflösen:

Delphi-Quellcode:

      Extractstrings([' ', '.', ',', ';', '?', ':', '-', '(', ')', '[', ']', '<', '>', '/', '\', '_', '*', '+', '=', '^', CHR(096),
       CHR(039), CHR(127), CHR(126), CHR(124), CHR(130), CHR(132), CHR(133), CHR(139), CHR(145)], ['.', ',', ';', '?', ':', '-',
       '(', ')', '[', ']', '<', '>', '/', '\', '_', '*', '+', '=', '^', CHR(096), CHR(039), CHR(127), CHR(126), CHR(124), CHR(130), CHR(132), CHR(133), CHR(139), CHR(145), CHR(146), CHR(147), CHR(148), CHR(151), CHR(155), CHR(171), CHR(180), CHR(187),
       CHR(146), CHR(147), CHR(148), CHR(151), CHR(155), CHR(171), CHR(180), CHR(187)], pchar(textinhalt.text), tokenlist);

EDIT: => Ich habe so im Gefühl, dass man hier noch was machen könnte, nur wie.. Mein Grundansatz wäre einfach, die Zeichen jeder Datei durch zu gehen und bei Leerzeichen eben zu einem Wort zusammenfügen und in die Liste ablegen. Aber das wird am Ende doch schlechter laufen als ExtractString, oder?

Eine Möglichkeit wäre auch - das würde viel Zeit sparen! -, wenn ich ExtractStrings dazu bekäme, " und ' (einfaches und doppelte Anführungszeichen) nicht mehr als besondere Separatoren zu interpretieren; dann müsste ich die vorherh nicht mehr rausfischen..

4) Tokens zählen

Delphi-Quellcode:

      for iii:=0 to tokenlist.Count -1 do
        begin
        if Form1.checkbox2.checked then occurindex := IndexOf_CS(tokenlistges, tokenlist[iii])
          else occurindex:= tokenlistges.indexof(tokenlist[iii]);
        if occurindex >=0 then tokenlistges.Objects[occurindex]:= TObject(Succ(Integer(tokenlistges.Objects[OccurIndex])))
          else tokenlistges.AddObject(tokenlist[iii],TObject(1));
        end;
      end;

5) Gesamtergebnisse in Listview ausgeben

Delphi-Quellcode:

 for ii := 0 to Tokenlistges.Count - 1 do
          with listenview do begin
            listitem := items.Add;
            listitem.Caption := Tokenlistges[ii];
            listitem.SubItems.Add(inttostr(integer(Tokenlistges.objects[ii])));
            end;

6) Aufräumen..

Gruß, frieder

[Satty67]

Zitat:

Zitat von frieder2008

danke für die Funktion, hast nur den Count überstrapaziert (..-1)

Ja, mein Dauerfehler, seit ich meine Arbeit mit Listen umgestellt hab'

Früher immer for i := 1 to Count do (und im Quelltext [i-1]). Das war natürlich Mist, aber jetzt vergesse ich das -1 in der Schleifendeklaration ständig ;)

***

Mal ein paar laienhafte Gedanken dazu:

Wenn Du sowieso primär Zeichenweise arbeitest, dann ist vielleicht TFileStream die bessere Variante. Stringlist bereitet die Daten ja noch für zeilenweisen Zugriff vor. Zeichen ausschneiden passiert dann beim Einlesen in dem Puffer (fallen quasi gleich durchs Netz)

Prozess-Priorität für Prog erhöhen (Nachteile?)? Bringt meiner Meinung nach Garnichts. Deine Anwendung bekommt doch sowieso 99,5% Priorität, wenn sonst nichts läuft. Wenn später jemand etwas nebenher startet, will er da ja gewollt auch etwas Prozessorleistung haben.