Hashing Problem

[stoxx]

Hallo Hagen,

> Bei einer Hashliste wird der große Datenwert möglichst eindeutig und
> gleichverteilt auf einen kleineren Datenwert runtergerechnet.

ja .. genau sowas suche ich ja


die binäre Suche geht doch nicht, da die Datensätze NICHT sortiert vorliegen, und ich auch nicht sortieren kann.




> Wieviele solcher Int64 willst du erwartungsgemäß verwalten ?

~ 2^32 Datensätze mit jeweils 4 Byte.
Da komm ich auf 16384 MB auf der Festplatte.
Grosses Umkopieren zum Einsortieren und Sortieren ist da nicht möglich.

type
TEntry = packed record
Value: Int64; // array[0..63] of Boolean
Next: Word; // Index des nächsten Eintrages in TEntryArray
end;

TEntryArray = array of TEntry;


müsste man umändern auf

type
TEntry = packed record
Value: Int64; // array[0..63] of Boolean
Information : integer;
Next: longint; // word reicht nicht
end;

TEntryArray = array of TEntry;


> Ich weis das Hashtabellen immer wieder als Allheilmittel bezeichnet
> werden, aber genau dies ist niemals der Fall.


also ist meine Aufgabe jetzt so nicht lösbar, wie ich mir das gedacht habe ?

[negaH]

Nochmal genauer: Zu jedem 64Bit Wert = äquivalent zu deinem A: array[0..63] of Boolean, wird per Hashfunktion ein 32Bit Hash erzeugt. Da dieser logischer weise niemals alle möglichen 2^64 Werte representieren kann muß man, wenn die Hashtabelle funktionieren soll, auch alle der in der Hashtabelle gehashten 64 Bit Werte gespeichert werden. D.h. also, du musst auf Platte die 2^32 Hashwerte + alle 64Bit Werte die die Hash Tabelle representiert speichern. NUR die Hashtabelle zu speichern bringt rein garnichts, da jeder 32 Bit Hash nur 1/2^32'tel aller möglichen 64 Bit Werte EINDEUTIG beschreibt !
Deine Hashtabelle würde also im schlechtesten Falle 2^32 * 4 Bytes Hash + 2^32 * 2^32 * 8 Bytes Werte speichern müssen. In diesem Falle wären ALLE 64 Bit Werte durch diese Tabellen gespeichert wurden. Nun kannst du per Wahrscheinlichkeiten diese Werte runterrechnen, und wirst immer feststellen das eine Hash Tabelle immer schlechter abschneidet als ein einfaches Array of Int64. Beim Array of Int64 hast du eben nur das Problem das beim Einfügen in dieses Array von einem Element alle nachfolgenden Element um eine Position verschoben werden müssen. Dies kann man aber extrem effizient gestalten, wenn man mit temporären Zwischenarrays arbeitet. D.h. man hat das Hauptarray das sortiert Int64 Werte enthält. Nun speichert man die nächsten 256 Int64 Werte in ein anderes array das ebefalls sortiert ist. Ist dieses array mit 256 Elementen voll, so wird dieses array in das große array eingefügt. Man macht dies indem man das große array um 256 Elemente vergrößert, nun fängt man von hinten nach vorne an die Elemente aus dem kleinen array in das große array einzufügen. Dabei wird einfach solange die Elemente im großen array an die höchste Position kopiert bis man ein Element im kleinen array findet das größer als das nächtse im großen array wäre. Diese Element fügt man dann ein usw. usw. bis das kleine array leer ist.
Somit würde dieser Einfügealgortihmus nur alle 256 Einfügeelemente mal, das große array umkopieren. Zudem würde die Wahrscheinlichkeiten und die Menge aller umzukopierenden Elemente auf ein Minimum reduziert.

Will man nun wissen ob ein neues Element schon in der List vorhanden ist dann müsste man per binärer Suchen nun 2 arrays durchsuchen. Bei 2^16 Einträgen im großen Array und 2^8 im kleinen array müsste man im schlechtesten Falle 24 Vergleiche durchführen. Das ist aber von der Komplexität besser als eine Hashliste da der Speicherverbrauch exakt 64Bit*Anzahl Einträge wäre. Bei einer Hashliste wäre der minimale Speicherverbrauch 2^32 * 32Bit + Anzahl Einträge * 64 Bit.


Gruß Hagen

[negaH]

Ich will dir eigentlich nur verdeutlichen das Hash Tabellen eher ineffizient sind in allgemein gültigen Szenarien. Nur in sehr speziellen Fällen werden hash Tabellen einen Vorteil bringen der dann aber enorm sein kann. Man muß also immer die Theorie der Hashtabellen begriffen haben und gleichzeitig die Wahrscheinlichkeiten und das Datenaufkommen des eigenen Algorithmus berücksichtigen, damit eine Hashtabelle überhaupt effizient sein kann. Im WEB und in vielen Foren hört man immer wieder "nim eine Hashtabelle das ist das effizientest Verfahren", dies ärgert mich jedes mal wieder da es einfach falsch ist aus Sicht einer Verallgemeinerung.

Gruß Hagen

[negaH]

So, jetzt wäre es an der Zeit für dich uns zu erkären wofür du diesen Algorithmus benötigst und was in deinen Daten gespeichert wird. Meistens findet man nämlich durch Umorientierung im übergeordneten Algorithmus ein viel effizienteren Weg, bzw. man kann den übergeordneten Algo. so umbauen das eine Hashtabelle sinnvoll wird.

Gruß Hagen

[stoxx]

Hallo Hagen,

also erstmal muss ich sagen, dass ich die Idee mit dem kleinen Zwischenarray, was man nur nach und nach in das grosse Array einordnet sehr gut
Danke, so werde ich es dann auch machen.

Zitat:

D.h. insgesamt würde eine Hashtabelle 4 Vergleiche im Duerchschnitt benötigen, im Gegensatz zu 8 bei einer reinen binären Suche. Dafür benötigt die hashtabelle ein wesentlich komplexerer Struktur die ihre Zeit kostet. In deinem Falle wäre dieser Zeitliche Aufwand aber der Performancebestimmende Faktor.

Du redest von "normalen" Hash Tabellen richtig ?
Es stand nämlich eigentlich hier, dass das gerade eben nicht mehr der Fall ist

http://www.informatik.uni-ulm.de/dbi...ualHashing.pdf

kennst Du denn das Verfahren des linearen virtuellen Hashings ?
Ich verstehs eben nicht, auch nach mehrmaligem Durchlesen.
Wahrscheinlich, weil ich mit "normalen" Hashes bisher auch nix zu tun hatte.



Und dann steht dort eben noch, das man keine grosse Hashtabelle braucht
Zitat:

Hieraus kann man nun natürlich folgern, daß das lineare virtuelle Hashverfahren sehr schnell
arbeitet. Selbstverständlich braucht lineares Hashing auch Hintergrundspeicherplatz,
allerdings nur für die Zeiger auf die Buckets, und dieser Platzbedarf ist minimal.

[negaH]

Nein ich kenne dieses Verfahren noch nicht. Aber die PDF habe ich mir schon mal gesichert

Was mir beim ersten Überfliegen aber aufgefallen ist ist der Punkt das wenn man keinerlei Ahnung von Hashalgos. im Allgemeinen hat einen falschen Eindruck von Anfang an bekommt.

Zu jedem Datensatz wird ein haswert erzeugt der dann in einer Hashtabelle = Index gesucht wird bzw. eingefügt wird. Diese Aussage IST wichtig da es IMMER der Fall ist das dieser Datensatz auch gespeichert werden muß. In deinem Falle heist das eine Hashtabelle als Index + eine Tabelle mit alle Datensätzen zu diesen Hash's muß gespeichert werden.

Ansonsten hört sich der Name des PDF's gut an, wenn das Verfahren hält was es verspricht. Aber um es gleich vorweg zu nehmen, ich habe nicht vor diese DPF genauer zu studieren oder einen Source zu coden, dazu fehlt mir einfach die Zeit und die Notwendigkeit.

Gruß Hagen

[stoxx]

Äusserst wichtig ist das schnelle Auffinden des entsprechenden Wertes.
Die Erstellung der Datei ist nicht primär wichtig, und kann auch länger dauern.

In dem PDF File stand halt, dass IMMER nur ein direkter Zugriff nötig ist, und nicht wie bei normalen Tabellen mehrere Zugriffe im Falle von Kollisionen.
Nachteil wäre eben, dass man die Datensätze nicht mehr sortiert ausgeben kann. Dies brauche ich aber nicht.

Zitat:

Aber um es gleich vorweg zu nehmen, ich habe nicht vor diese DPF genauer zu studieren oder einen Source zu coden, dazu fehlt mir einfach die Zeit und die Notwendigkeit.

Wäre es unter Umständen möglich, dass ich Dir während der Entwicklung immer mal paar Fragen stellen könnte ?

[negaH]

Zitat:

Wäre es unter Umständen möglich, dass ich Dir während der Entwicklung immer mal paar Fragen stellen könnte ?

Ja aber natürlich !