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);
    //nur zur Sicherheit
    if (hash_wert)>length(hashliste) then begin
      hash_wert:=length(hashliste);
    end;

  if hashliste[hash_wert].h_name='' then begin
    //eintragen;
    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 user profile iconMartok: 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

user profile iconDude566 hat folgendes geschrieben Zum zitierten Posting springen:
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.