Hallo, hab mir Dein Programm angeschaut, es schaut schon recht gut aus.
Danke, dass du dir den Code angesehen hast und für dein Feedback.
Ich habe die Hashmap inzwischen noch etwas überarbeitet und unter anderem die Widestring-Map implementiert. Leider ist die ca. 4-5 mal so langsam wie die
Ansi-Variante
Ist es normal, dass Widestrings so viel langsamer sind? Wenn ich den Benchmark durch den SamplingProfiler laufen lasse, erzeugt ntdll.dll 57% der CPU-Last, was denke ich darauf zurückzuführen ist, dass WideStrings von Windows gemanaged werden. Die Exe selbst belegt nur ca 20%, wovon 50% die System.pas-Funktion mit WStrCmp und Co einnehmen.
Hat jemand eine Idee, wie man den Code vielleicht noch optimieren könnte?
Folgendes würde ich anders machen:
1. Die Suche nach Primzahlen ist beim verwendeten Algorithmus wirklich ganz überflüssig. Es sollte eine zum Wertebereich des Schlüssels teilerfremde Zahl sein. Im Fall des Stringkey ist der Wertebereich 2 hoch n, jede ungerade Zahl ist dazu teilerfremd. Im Fall eines Integerkeys hängt es vom Wertebereich des Integerkeys ab, der sollte besser kein Vielfaches der Feldgrösse sein - nicht umgekehrt. In fast allen Fällen in der Praxis wird das aber egal sein. Die hier eingesetzten Algorithmen gewinnen durch Primzahlen nichts.
Primzahlen benutze ich in meiner Komponente ja auch nicht, nur die von alzaimar macht das. Meine Hashmap verdoppelt immer ihre Größe ab einer gewissen Schwelle und nutzt diesen Code um den Hash zu verlürzen:
Delphi-Quellcode:
function THashMap.GetShrunkHash(AKey: Pointer): cardinal;
var
Tmp: Cardinal;
begin
Tmp := CalculateHash(AKey);
Result := (Tmp
xor (Tmp shr 8)
xor (Tmp shr 16)
xor (tmp shr 24))
and
FMask;
end;
2. Ein Rehash würde ich nicht davon abhängig machen, wie gefüllt die Tabelle schon ist, weil das ist eigentlich für die Performance ziemlich egal, sondern dann machen, wenn eine vorgegebene Anzahl von Kollisionen pro Hashentry überschritten wird: z.B: wenn bei irgend einem hashentry die angehängte Feldliste drei oder vier Elemente überschreitet.
Die Methode habe ich von alzaimars Hashmap übernommen. Prinzipiell würde ich die Größe auch von der Anzahl an Kollisionen abhängig machen, das Problem ist nur, diese zu ermitteln, da die Kollisionen über eine verkettete Liste gehandhabt werden. Man müsste dann bei jeder Änderung die Liste komplett durchlaufen, um zu prüfen, wie viele Einträge dort abgelegt sind.