AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Hashtable, wie benutzen?

Ein Thema von isilive · begonnen am 28. Mär 2012 · letzter Beitrag vom 25. Apr 2012
Antwort Antwort
Seite 2 von 3     12 3   
Furtbichler
(Gast)

n/a Beiträge
 
#11

AW: Hashtable, wie benutzen?

  Alt 31. Mär 2012, 14:57
Delphi-Quellcode:
for i:=0 to arraysize do // arraysize=25 Mio.
 begin
 array1[i]:=int64_x; //irgendeine zahl, zB: Zufallszahl
 for j:=0 to i-1 do
  if int64_x = array1[j] then
    found:=true;
 end;
Es kann ja nichts finden. Du fügst eine Zahl bei Index i ein suchst aber bis Index i-1
Er muss ja nix finden: Ich packe an die N+1.te Stelle eine Zahl und erhöhe nur, wenn die Zahl vorher (0..N) noch nicht gefunden wurde.

Sofern die Daten nicht sortiert vorliegen, sollte das Ausschließen doppelter Einträge über eine Hashmap am Schnellsten sein. Das Suchen eines Elements in einer Hashmap ist vom Aufwand O(1), das binäre Suchen dagegen O(log n).

Die Hashfunktion einer 64-bit Zahl lässt sich auf N mod <HashMapSize> kürzen.

Ich schaffe hier 1 Mio Tests in 370ms. Das wäre ja auszuhalten.
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#12

AW: Hashtable, wie benutzen?

  Alt 1. Apr 2012, 01:31
Hallo,

Binsuche dauert zwar "nur" etwa 4xmal so lang auf meinem 2,3 Ghz Notebook bei 1 Mio Elementen, aber das Aufrechterhalten der Sortierung kostet viel zuviel Zeit.

Gruß Horst

Geändert von Horst_ ( 1. Apr 2012 um 07:44 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von isilive
isilive

Registriert seit: 15. Okt 2008
Ort: Österreich
192 Beiträge
 
Delphi 2009 Professional
 
#13

AW: Hashtable, wie benutzen?

  Alt 1. Apr 2012, 14:29
Delphi-Quellcode:
MyDict:= TIntegerDictionary.Create;
For i:=0 to Samples.Count do MyDict.Add(Samples[i],nil);

...
If MyDict.contains(SomeValue) Then ....
Ok, soweit war es mir schon klar, aber:
- Der Pointer kriegt einfach immer NIL übergeben?
- Brauch ich das Array "Samples[]" auch, oder übernimmt das Dictionary beide Datenfelder?

Nehmen wir mal ich habe
einen fortlaufenden Integer 0..5Millionen
jeweils eine zugehörige Zufallszahl vom Typ INT64
und die INT64 möchte ich auf Gleichheit/Kollision überprüfen und dann den zugehörigen Integer wissen.

Was übergebe ich dann dem Dictionary? Nur Mydict.add(INT64, nil)? Und den zugehörigen Integer muss ich mir dann im Array suchen? Oder kann ich Integer UND Int64 im MyDict speichern?
Danke!
Stefan
Jedoch kann die referenzbasierte Implementierung des Standard-Objektmodells in Kombination mit den komplexen syntaktischen Dereferenzierungsregeln bei einer objektorientierten API wie ein Stolperstein wirken.
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#14

AW: Hashtable, wie benutzen?

  Alt 2. Apr 2012, 11:25
Hallo,

ich habe jetzt keine Version von csDictionary gesehen, die mit Int64 umgeht, sondern nur cardinal.
Deshalb habe ich dort einen TDictIntType eingeführt und dann auf Int64 zugewiesen.
Die procedure Add habe ich in eine Function:boolean umgewandelt, damit ich weiß, ob der Wert eingefügt wurde, also schon vorhanden war, sonst hätte ich .contains nutzen müssen, was in .Add ja auch gemacht wird.
Das sollte ich vielleicht alzaimar ( wo ist der überhaupt ? ) vorschlagen.

Ich habe statt eines Pointers auf den Schlüssel A64[j] den Index j im Feld A64 im Hashfeld abgespeichert.

10 Mio Werte sind in 7,6 Sekunden eingefügt.( 420 MB belegt )
Delphi-Quellcode:
A64 : array of TDictIntType;//Int64
  j := low(A64);
  For i := low(A64) to High(A64) do
    begin
    Wert := random(RANDOMRANGE);
    // Nur wenn der Wert nicht doppelt war
    // wird er eingefuegt
    IF TestHash.Add(Wert,Pointer(j)) then
      begin
      A64[j] := Wert;
      inc(j);
      end;
    end;
  setlength(A64,j);
Anhand des Schlüssels erhält man also die Position im Feld.
Die Ausgabe auf dem Notebook ist dann:
Code:
Erzeugen von 10000000 Zufallszahlen [0..9223372036854775806] 00:00:00,678
Einfügen von 10000000 verschiedenen Daten in 00:00:07,546
         0  702565670347126292    TRUE        0
         1 8731026331172931038    TRUE        1
         2 7315597276161830344    TRUE        2
         3 6054991081758643474    TRUE        3
         4  974630338373080205    TRUE        4
         5 2802662720263935392    TRUE        5
         6  992661471859547074    TRUE        6
         7 7770774513438344891    TRUE        7
         8 2847780276242346111    TRUE        8
         9 8442204931085970693    TRUE        9
        10 2662600269196791808    TRUE       10
Auflösen der Hashmap in 00:00:04,574
25e6 Werte brauchen über 1 Gbyte

Ich hoffe den Index abzuspeichern macht Sinn für Dich

Gruß Horst
P.S
In einer Hash-Tabelle kann es keine doppelten Einträge geben.

Edit: ich habe create geändert, sodass man man die zu erwartende Anzahl der Elemente vorgeben kann, das beschleunigt auf dem Desktop Rechner die Einfüge Zeit von 15,5 auf 7,6 Sekunden, der Abbau dauert 8,4 Sekunden.
Angehängte Dateien
Dateityp: zip CsDictTest.zip (4,4 KB, 14x aufgerufen)

Geändert von Horst_ ( 2. Apr 2012 um 16:53 Uhr) Grund: Modifikationen
  Mit Zitat antworten Zitat
Benutzerbild von isilive
isilive

Registriert seit: 15. Okt 2008
Ort: Österreich
192 Beiträge
 
Delphi 2009 Professional
 
#15

AW: Hashtable, wie benutzen?

  Alt 24. Apr 2012, 04:51
Danke, habs jetzt unter Delphi 2009, Win7 zum laufen gebracht. Allerdings knallt es regelmässig nach ca. 500 bis 2000 Schleifendurchläufen und zwar beim
Delphi-Quellcode:
Hash.Add:

-> Zeile 535 der DictionaryUnit
   With PIntHashEntry(Result)^ Do
     If heKey = aKey Then <-- hier knallts
       Exit
Wohl bei der ersten Kollision?! Warum versteh ich noch nicht ganz...

Verstehe ich deinen Programmablauf richtig, dass die Hashmap verhindert, dass ein schon vorhandener Wert ins Array kommt?

PS: QWord kennt mein Delphi nicht. Habs durch INT64 ersetzt.
Stefan
Jedoch kann die referenzbasierte Implementierung des Standard-Objektmodells in Kombination mit den komplexen syntaktischen Dereferenzierungsregeln bei einer objektorientierten API wie ein Stolperstein wirken.
  Mit Zitat antworten Zitat
Iwo Asnet

Registriert seit: 11. Jun 2011
313 Beiträge
 
#16

AW: Hashtable, wie benutzen?

  Alt 24. Apr 2012, 08:37
Kann ich nicht nachvollziehen (D2007).
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#17

AW: Hashtable, wie benutzen?

  Alt 24. Apr 2012, 10:10
Hallo,

ich bekomme den Fehler auch nicht hin
Ich habe mal DictFind.pas geändert.
Es wird jetzt eine lineare Liste erzwungen.
Delphi-Quellcode:
function myRandom(i : TDictIntType):TDictIntType;inline;
begin
  result := i*ccInitialSize+17;//random(i);
end;
denn alle erzeugten Zahlen Wert sind verschieden, aber (Wert mod ccInitialSize) = 17.
Delphi-Quellcode:
program DictFind;
{$IFDEF FPC}
  {$MODE DELPHI}
  {$OPTIMIZATION ON}
  {$OPTIMIZATION REGVAR}
  {$OPTIMIZATION PEEPHOLE}
  {$OPTIMIZATION CSE}
  {$OPTIMIZATION ASMCSE}
{$ELSE}
  {$APPTYPE CONSOLE}
{$ENDIF}

uses
  sysutils,csDictionary;
  
const
  LAENGE = 25*1000*1000;
  RANDOMRANGE = 1000*100;
// RANDOMRANGE = High(tDictIntType);

type
  tArr64 = array of TDictIntType;
var
   t1,t0,dt : TDateTime;
   Wert : TDictIntType;
   dummy : Pointer;
   i,j: integer;

   A64 : tarr64;
   TestHash : TIntegerDictionary;
   
function myRandom(i : TDictIntType):TDictIntType;inline;
begin
  result := i*ccInitialSize+17;//random(i);
end;

BEGIN
  randomize;
  setlength(A64 ,LAENGE);
  TestHash:= TIntegerDictionary.create;

  t0 := time;
  For i := low(A64) to High(A64) do
    Wert := myrandom(i);//random(RANDOMRANGE);
    
  t1 := time;
  dt := t1-t0;
  Write('Erzeugen von ',LAENGE,' Zufallszahlen [0..',Randomrange-1);
  writeln(FormatDateTime('] hh:nn:ss,zzz',dt));

  t0 := time;
  j := low(A64);
  For i := low(A64) to High(A64) do
    begin
    Wert := myrandom(i);//myrandom(RANDOMRANGE);
    IF TestHash.Add(Wert,Pointer(j)) then
      begin
      A64[j] := Wert;
      inc(j);
      end;
    end;
  setlength(A64,j);
  t1 := time;
  Write('TotalCOunt :',TestHash.TotalCount:10);
  Write('Einfuegen von ',j,' verschiedenen Daten in ');
  writeln(FormatDateTime(' hh:nn:ss,zzz',t1-t0-dt));

  For i := low(A64) to 10 do
    writeln(i:10,A64[i]:20,TestHash.find(A64[i],dummy):8,integer(dummy):10);
  writeln(j-1:10,A64[j-1]:20,TestHash.find(A64[j-1],dummy):8,integer(dummy):10);
  t0 := time;
  testHash.free;
  t1 := time;
  Write('Aufloesen der Hashmap in ');
  Writeln(FormatDateTime('hh:nn:ss,zzz',t1-t0));
  setlength(A64,0);
  readln;
END.
Ich erhalte auch so keine Fehlermeldung mit Freepascal 2.6.0 /Win7

Gruß Horst
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
40.504 Beiträge
 
Delphi 11 Alexandria
 
#18

AW: Hashtable, wie benutzen?

  Alt 24. Apr 2012, 10:18
Kann ich nicht nachvollziehen (D2007).
Was?

Zitat:
hier knallts
Sagt mir so rein überhaupt nichts.


Vermutlicher Grund:
- der Zeiger "Result" ist defekt und zeigt sonstwohin
- der Zeiger "Result" steht auf nil, was natürlich zum knallen führt

Letzeres hätte man über die Fehlermeldung (die keiner kennt) leicht rausbekommen und mit dem Debugger gegenprüfen können.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#19

AW: Hashtable, wie benutzen?

  Alt 24. Apr 2012, 10:29
Hallo,

hier die Funktion bei Zeile 535:
Delphi-Quellcode:
Function TIntegerDictionary.FindHash(aKey : TDictIntType; Out h: Cardinal): Pointer;
Begin
  h := HashFromInt(aKey) Mod fHashMod;
  Result := fHashList[h];
  While PIntHashEntry(Result) <> Nil Do
    With PIntHashEntry(Result)^ Do
      If heKey = aKey Then
        Exit
      Else
        Result := heNext;
End;
Der Wert NIL wird abgefangen.
Was eventuell helfen könnte, ein paar unnötige Begin/end einzubauen, damit das with sich auch garantiert auf den else-Teil erstreckt, aber diese Zeiten sind doch wohl lange vorbei...

Delphi-Quellcode:
Function TIntegerDictionary.FindHash(aKey : TDictIntType; Out h: Cardinal): Pointer;
Begin
  h := HashFromInt(aKey) Mod fHashMod;
  Result := fHashList[h];
  While PIntHashEntry(Result) <> Nil Do
    Begin
    With PIntHashEntry(Result)^ Do
      Begin
      If heKey = aKey Then
        Exit
      Else
        Result := heNext;
      end;
    end;
End;
Man kann ja in der Zeile " If heKey = aKey Then" mit F9 einen Breakpoint setzen und dann mal laufen lassen.

Gruß Horst
  Mit Zitat antworten Zitat
Iwo Asnet

Registriert seit: 11. Jun 2011
313 Beiträge
 
#20

AW: Hashtable, wie benutzen?

  Alt 24. Apr 2012, 11:41
Zitat:
hier knallts
Kann ich nicht nachvollziehen (D2007).
Was?
Na was wohl?

Vermutlicher Grund:
- der Zeiger "Result" ist defekt und zeigt sonstwohin
- der Zeiger "Result" steht auf nil, was natürlich zum knallen führt

Letzeres hätte man über die Fehlermeldung (die keiner kennt) leicht rausbekommen und mit dem Debugger gegenprüfen können.
Es wird wohl keine NIL-Exception sein, denn 'Result' wird auf NIL geprüft und Delphi-Code ist deterministisch und korrekt.

Du willst vermutlich darauf hinaus, das die Problembeschreibung etwas knapp ist. Da hast Du sicherlich Recht, aber im Kontext reicht es.
Das Testprogramm wäre es noch wert, gepostet zu werden.

Oder man verwendet mal FastMM mit Sentinel, um zu prüfen, ob Speicherbereiche überschrieben werden.
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 06:36 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf