Hi,
ich habe mal eine Frage. Ich nutze gerne THashedStringList wenn ich viel vergleichen muss. Nun hatte ich eine liste mit ca. 2 Mio. Einträgen und eine liste mit ca. 500.000 Einträgen.
Die habe ich mit IndexOf verglichen. Unter Delphi Dauerte es ca. 5 Minuten. Dann habe ich das mal mit Freepascal übersetzt weil ich es auch für Unix brauche.
Es ist nichts geändert. Der Quellcode ist wirklich der gleiche. Aber unter FreePascal dauert das 1,5 Sekunden. Egal ob Windows oder Unix.

Mache ich bei Delphi etwas falsch? Ich mache nur ein Create. Muss man bei Delphi noch etwas andere setzen?

Was ist allerdings festgestellt habe, unter FreePascal kann man nicht mit mehreren Threads lesend auf THashedStringList zugreifen.

Oder ist das unter Delphi so langsam weil es Threadfest ist?

Vielen dank im Voraus

Ein IndexOf dauert 5 Minuten? (würde aber nicht erwarten, dass Delphi da wirklich sooooo schlecht wäre)


Tja, beide werden bestimmt eigene/unterschiedliche Implementationen verwenden, die auch unterschlich gut implementiert wurden-

Ist deine Liste sortiert?
Ich weiß jetzt nicht wie es bei der THashedStringList aussieht, aber TStrings/TStringList hat unterschlieliche Suchfunktionen für Sortiert oder nicht. (ich hoffe mal das hat die THashedStringList auch)


PS: per se ist da in Delphi garnichts threadsafe gebaut, aber beim Lesen (solange dabei intern kein Schreibzugriff passiert, wie z.B. bei einem TStream), ist paralleles Lesen möglich.

Nein, die liste ist nicht Sortiert. Also ein Unterschied von sagen wir mal 1-2 Minuten hätte ich noch verstanden. Aber soooo krass... Das hat mich wirklich erstaunt.

Die Freepascal Version hatte ich vergessen.
Free Pascal Compiler version 3.1.1 [2017/05/24] for x86_64

Und die Delphi-Version ist 2007?

Zitat von DelTurbo:

Mache ich bei Delphi etwas falsch?

Etwas Code wäre vielleicht hilfreich.

Zitat von DelTurbo:

Oder ist das unter Delphi so langsam weil es Threadfest ist?

Wo wird das denn behauptet?

Ja Delphi 2007.
Das mit dem Threadfest hatte ich mir einfach überlegt. Weil das auf den 1. Blick der einzige unterschied ist.

Und dann etwas Code. Ich habe eine Hauptschleife die sooft durchlaufen wie Daten da sind. Im moment ca. 500.000.

markieren

Delphi-Quellcode:

function IsInSubListID(list_id:String):Boolean; inline;
begin
    Result:=False;
    if ( GblListID.IndexOf(list_id)<>-1 ) then begin
      Result:=True;
    end;
end;

In der schleife wird dann hier nachgesehen ob die ID schon vorhanden ist. GblListID hat ca. 2,3Mio einträge.

Es liegt mir ferne Delphi "schlecht" zu machen. Mich hat das nur total gewundert das der gleiche Code plötzlich so schnell ist.

Vielleicht ist die Liste, bzw. sind zumindestens die Hashs in FP standardmäßig soritert und in Delphi eben nicht standardmäßig.

Als Erklärung, auf eine Datenbank bezogen:
TStringList.IndexOf ohne Sortierung ist ein FullTableScan
und mit Sortierung ist es ein IndexScan.

[add]
In Delphi XE ist es immer ein "teilweiser" FullScan.
Und in Delphi2007 wird das nicht anders gewesen sein.

zusammenfalten · markieren

Delphi-Quellcode:

unit IniFiles;

//THashedStringList = class(TStringList)

function TStringHash.Find(const Key: string): PPHashItem;
var
  Hash: Integer;
begin
  Hash := HashOf(Key) mod Cardinal(Length(Buckets));
  Result := @Buckets[Hash];
  while Result^ <> nil do
  begin
    if Result^.Key = Key then
      Exit
    else
      Result := @Result^.Next;
  end;
end;

Für Delphi würde ich dann eher ein TDictionary<T> empfehlen.

Ich würde das vielleicht nochmal mit einer aktuellen Delphi-Version probieren. In D2007 wird eine verkettete Liste für die Hash-Buckets verwendet. Neuere Versionen nehmen da ein Array.

Es ist aber vermutlich eher so, daß FP einen anderen Hash-Algorithmus verwendet, der für die aktuell verwendeten Strings weniger Kollisionen verursacht.

Zitat von Uwe Raabe:

Es ist aber vermutlich eher so, daß FP einen anderen Hash-Algorithmus verwendet, der für die aktuell verwendeten Strings weniger Kollisionen verursacht.

Danke für die Antwort. Das kann natürlich sein. Obwohl FP Quelloffen ist, habe ich da nicht reingeschaut. Ich wollte den einfachen gehen und einfach mal fragen.

Und das ich mit einer 14 Jahre alten Delphi Version arbeite macht es nicht besser, das kann ich mir auch denken. Ich wollte auch nicht das dieser Thread "lang" wird.

Nochmal vielen dank an alle.....

Richtig stellung:
Ich hatte mit mit den Zeiten vertan. Hier nun einmal die richtigen Daten.

Einträge in der THashedStringList: 2,313,748
Einträge die gegen getestet werden: 685,158

Zeiten:
Delphi 2007: 16:37 Minuten
FreePascal: 2:23 Minuten

So, das war es aber nun. Was ich im Kopf hatte als ich oben die Zeiten geschrieben weiß ich nicht mehr.

THashedStringList steht nicht umsonst in der Unit IniFiles. Die ist nicht dafür ausgelegt mit vielen Einträgen performant zu funktionieren sondern nur im Kontext der TMemIniFile (die das inzwischen auch nicht mehr benutzt, sondern ein TDictionary aus System.Generics.Collections).

Die zugrundeliegende Hashtable wird mit einer festen Anzahl von 256 Buckets erstellt - d.h. bei 2mio Elementen wird aus einem theoretischen O(1) ein O(n).

Vergiss einfach, dass du jemals von THashedStringList gehört hast und benutz ein TDictionary aus System.Generics.Collections.

P.S. Ähh, Delphi 2007 - musst du dir was eigenes bauen, oder du modifizierst THashedStringList, dass sie mehr Buckets baut. Allerdings wirst du da auch nicht wirklich auf einen grünen Zweig kommen, da das intern ein bisschen verwurschtelt ist (hab hier grad nur XE als ältesten Sourcestand).