AW: Dictionary statt binärer Suche?
Zitat:
|
AW: Dictionary statt binärer Suche?
Zitat:
|
AW: Dictionary statt binärer Suche?
Der Sir wollte nur zeigen, dass die Anzahl der Einträge letztlich kein Problem darstellt, was ich nun auch einsehe.
Offenbar muss man aber für die Berechnung des Hashwertes eine optimale Lösung finden, was mir vorliegend nicht gelungen ist. Deshalb hat sich mein Dic nicht performant genug verhalten. Aber ich habe mit der einfachen sortierten Liste eine für mich sehr gut passende Alternative, mit der ich sehr gut zurecht komme. |
AW: Dictionary statt binärer Suche?
@stahli :thumb:
|
AW: Dictionary statt binärer Suche?
Hallo,
es lässt mir keine Ruhe, ich muss auch mal was dazu sagen. Erstmal die Frage ob sich jemand die Implementierung von TDictionary<TKey,TValue> angeschaut hat? Denn ich glaube die Implementierung ist das Problem. Zitat:
Delphi-Quellcode:
oder
// Hash-Wert ist der 1.Index im zweidimensionalen Array
THashTable= array of array of record Key: TKey; Value: TValue; end;
Delphi-Quellcode:
Folgende Aussagen meinerseits beziehen sich auf die Implementierung vom TDictionary<TKey,TValue> im Delphi-XE8.
THashTable= array of record
Hash: THash; // Array ist nach Hash sortiert, Zugriff mittels binärer Suche nach dem Hash Values: array of record Key: TKey; Value: TValue; end; end; Leider wird keine der Varianten benutzt. Die Implementierung ist sicherlich Creative. Ob sie auch Klever ist, wage ich zu bezweifeln. Zitat:
Zitat:
Delphi-Quellcode:
Für mich ist bei diesem Algorithmus der ermittelte Startindex der eigentliche Hash, denn wenn an der Stelle das Gesuchte nicht liegt, wird anschließend eine sequenzielle Suche durchgeführt, was man wegen teuer ja nicht will. Und bei meinen Versuchen mit TObjectDictionary<TObject,Integer> bekommen sehr viele Objekte den gleichen Startindex.
function TDictionary<TKey,TValue>.GetBucketIndex(const Key: TKey; HashCode: Integer): Integer;
var start, hc: Integer; begin if Length(FItems) = 0 then Exit(not High(Integer)); start := HashCode and (Length(FItems) - 1); Result := start; while True do begin hc := FItems[Result].HashCode; // Not found: return complement of insertion point. if hc = EMPTY_HASH then Exit(not Result); // Found: return location. if (hc = HashCode) and FComparer.Equals(FItems[Result].Key, Key) then Exit(Result); Inc(Result); if Result >= Length(FItems) then Result := 0; end; end; Und wenn man sich dann noch
Delphi-Quellcode:
und vor allem
Grow
Delphi-Quellcode:
anschaut sieht man auch wieso Stahli das misst was er misst.
Rehash
Also immer schön überprüfen ob die eingesetzten Klassen auch das leisten, weswegen man sie einsetzt. einbeliebigername. |
AW: Dictionary statt binärer Suche?
Bei Video2Brain ist ein interessantes Tutorial zu Datenstrukturen und darin auch zu Hash-basierten Strukturen.
https://www.video2brain.com/de/video...atenstrukturen Ist halt leider kostenpflichtig. Das ist recht einfach gehalten und daher gut verständlich. Was Emba im Detail umgesetzt hat kann ich nicht wirklich nachvollziehen. Insbesondere erschließt sich mir nicht, was ich beachten müsste, um effektive Hashwerte zu erhalten. Aber wie gesagt. Ich komme derzeit auch sehr gut ohne aus. PS: Ich meine mich zu erinnern, dass AQTime genau auch Grow und Rehash als Bremse ausgemacht hatte. Und ich hatte daraus dann interpretiert, dass ich das dann nicht ändern kann, weil das ja ein Verhalten der Komponente ist. |
AW: Dictionary statt binärer Suche?
Wenn man etwas nicht nicht weiß, dann kann man die gute Tante fragen HashSet.
Und ein HashSet ist eine Menge von eindeutigen Werten. Wenn die Implementierung so schlecht ist, was habe ich denn dann falsch gemacht wenn bei mir 1.000.000 Instanzen da in 179ms reinflutschen? :gruebel: |
AW: Dictionary statt binärer Suche?
Diese Implementierung ist allerdings ziemlich miserabel.
Für eine brauchbare Hashtabelle braucht man entweder ein zweidimensionales Feld, oder eine Familie von Hashfunktionen, durch die man sicherstellt, dass keine "Ballungen" von Kollisionen auftreten. Wenn ein eindimensionales Hashfeld verwendet und bei einer Kollision einfach immer der nächsthöhere Index genommen wird, entstehen immer grössere Blöcke von bereits besetzten Indizes, und wenn ein neuer Hashwert irgendwo in so einen Block hineinfällt, vergrössert sich der besetzte Block weiter und damit 1. die Wahrscheinlichkeit, dass irgend ein Hashwert wieder in diesen Block fällt und ihn weiter verlängert, und 2. natürlich die durchschnittliche Suchzeit nach jedem Schlüssel, dessen Hashberechnung irgendwo in diesem besetzten Block aufschlägt. @ Sir Rufo Die Verwendung von der Reihe nach angelegten Speicheradressen als Index ist eine absolut atypische Anwendung. Nachdem ein TObject eine Anzahl n Bytes braucht und das nächste TObject typischerweise die Adresse des vorigen TObject + n erhält, wird hier die Problematik der Kollisionsballungen automatisch entschärft. Bei zufälligen Werten für den Index hast du in aller Regel keine so optimal-gleichmässige Verteilung der Schlüsselwerte (die durch das "and" bei der Erzeugung des Hashindex eine optimal-gleichmässige Verteilung der Hashwerte über die ganze Breite der Hashtabelle ergibt). |
AW: Dictionary statt binärer Suche?
Zitat:
Delphi-Quellcode:
oder
[1, 2, 3, 4, ...]
Delphi-Quellcode:
hat, auch wenn beide 1.000.000 Elemente haben.[/nur dahingesagt]
[4, 8, 12, 16, ...]
@idefix2: +100 einbeliebigername. |
AW: Dictionary statt binärer Suche?
Warum war denn wohl mein erstes Fazit, dass der Hash-Algorithmus von stahli das Problem verursacht (zu langsam oder zu viele Kollisionen)? :roll:
Bei einer Entität ist die ID das ausschlaggebende Kriterium. Die ist gerne mal ein
Delphi-Quellcode:
und wird fortlaufend (Datenbank) vergeben. Da wird es sogar egal, wo die Instanz im Speicher liegt, der Hashwert wird über die ID erzeugt.
integer
Hier haben wir eine GUID. Na und, dann eben den Hashwert davon bilden. Aber mit Sinn und Verstand. Und wenn das Erzeugen zu lange dauert, dann einfach mit einem Cache des Wertes (muss ja eh ein stabiler Hashwert sein). |
Alle Zeitangaben in WEZ +1. Es ist jetzt 17:31 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz