Hashtable, wie benutzen?

[Furtbichler]

So ein Bloom Filter ist ja ganz lustig, aber ich bezweifle, das er schneller als eine Hashmap ist.

[BUG]

Ein Bloomfilter der Hashmap vorgeschalten werden und verhindern, dass bei einer Kollision (bei Millionen unterschiedlichen Werten nicht unwahrscheinlich) die Liste in einem Hashmap-Eintrag durchsucht werden muss.

Anders herum könnte man mit einem kleinem Filter und einer großen Hashmap ein bisschen vom Cache und davon profitieren, dass nicht ständig zufällig Speicherseiten eingeswap werden müssen, die zur Hashmap gehören.

Das könnte also schon was bringen.
Bei weiteren Überlegungen wäre es interessant zu wissen: wieviel Prozent der Werte, die du prüfen möchtest, sind denn in dem Array?

Wenn du noch Probleme hast, dir vorzustellen, wie du Hashmaps benutzt:
Sie implementieren ein assoziatives Array (wie es in Scriptsprachen überall genutzt wird).

[Iwo Asnet]

Zitat von BUG:

Ein Bloomfilter der Hashmap vorgeschalten werden und verhindern, dass bei einer Kollision (bei Millionen unterschiedlichen Werten nicht unwahrscheinlich) die Liste in einem Hashmap-Eintrag durchsucht werden muss.

Eine gute Hashmap skaliert, d.h. die Anzahl der Kollisionen ist dann relativ gering.

Zitat:

Das könnte also schon was bringen.

Das wäre denkbar. Bei den mir bekannten Bloomfilter-Implementierungen werden jedoch verschiedene Hashfunktionen verwendet. Dies dürfte der Pferdefuß werden.

[isilive]

Danke für eure Antworten!

Mein Array hat 25 Mio. Einträge und obwohl die lineare suche bei < 1 Mio Einträge noch ganz ok ist wenn man sie flott programmiert, wird es bei mehreren Mio. Einträgen eine Katastrophe.

Delphi-Quellcode:

for i:=0 to arraysize do   // arraysize=25 Mio.
array1[i]:=int64_x;        //irgendeine zahl, zB: Zufallszahl
  for j:=0 to i-1 do
    if int64_x = array1[j] then
      found:=true;

Der Rechenaufwand steigt zum Quadrat. O(n²)
Hab das Pgm 24h laufen gelassen und er ist bis 8 Mio. gekommen

Hab dann mjustins Vorschlag ausprobiert und die Generics.Collections verwendet.
Das TDictionary wie im Beispiel hat perfekt funktioniert und die Zeit auf O(n) reduziert!
Das ermöglicht die Abfrage der gesamten Tabelle auf einen doppelten Eintrag in <2 min !
Danke!

Trotzdem würde mich noch interessieren, wie man Alzaimars Hashtable benützt. Hat jemand einen kleinen Beispielcode?

[Iwo Asnet]

Delphi-Quellcode:

MyDict:= TIntegerDictionary.Create;
For i:=0 to Samples.Count do MyDict.Add(Samples[i],nil);

...
If MyDict.contains(SomeValue) Then ....

so ähnlich sollte es gehen.

[Horst_]

Hallo,

@isilive:
Was tut denn dies Programm?

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

Wie Aphton schon schrieb:
Du könntest die Daten sortieren oder stattdessen ein IndexFeld anlegen, dass dort die Daten sortiert vorliegen und dort dann die binäre Suche durchführen.

Delphi-Quellcode:

function VergleichsFunktion(i,j: integer):integer;
var
  Test : Int64;
begin
  result := 0;
  Test := array[Index[i]]-array[Index[j]];
  IF Test> 0 then
    result := 1;
  else
    IF Test< 0 then
      result := -1;
end;
...
//Daten auffüllen
 if array[Index[i]]< array[Index[i]]
for i:=0 to arraysize do // arraysize=25 Mio.
 begin
 array1[i]:=int64_x;
 Index[i]:= i;
 end;

QuickSort(Index,VergleichsFunktion);

Wenn Du schon während des Aufbauens der Felder Doppelte vermeiden willst, kannst Du ja sortieren durch Einfügen anwenden.

Gruß Horst

[Furtbichler]

Zitat von Horst_:

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.

[isilive]

Zitat von Iwo Asnet:

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!

[Horst_]

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.