[Delphi] hash Eintrag
spacer
Autor Nachricht
gerd8888
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 56



BeitragVerfasst: Mi 27.04.11 16:49 
Verwendete Sprache: Delphi
Hallo,

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

ausblenden Delphi-Quelltext markieren
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 markieren
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 markieren
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
 
Antworten mit Zitat Beitrag melden
Private Nachricht sendenPosting in privater Nachricht zitieren
Werbung ausblenden? Dann registriere Dich kostenlos. Weitere Gründe für eine Registrierung.


Werbung ausblenden? Dann registriere Dich kostenlos. Weitere Gründe für eine Registrierung.
Dude566
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 1486
Erhaltene Danke: 72

W7, Vista, XP, Ubuntu
Delphi XE2 Pro, Turbo Delphi, Java/Eclipse, Notepad++
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.
 
Antworten mit Zitat Beitrag melden
Private Nachricht sendenPosting in privater Nachricht zitieren
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Moderator
Beiträge: 2837
Erhaltene Danke: 182

Win 2000, Win XP
Delphi 7, Turbo Delphi Exp.
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."
Ich code EdgeMonkey -~==~- #ee-lounge in Freenode
 
Antworten mit Zitat Beitrag melden
Private Nachricht sendenPosting in privater Nachricht zitieren
gerd8888 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 56



BeitragVerfasst: Mi 27.04.11 17:37 
ich habe den Fehler jetzt herausgefunden. Er lag an einer ganz anderen Stelle...
 
Antworten mit Zitat Beitrag melden
Private Nachricht sendenPosting in privater Nachricht zitieren
Dude566
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 1486
Erhaltene Danke: 72

W7, Vista, XP, Ubuntu
Delphi XE2 Pro, Turbo Delphi, Java/Eclipse, Notepad++
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.
 
Antworten mit Zitat Beitrag melden
Private Nachricht sendenPosting in privater Nachricht zitieren
gerd8888 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 56



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.
 
Antworten mit Zitat Beitrag melden
Private Nachricht sendenPosting in privater Nachricht zitieren
home home