AGB  ·  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 1 von 3  1 23   
Benutzerbild von isilive
isilive

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

Hashtable, wie benutzen?

  Alt 28. Mär 2012, 13:59
Hallo Leute,

ich habe ein sehr grosses Array mit mehreren Millionen Einträgen vom Typ INT64.
Nun möchte ich diese Zahlen schnell auffinden können bzw. nachschauen, ob sie schon im Array existiert.
Ich denke dazu würde sich wohl eine Hashtable anbieten und ich hab diese hier gefunden.
Blöde Frage: Wie benutz ich die Hashtable?
Als TIntegerDictionary erwartet sie von mir bei Add(Key, Data) als Key einen Int64/Cardinal und als Data einen Pointer.
Heisst das ich erstelle mein Array wie gewohnt und liefere dann als Key den Index vom aktuellen Element und als Pointer einen Pointer zum aktuellen Element vom Array? Oder ersetzt die Hashtabelle das Array?
Hab noch nie Hashtabellen benutzt und verstehe grad das Grundprinzip nicht.
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
Benutzerbild von Aphton
Aphton

Registriert seit: 31. Mai 2009
1.198 Beiträge
 
Turbo Delphi für Win32
 
#2

AW: Hashtable, wie benutzen?

  Alt 28. Mär 2012, 14:39
Die Hashtabelle funktioniert im Prinzip ca so:
- Für jeden Input (Int64 in deinem Fall) wird ein Hash (Pseudo Hash Funktion; liefert in meisten Fällen eine Zahl im Bereich von 2^8 oder 2^16) berechnet
- Dieser Hash dient als Array Index (es existiert ein Array mit der festen Größe 2^8 oder 2^16 (Hash Max-Wert).
Das Array ist in meisten Fällen vom Typ <einfach verkettete Liste>
Dieser Liste werden die Daten angehängt.

Wenn du nun nach Input xyz suchst, musst du zuerst den Hash bilden, diesen als Index benützen und dann die Liste so lange durchiterieren, bis du das Element findest!

Edit:
Achja, evt. wäre hier die binäre Suche angebrachter, sofern die Daten sortiert vorliegen!
Bei genau 1.000.000 Datensätzen bräuchtest du nur ~20 Abfragen (=log2(1.000.000))

Edit2:
Man könnte ja auch beides Kombinieren und ein 2 dimensionales Array verwenden, wobei man auf die erste mit dem Hashindex zugreift und auf die Zweie die binäre Suche drüberjagt!
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG

Geändert von Aphton (28. Mär 2012 um 14:53 Uhr)
  Mit Zitat antworten Zitat
mjustin

Registriert seit: 14. Apr 2008
2.213 Beiträge
 
Delphi 2009 Professional
 
#3

AW: Hashtable, wie benutzen?

  Alt 28. Mär 2012, 15:49
Hallo Leute,

ich habe ein sehr grosses Array mit mehreren Millionen Einträgen vom Typ INT64.
Nun möchte ich diese Zahlen schnell auffinden können bzw. nachschauen, ob sie schon im Array existiert.
Ich denke dazu würde sich wohl eine Hashtable anbieten und ich hab diese hier gefunden
Delphi 2009 verwendet Hashtables in Generics.Collections,
man kann z.B. die Klasse TDictionary<Key, Value> nutzen:

Delphi-Quellcode:
type
  TMyInt64HashTable = TDictionary<Int64, Boolean>;
   ...

  // Hashtable mit fünf Millionen Einträgen Anfangskapazität
  Table := TMyInt64HashTable.Create(5000000);

  ...

  Table.Add(1, True);

  if Table.ContainsKey(1) then ...
Michael Justin

Geändert von mjustin (28. Mär 2012 um 16:15 Uhr)
  Mit Zitat antworten Zitat
bit4bit

Registriert seit: 14. Jun 2006
Ort: Köln
25 Beiträge
 
#4

AW: Hashtable, wie benutzen?

  Alt 28. Mär 2012, 22:32
Wenn Du wissen willst, ob die Zahl schon in Deinem Array drin ist, benutzt Du am besten ein Bloom Filter.

Ein negatives Ergebnis ist absolut verlässlich, die Zahl ist also 100%ig nicht im Array vorhanden.
Ein positives Ergebnis kann mit einer geringen Wahrscheinlichkeit falsch sein, d.h. Du musst das
Ergebnis mit einer anderen, etwas aufwendigeren Methode überprüfen um sicher zu sein.

Bloom Filter sind sehr schnell. Ich hab jedenfalls gute Ergebnisse damit erzielt.
Such einfach mal nach dem Begriff (z.B. Wikipedia).
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#5

AW: Hashtable, wie benutzen?

  Alt 29. Mär 2012, 09:36
So ein Bloom Filter ist ja ganz lustig, aber ich bezweifle, das er schneller als eine Hashmap ist.
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG
Online

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.080 Beiträge
 
#6

AW: Hashtable, wie benutzen?

  Alt 29. Mär 2012, 10:26
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).

Geändert von BUG (29. Mär 2012 um 11:03 Uhr)
  Mit Zitat antworten Zitat
Iwo Asnet

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

AW: Hashtable, wie benutzen?

  Alt 29. Mär 2012, 12:04
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.

Geändert von Iwo Asnet (29. Mär 2012 um 12:14 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von isilive
isilive

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

AW: Hashtable, wie benutzen?

  Alt 30. Mär 2012, 15:09
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?
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
 
#9

AW: Hashtable, wie benutzen?

  Alt 30. Mär 2012, 16:04
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.
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
116 Beiträge
 
#10

AW: Hashtable, wie benutzen?

  Alt 31. Mär 2012, 11:21
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
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23   

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:

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