Entwickler-Ecke
Algorithmen, Optimierung und Assembler - hash Eintrag
gerd8888 - Mi 27.04.11 16:49
Titel: hash Eintrag
Hallo,
ich habe eine string hash-table (ohne verkettete liste).
Zuerst ein paar Zeilen:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20:
| Type Thash_name=record h_name:string; h_tiefe:byte; end;
var hashmax:cardinal; hashliste:array of Thash_name;
for x:=1 to length(hash_string) do hash_wert:=(hash_wert * ord(hash_string[x])) mod length(hashliste); if (hash_wert)>length(hashliste) then begin hash_wert:=length(hashliste); end;
if hashliste[hash_wert].h_name='' then begin hashliste[hash_wert].h_name:=hash_string; hashliste[hash_wert].h_tiefe:=h1_tiefe; |
Das Problem liegt ganz genau in folgender Zeile:
Delphi-Quelltext
1:
| hashliste[hash_wert].h_name:=hash_string; |
Wenn ich nun mehrere Eintraege habe, dann wird es sehr, sehr langsam.
Wenn ich genau diese Zeile ausklammere, wieder verdammt schnell.
Komischerweise bei
Delphi-Quelltext
1:
| hashliste[hash_wert].h_tiefe:=h1_tiefe; |
was auch ein Eintrag-Vorgang ist, macht es nichts aus.
An den dyn. arrays kann es nicht liegen.
Ich weiss, dass es im Grunde nur Zeiger sind, und das einfügen und löschen Zeit kostet.
Ich weise aber ja nur ein Wert zu.
Ich verstehe also nicht, warum es ploetzlich so langsam wird.
Moderiert von
Martok: Delphi-Tags hinzugefügt
Dude566 - Mi 27.04.11 16:54
Bitte verwende die Delphi-Tags.
["delphi"]["/delphi"] ohne die Anführungszeichen. ;)
Martok - Mi 27.04.11 17:02
Dude566 hat folgendes geschrieben : |
Bitte verwende die Delphi-Tags.
["delphi"]["/delphi"] ohne die Anführungszeichen. ;) |
Dem schließe ich mich an ;)
Ich war mal so frei, das für dich zu erledigen/editieren.
gerd8888 - Mi 27.04.11 17:37
ich habe den Fehler jetzt herausgefunden. Er lag an einer ganz anderen Stelle...
Dude566 - Mi 27.04.11 18:27
Wäre bestimmt gut wenn du deine Lösung posten würdest, falls jemand mal das selbe Problem hat, findet er hier dann ja die Lösung. ;)
gerd8888 - Do 28.04.11 17:47
bei groessere Anzahl der stringkette ist die wahrscheinlichkeit auch groesser, dass der hash_wert immer 0 wird.
Dann ist die Streuung misslungen. Man hat dann eine einfache Vorwaertssuche. Das war der Fehler. Man kann ihn einfach beheben, indem man bei ord(hash_string[x] einfach -50 ergänzt. Ploetzlich, obwohl mit Sicherheit nicht optimal, geht es wieder verdammt schnell.
Aber ich bin selbst beim experimentieren und habe das als erstes ausgeschlossen.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!