Optimierung Code / Alternative zu Stringlist? (Delphi 5)

[frieder2008]

Zitat von Bernhard Geyer:

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 von ele:

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

[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).

[frieder2008]

Zitat von 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

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

[p80286]

Zitat von frieder2008:

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