Autor Beitrag
gerd8888
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 205
Erhaltene Danke: 3

Win7
Delphi 10.1 Starter (kostenlos) Lazarus
BeitragVerfasst: Mi 27.04.11 16:49 
Hallo,

ich habe eine string hash-table (ohne verkettete liste).
Zuerst ein paar Zeilen:

ausblenden 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:

ausblenden 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

ausblenden 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
ontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic starofftopic star
Beiträge: 1592
Erhaltene Danke: 79

W8, W7 (Chrome, FF, IE)
Delphi XE2 Pro, Eclipse Juno, VS2012
BeitragVerfasst: Mi 27.04.11 16:54 
Bitte verwende die Delphi-Tags.

["delphi"]["/delphi"] ohne die Anführungszeichen. ;)

_________________
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 3661
Erhaltene Danke: 604

Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
BeitragVerfasst: 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.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
gerd8888 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 205
Erhaltene Danke: 3

Win7
Delphi 10.1 Starter (kostenlos) Lazarus
BeitragVerfasst: Mi 27.04.11 17:37 
ich habe den Fehler jetzt herausgefunden. Er lag an einer ganz anderen Stelle...
Dude566
ontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic starofftopic star
Beiträge: 1592
Erhaltene Danke: 79

W8, W7 (Chrome, FF, IE)
Delphi XE2 Pro, Eclipse Juno, VS2012
BeitragVerfasst: 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. ;)

_________________
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.
gerd8888 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 205
Erhaltene Danke: 3

Win7
Delphi 10.1 Starter (kostenlos) Lazarus
BeitragVerfasst: 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.