|
Hashtable, wie benutzen?
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. |
AW: Hashtable, wie benutzen?
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! |
AW: Hashtable, wie benutzen?
Zitat:
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 ... |
AW: Hashtable, wie benutzen?
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). |
AW: Hashtable, wie benutzen?
So ein Bloom Filter ist ja ganz lustig, aber ich bezweifle, das er schneller als eine Hashmap ist.
|
AW: Hashtable, wie benutzen?
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). |
AW: Hashtable, wie benutzen?
Zitat:
Zitat:
|
AW: Hashtable, wie benutzen?
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:
Der Rechenaufwand steigt zum Quadrat. O(n²)
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; Hab das Pgm 24h laufen gelassen und er ist bis 8 Mio. gekommen :stupid: 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! :thumb: Trotzdem würde mich noch interessieren, wie man Alzaimars Hashtable benützt. Hat jemand einen kleinen Beispielcode? |
AW: Hashtable, wie benutzen?
Delphi-Quellcode:
so ähnlich sollte es gehen.
MyDict:= TIntegerDictionary.Create;
For i:=0 to Samples.Count do MyDict.Add(Samples[i],nil); ... If MyDict.contains(SomeValue) Then .... |
AW: Hashtable, wie benutzen?
Hallo,
@isilive: Was tut denn dies Programm?
Delphi-Quellcode:
Es kann ja nichts finden. Du fügst eine Zahl bei Index i ein suchst aber bis Index i-1 :?:
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; 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:
Wenn Du schon während des Aufbauens der Felder Doppelte vermeiden willst, kannst Du ja sortieren durch Einfügen anwenden.
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); Gruß Horst |
AW: Hashtable, wie benutzen?
Zitat:
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. |
AW: Hashtable, wie benutzen?
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 |
AW: Hashtable, wie benutzen?
Zitat:
- 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!:thumb: |
AW: Hashtable, wie benutzen?
Liste der Anhänge anzeigen (Anzahl: 1)
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:
Anhand des Schlüssels erhält man also die Position im Feld.
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); Die Ausgabe auf dem Notebook ist dann:
Code:
25e6 Werte brauchen über 1 Gbyte
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 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. |
AW: Hashtable, wie benutzen?
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:
Wohl bei der ersten Kollision?! Warum versteh ich noch nicht ganz...
Hash.Add:
-> Zeile 535 der DictionaryUnit With PIntHashEntry(Result)^ Do If heKey = aKey Then <-- hier knallts Exit 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. |
AW: Hashtable, wie benutzen?
Kann ich nicht nachvollziehen (D2007).
|
AW: Hashtable, wie benutzen?
Hallo,
ich bekomme den Fehler auch nicht hin :-( Ich habe mal DictFind.pas geändert. Es wird jetzt eine lineare Liste erzwungen.
Delphi-Quellcode:
denn alle erzeugten Zahlen Wert sind verschieden, aber (Wert mod ccInitialSize) = 17.
function myRandom(i : TDictIntType):TDictIntType;inline;
begin result := i*ccInitialSize+17;//random(i); end;
Delphi-Quellcode:
Ich erhalte auch so keine Fehlermeldung mit Freepascal 2.6.0 /Win7
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. Gruß Horst |
AW: Hashtable, wie benutzen?
Zitat:
Zitat:
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. |
AW: Hashtable, wie benutzen?
Hallo,
hier die Funktion bei Zeile 535:
Delphi-Quellcode:
Der Wert NIL wird abgefangen.
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; 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:
Man kann ja in der Zeile " If heKey = aKey Then" mit F9 einen Breakpoint setzen und dann mal laufen lassen.
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; Gruß Horst |
AW: Hashtable, wie benutzen?
Zitat:
Zitat:
Zitat:
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. |
AW: Hashtable, wie benutzen?
Dennoch sagen die Code- und Speicherpositionen manchmal was aus.
Also warum sollte man dann die Texte der Fehlermeldungen unterschlagen? |
AW: Hashtable, wie benutzen?
Es ist eine Zugriffsverletzung "Lesen von Adresse 00000001" und bezieht sich nur auf die abgewandelte .pas Datei von Horst, der sie ja primär auf Freepascal geschrieben hat. Der Fehler tritt unregelmässig und nur bei 500-2000 Schleifendurchläufen auf, was darauf hindeutet, dass es dann knallt wenns eine Kollision in der Hashtable gibt. (Aber um das genau zu wissen versteh ich das ganze Konstrukt noch etwas zu wenig.)
Die orginale .pas läuft und die hab ich jetzt auch verbaut. Also für mich ist die Exception hier kein Problem mehr. Hab jetzt leider keine Zeit, kann aber morgen mehr posten wenns gewünscht ist. |
AW: Hashtable, wie benutzen?
Zitat:
Zitat:
|
AW: Hashtable, wie benutzen?
Um nochmal auf die Hauptroutine von Horst zurückzukommen (warum seine dictionary.pas bei mir knallt ist momentan nicht so wichtig. Die orginale funzt ja tadellos.)
Delphi-Quellcode:
Das mit der Hashtable und dem Key ist klar und läuft auch. :)
j := low(A64);
For i := low(A64) to High(A64) do begin Wert := random(RANDOMRANGE); IF TestHash.Add(Wert,Pointer(j)) then begin A64[j] := Wert; inc(j); end; end; setlength(A64,j); //wieder auslesen aus der Hashtable: TestHash.find(A64[i],dummy) writeln (integer(dummy)); Aber was kann ich denn als Data abspeichern und somit als Pointer übergeben? Nur Integer? Und was wird dann abgespeichert, ein Adresspointer auf die übergebene Variable oder deren Wert? Also darf ich diese Variable danach verändern? Ist das Auslesen generell so vorgesehen wie in den unteren beiden Zeilen? Bei einem ersten Test hat's funktioniert. |
AW: Hashtable, wie benutzen?
Hallo,
man kann der Hash-table den Schlüssel und einen Zeiger auf irgendwelche Daten übergeben. Da aber da ja nur Index in das Feld gebraucht wird, reicht es, den integer Index in einen Pointer zu casten. Beim Auslesen wird der Pointer eben wieder in ein integer gecastet. Das geht aber nur, solange die Daten maximal soviel Speicher wie der type Pointer brauchen, bei 32 Bit-Systemem 4 Byte== LongInt und bei 64 Bit eben 8 byte = Int64. Gruß Horst P.S. csdictionary ist von alzaimar für Delphi hier aus der code-library. Ich habe nur den Typ des Schlüsselwertes geändert. Probiere mal Dictfind in http://www.delphipraxis.net/1163327-post17.html testen. |
AW: Hashtable, wie benutzen?
Die geht (mit deiner Version von csDictionary, das ich csDictionaryh getauft habe um Verwechslungen zu vermeiden).
Es liegt an "RANDOMRANGE" mit high(Int64). Bei "MyRandom" oder einer Randomrange:=high(Integer) funktioniert es problemlos. Rufe ich allerdings Dict.add (Testhash.add) mit random(high(Int64)) als key auf, dann kommt irgendwann die Exception. Tracen ist ein bisschen schwierig, weil es erst beim x-ten Schleifendurchlauf (500<x<5000) passiert.
Delphi-Quellcode:
Aber es passiert in der Zeile "If heKey = aKey then", also nur wenn ein Hashentry gefunden wurde.
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; |
AW: Hashtable, wie benutzen?
Hallo,
ich wollte mit myrandom eben keine Zufallszahlen erzeugen, sondern Zahlen, die in der Hashtable alle an der selben Stelle landen. Damit erzwinge ich im Beispiel 25 Mio -1 Kollisionen und die Erzeugung einer linearen Liste. Du hattest doch mal vermutet, das bei der ersten Kollision der Fehler mit dem Zugriff auf Speicheradresse 0...01 erfolgt sein könnte. Das kann man jetzt wohl ausschließen. Gruß Horst P.S: 2008 wusste alzaimar das sein csDictionary aus http://www.delphipraxis.net/45571-hash-tabellen.htmlnicht Int64 sondern cardinal ist, http://www.delphi-forum.de/viewtopic...=501690#501690 |
AW: Hashtable, wie benutzen?
Wie auch immer, auf jedenfall konnte ich schon erfolgreich die
orginale csDictionary verwenden. Ich hab mit grossen Zahlen gerechnet - mpArith von Wolfgang Ehrhardt. Das BigNumberErgebnis wollte ich zusammen mit einem Integer in eine Hashtable schreiben.Wenn man die bigNumber als String ausgibt kann man sie problemlos im Stringdictionary verwenden. Es ist praktisch, dass man Strings verschiedener Länge ohne Performanceverlust verwenden kann, da ja einfach gehasht wird. Und mit deinem Pointertrick konnte ich den zugehörigen Integer speichern und wieder lesen. Danke!!! :thumb:
Delphi-Quellcode:
Zwei Sachen:
var dummy:pointer;
begin j:=someinteger; IF TestHash.Add (Wert, Pointer(j)) then ... TestHash.Find (Zahl, dummy); j:=integer(dummy) end; - Dein "Pointertrick" ist cool. Aber wie lautet die Syntax die für den 2. Parameter normalerweise vorgesehen ist? (Übergibt man die Adresse eines Arrayelements um diese bei .Find wiederzubekommen?) - dict.add als function statt als procedure ist wirklich eine starke Verbesserung! Vielleicht würde es Alzeimar einbauen?! PS: Wen's interessiert, interessehalber hab ich dieselbe Hashmap danach mit Generics.collections inplementiert. Die Syntax ist sehr ähnlich, die Funktionalität auch und die resultierende Geschwindigkeit für 1 Mio. Einträge auch. Evtl. ist Generics um geschätzte 2-3 Prozent schneller. Zeigt, dass alzeimar hier einen guten Job geliefert hat. |
| Alle Zeitangaben in WEZ +1. Es ist jetzt 08:15 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz