Hashtable, wie benutzen?

[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.

[Horst_]

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