Optimierung Code / Alternative zu Stringlist? (Delphi 5)

[frieder2008]

Liebe Leute,

ich habe eine Liste mit mehr als 7 Mio Einträgen (Strings/einzelne Wörter), die ich gerne gruppieren und zählen würde.

Derzeit habe ich das mit einer Stringlist realisiert:

Delphi-Quellcode:

Procedure GruppiereZaehleListe(Quellliste, Ziellist: tstringlist);
var
  i: integer;
  CurIndex: integer;
begin

  for i:= 0 to Quellliste.count-1 do
    begin
      CurIndex := Ziellist.IndexOf(Quellliste[i]);
      if CurIndex >= 0 then
        Ziellist.Objects[CurIndex] := TObject(Succ(Integer(Ziellist.Objects[CurIndex])))
      else
        Ziellist.AddObject(Quellliste[i], TObject(1));
    end;
end;

Mein Problem: Das ist VIEL zu langsam. Gibt es irgendeine Möglichkeit, den Code zu optimieren oder eine Alternative zu TStringlist, die einfach schneller arbeitet?

- Habe nur D5 zur Verfügung (ich weiß, alt).

Danke und beste Grüße,
frieder

[Bernhard Geyer]

BTree oder HashMap dürften viel schneller sein.

TStringList wird auch schneller wenn sie sortiert ist.

[Luckie]

Eventuell sollte man sich auch über die 7 Mio Einträge Gedanken machen.

[frieder2008]

Zitat:

Zitat von Bernhard Geyer (Beitrag 1088698)

BTree oder HashMap dürften viel schneller sein.

TStringList wird auch schneller wenn sie sortiert ist.

Danke für das Feedback. Sortierung hat in der Tat schon mal was gebracht, aber immer noch zu langsam. Die Sache mit den Hash-Maps verstehe ich nicht ganz. Wie funktioniert das Prinzip bzw. wie kann ich das auf mein Problem übertragen?

- Die 7 Mio Einträge resultieren aus einem großen Textkorpus mit ~11000 Texten, tokenisiert. Da kann ich schlecht einen Teil 'auslagern' ;)

Danke und Gruß,
frieder

[mkinzler]

Ein HashMap ist ein Art Index der auf HashWerten der Daten basiert

[p80286]

zum einen würde ich Dir für das Suchen die Binäre Suche empfehlen, zum anderen, wenn ich das richtig gesehen habe, dann fügst Du nicht vorhandene Datensätze ein, wie wäre es dann mit:

Delphi-Quellcode:

zielliste.Sorted:=true;
zielliste.Duplicates:=Dupignore;
{not found}
zielliste.add(quellliste[i]);

Gruß
K-H

[ele]

Es gibt da auch noch die THashedStringList, aber ich weiss nicht ab welcher Delphi-Version.

[frieder2008]

Zitat:

Zitat von p80286 (Beitrag 1088715)

zum einen würde ich Dir für das Suchen die Binäre Suche empfehlen, zum anderen, wenn ich das richtig gesehen habe, dann fügst Du nicht vorhandene Datensätze ein, wie wäre es dann mit:

Delphi-Quellcode:

zielliste.Sorted:=true;
zielliste.Duplicates:=Dupignore;
{not found}
zielliste.add(quellliste[i]);

Gruß
K-H

Wenn ich richtig verstehe, fallen die Duplikate für die Zählung dann aber raus. - Das wäre kontraproduktiv.. Oder hab ich was falsch verstanden?

Gruß, frieder

[frieder2008]

Zitat:

Zitat von ele (Beitrag 1088720)

Es gibt da auch noch die THashedStringList, aber ich weiss nicht ab welcher Delphi-Version.

Das wäre es wohl! In D5 gibts das leider nicht. Hat jemand das dazugehörige Script (im Netz find ich jetzt spontan nichts, nur Hinweise, dass es das geben soll)?

Danke und Gruß,
frieder

[p80286]

Zitat:

Zitat von frieder2008 (Beitrag 1088724)

Wenn ich richtig verstehe, fallen die Duplikate für die Zählung dann aber raus. - Das wäre kontraproduktiv.. Oder hab ich was falsch verstanden?

Nicht Du, ich
(man könnte vllt. dupError nutzen und dann in der Exceptionbehandlung zählen..??)
[bitte nicht schlagen!]
Gruß
K-H

[RaSoWa1]

Bei langen Stringlisten verwende ich zum Suchen nicht "IndexOf".
Folgender Code ist bei mir viel schneller (warum auch immer?):

Delphi-Quellcode:

function InLst(lst: TStrings; s: String): Integer;
var   i : Integer;
begin
  result := -1;
  for i := 0 to lst.Count - 1 do
    if lst[i] = s then
    begin
      result := i;
      Break;
    end
end;

Gruß
Klaus

[ele]

Das liegt vermutlich daran, dass bei Nachfahren von TStrings die virtuelle Methode CompareStrings aufgerufen wird, das ist etwas langsamer als ein direkter Stringvergleich...

Delphi-Quellcode:

function TStrings.IndexOf(const S: string): Integer;
begin
  for Result := 0 to GetCount - 1 do
    if CompareStrings(Get(Result), S) = 0 then Exit;
  Result := -1;
end;

[BUG]

Nur so ne Überlegung...

Gibt es eine Chance alle verschieden Tokens einfach durchgehend zu nummerieren?

Zumindest die Vergleiche könnten schneller werden, wenn man nur noch die Indices vergleicht und vielleicht wird nebenbei auch der Speicherverbrauch kleiner (je nachdem wie viele Strings doppelt vorkommen).

[jobo]

Willst Du die Stringlist nur als Vehikel für deine Operationen oder soll die im Rahmen einer Anwendung irgendwelche GUI Elemente füttern?
Im ersten Fall wär doch vielleicht eine einfache DB angesagt oder?

[frieder2008]

Zitat:

Zitat von jobo (Beitrag 1088775)

Willst Du die Stringlist nur als Vehikel für deine Operationen oder soll die im Rahmen einer Anwendung irgendwelche GUI Elemente füttern?
Im ersten Fall wär doch vielleicht eine einfache DB angesagt oder?

Also ich habe zuerst sehr lange Wortlisten, die ich dann zusammenfassen möchte (Wort1=3, Wort2=1200,...). KA, ob da eine DB für ausreichen würde..hm.

Zitat:

Zitat von BUG (Beitrag 1088772)

Gibt es eine Chance alle verschieden Tokens einfach durchgehend zu nummerieren?

Das ginge im Prinzip schon, aber macht eig keinen Sinn. Denn ich müsste ja gleichen Tokens gleiche Nummern/Indizes vergeben, wofür ich jeweils doch wieder danach suchen muss, oder?

Du meinst doch:

1 das
2 ist
3 ein
4 Wort
1 das
3 ein
4 Wort
5 ist
6 .

-> 1=2, 2=2, 3=2 usw.
-> das=2, ist=2 usw.

Ich könnte mir nur vorstellen, dass das schneller ginge, wenn ich die Zahlenreihen eben NICHT als Stringlist speichert. Wäre das dann ein Array of integer? (habe bisher nie mit Arrays gearbeitet)

=> Wäre das auch das Prinzip von "HashMaps"?

Danke und Gruß,
frieder

[BUG]

Zitat:

Zitat von frieder2008 (Beitrag 1088808)

=> Wäre das auch das Prinzip von "HashMaps"?

Nicht ganz, aber stimmt, es geht in die Richtung :gruebel:

Vermutlich ist eine gute fertige Lösung (à la Hashmap oder DB) besser als wenn man sich selbst irgendwas zusammenbastelt.

[frieder2008]

Zitat:

Zitat von BUG (Beitrag 1088817)

Zitat:

Zitat von frieder2008 (Beitrag 1088808)

=> Wäre das auch das Prinzip von "HashMaps"?

Nicht ganz, aber stimmt, es geht in die Richtung :gruebel:

Vermutlich ist eine gute fertige Lösung (à la Hashmap oder DB) besser als wenn man sich selbst irgendwas zusammenbastelt.

Moin zusammen,

ja, das denke ich auch. Mein Problem ist, dass ich nirgends Infos zu einer 'fertigen' Hashmap finde! Hat niemand einen Tipp oder kann mir ein Codebsp schicken?

Wenn ich das Konzept von Hashmaps richtig verstehe, dann müsste es doch so gehen:

- 'Übersetzen' der Strings in Zahlen: z.B. einzelne Buchstaben in Zahlen: "aha" => 181 o.ä.; gibt es da zufällig schon einen guten Algor., der das schnell macht?

Und nochmal eine Nachfrage zu den Arrays of Integer: ich verstehe nicht ganz, wie ich die bei Laufzeit entsprechend nutzen kann. Denn ich müsste - damit es schnell läuft - als Index des Arrays den 'Stringcode' (z.B. 181) dann setzen können, wenn es eben zum ersten mal auftaucht - und nicht 'in Reihe' (12345..). Das ginge doch nur, wenn ich das Array dann vorsorglich auf x Mio dimensionieren würde, oder? Da würde dann aber wohl übel viel Speicher belegt..

Delphi-Quellcode:

var
  myarray: array of integer;
  i: integer;
  Wortliste: tstringlist;
  wortcode: integer;
begin
  {Wortliste laden}

  setlength(myarray, 100000000000);
  for i:= 0 to Wortliste.count-1 do
    begin
      Wortcode:= {Wort aus Wortliste[i] in Wortcode übersetzen}
      myarray[Wortcode]:= succ(myarray[Wortcode]);
    end;
  
  {Rückübersetzen der Wortcodes in Wörter und Ausgabe}
  setlength(myarray, 0);

- Aua, fällt mir gerade auf, dass ich anschließend ja im Grunde das komplette Array durchlaufen müsste, um diejenigen Wörter wieder zu holen, die es dann auch 'tatsächlich' gibt.. hm.. Besser wäre dann wohl eine Lösung a la Wortcode=f in einer Stringlist, oder?

Sorry, wenn ich soviel nachfrage, aber das Problem beschäftigt mich schon seit langem und ich muss es endlich mal ein für alle mal lösen! Mit Eurer Hilfe :oops: :thumb:

Danke und viele Grüße,
frieder

[jobo]

Ich denke, das ist keine Frage, ob eine DB reicht. Sie kann potentiell das, was Du brauchst.
Du "kippst" alle Daten rein und kannst anschließend nach Lust und Laune sortieren, gruppieren, zählen.
Das kannst Du auch gleich mit dem Vorschlag von Bug kombinieren, die Wörter zu nummerieren.

[jobo]

Je nach Verwendung brauchst Du ein oder 2 Tabellen (Mir ist nicht genau klar, was Du brauchst)
Denkbar wäre, auch noch die Textherkunft des Wortes zu verwalten.

Code:

create table NurDieWorte (
NDW_ID number(9) [AutoSequence],      -- Primärschlüssel
NDW_Wort varchar(50)                  -- unique constraint
)

create table WortVorkommen(
WVk_Id number(9) [AutoSequence],      -- Order of Appearance, falls nötig
NDW_ID number(9)                      -- Verweis auf Wort
)
-- oder statt der beiden Tabellen oben nur diese
create table WorteUndAnzahl (
NDW_ID number(9) [AutoSequence],      -- Primärschlüssel
NDW_Wort varchar(50),                 -- unique
NDW_WortAnzahl number(9)              -- Direkte Häufigkeit, wenn Reihenfolge unwichtig 
)

Die Tabellen kannst Du dann entsprechend auswerten.

[frieder2008]

Hm, ich habe eben folgendes gefunden:

http://www.delphipraxis.net/45571-hash-tabellen.html

Das wäre wohl genau das, was ihr mit Hashmaps meintet (nehme ich an). Jetzt habe ich nur noch Probleme mit der Anwendung von Pointern..

Delphi-Quellcode:

var
  x: TStringDictionary;
  meinpointer: ^Integer;
begin
  x:= TStringDictionary.create;
  new(meinpointer);
  meinpointer^:= 3;

  x.Add('Wort1', meinpointer);

  meinpointer^:= 5;

  x.Add('Wort2', meinpointer);

  x.Find ('Wort1', meinpointer); --- FEHLER!
  showmessage(meinpointer);  --- potFEHLER

  x.Clear;
  x.Free;
  dispose(meinpointer);
end;

Bei FEHLER kommt die Meldung, dass die "Typen der tatsächlichen und formalen Var-Parameter" nicht übereinstimmten. Was mache ich falsch?

Und bei potFEHLER weiß ich, dass ich keinen pointer direkt als String ausgeben kann; reicht da ein inttostr(meinpointer) oder wie bekomme ich das zurück?

danke und gruß,
frieder

PS: Ist eine neue Frage, kann daher auch einen neuen Thread aufmachen.. - Danke jedenfalls schon mal für Eure Infos!!

[frieder2008]

Liebe Leute,

ich habe es jetzt mit der TStringDictionary von alzaimar hinbekommen: der absolute Hammer, das Teil! :thumb: Geht ab, wie die Kanone! Hat sich doch wieder gelohnt, sich mit neuem zu beschäftigen :)

Danke Euch allen und beste Grüße,
frieder

[mjustin]

Tja, leider zu spät - mein Vorschlag wäre gewesen, die TStringlist mit der richtigen Größe zu erstellen, damit das Anlegen neuer Einträge nicht zu viele Speicherallokationen benötigt - also mit Capacity := <gigantische Zahl>

http://docwiki.embarcadero.com/VCL/d...rings.Capacity

http://www.festra.com/wwwboard/messages/13039.html

Zitat:

the trick is in setting the stringlist capacity large enough, so that the program doesn't have to re-adjust the capacity many thousands of times when many items are added