Hashing Problem

[stoxx]

mir ist gerade aufgefallen, dass ein Algorithmen Forum sehr nützlich wäre :-)

ich habe ein Problem, und komme nicht so recht weiter.
Auch weil ich mich nicht genügend mit dem Thema Hashing auskenne.

Ich habe folgende Ausgangsvariablen.
viele aufeinanderfolgende wahr und falsch Sequenzen.

a : array [1..63] of boolean;

das würde dann ungefähr so aussehen.
10001010100010100100 ....1010100

daraus möchte ich eine Integer Zahl machen (da brauche ich INT64 Zahlen )

aus 1110 wird dann z.B. 14

jetzt komm ich hier nicht weiter.
Ich suche ein Hash Funktion, die mir die optimale Adresse liefert.
Mein Problem. Ich weiß zwar, was die angeblichen vorteile eines Hashes sind, bekomme das selber aber irgendwie nicht so recht auf die Reihe.
Weiß jemand Rat ? .. stecke irgendwie in einer Sackgasse.
Binäre Bäume möchte ich nicht nehmen, wegen den vielen Zeigern
(ich möchte nur 4 Byte pro Datensatz speichern), die Zeiger würden das ganze dann auf 4 + 8 = 12 Byte aufblähen

[Pascal]

Hallo,
ich verstehe leider nicht, was du genau machen möchtest.
Du hast doch in deinem array schon alle Informationen, was möchtest du nun in einer Hashtabelle speichern bzw. warum willst du deine Werte in Integer-Zahlen umrechnen. Ist mir nicht ganz klar!

Hashtabellen benützt du normalerweise, um Daten in eine Tabelle zu speichern und möglichst schnell wieder zu finden.

Vielleicht kannst du dein Problem noch mal genauer erklären!

Gruß Pascal

[negaH]

Erstmal kannste dein A: array[0..63] of Boolean optimieren auf 1/8 der jetzigen Größe wenn du A: Int64 nutzt. Jedes Bit in A wäre dann ein Boolean aus A[]. Nun sortierst du diese A's binär in eine Liste ein. Die Suche nach einem A wäre dann die Suche in dieser Liste von Int64 Werten. Angenommen 1024 solcher A's sind in der Liste, dann benötigst du nur maximal 10 Vergleiche per Binärer Suche um das richtige A zu finden. Somit benötigst du überhaupt keinen Hashalgortihmus, er wäre in deinem alle sinnlos und wesentlich langsammer. Die Suche nach der richtigen Einfügeposition in der Liste für ein neues A wäre bei 1024 Einträge ebenfalls nur 10 Vergleiche maximal. Beim Einfügen selber müsste man aber ca. 512 Einträge durchschnittlich im Speicher kopieren.

Gruß Hagen

[stoxx]

Zitat:

Zitat von Pascal

Hallo,

Vielleicht kannst du dein Problem noch mal genauer erklären!

Gruß Pascal

Hallo Pascal,

also ich möchtei die Daten so schnell wie möglich wiederfinden.
Das ist das wichtigste daran.
Sonst stelle ich keine Bedingungen an die Hashtabelle.
Die Daten müssen nicht sortiert ausgegeben werden oder so.

Zitat:

Du hast doch in deinem array schon alle Informationen,

naja .. es treten ja nicht alle Kombinationen von 001010011 auf.
(Aber aus diesem Bereich sind alle möglich)
Also umgerechnet nicht alle Integer Zahlen von 0 bis 2^64.
Weil das nämlich auch die Grenzen meines Computer sprengen würde *g*
Also kann ich nicht für jede Sequenz von 01001 linear eine Array Stelle festlegen.
Also brauch ich ein kleineres array als 2^64, brauche aber nun eine Adress Berechnung, wo die Werte abgespeichert werden, und zum schnellen Finden wäre es halt günstig, wenn das in Form einer Hashtabelle geschehen würde, da ja dort der Schlüssel aus der "information" berechnet wird.
Aber ich seh doch noch nicht so recht durch.

Bin aber schon bissl weitergekommen, mal sehen ob ich das verstehe.
Das hier brauch ich im Prinzip.
http://www.informatik.uni-ulm.de/dbi...ualHashing.pdf

[stoxx]

Zitat:

Zitat von negaH

Die Suche nach der richtigen Einfügeposition in der Liste für ein neues A wäre bei 1024 Einträge ebenfalls nur 10 Vergleiche maximal.
Gruß Hagen

Hi Hagen,

1024 .. also so wenig Einträge sind es halt nicht.
Die Umrechnung von dem array of boolean nach int64 kommt ja ganz zuerst.
Danach will ich 4 Byte grosse Datensätze, wo int64 verschiedene Möglichkeiten vorkommen können, auf die Festplatte speichern.

[jbg]

In 4 Bytes (Int32) bekommt man keine 8 Bytes (Int64).


Durch deine Ausführungen, komme ich noch nicht dahinter, was dein eigentliches Ziel ist. Soll der Hash-Wert 4 Bytes groß sein? Wo kommen dann die Int64s her?

[negaH]

Wieviele solcher Int64 willst du erwartungsgemäß verwalten ?
Das einzigste Problem mit meinem obigen Vorschlag wäre das Einfügen eines neuen Int64 in die Liste. Da dann Speicherkopierungen nötig wären. Wenn du aber nur maximal 2^16 solcher Werte verwalten willst dann wäre der beste Weg ein Array mit verlinkten Int64 Werten zu benutzen. D.h. ein Eintrag sähe so aus

Delphi-Quellcode:

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;

TEntryArray wird succesive blockweise vergößert. Also zb. erst 1024, 2048,4096 usw. Bei 65535 max. Einträgen würden so nur 7 Reallokationen dieses Arrays auftreten. Mit 2^16 Einträgen würde das Array 2^16*10 = 650Kb im Speicher benötigen. Das Einfügen eines neuen Wertes benötigt KEINERLEI Kopieroperationen, da der neue Wert nur ans Ende des Arrays angehangen wird. Die Binäre Suche ist dagegen ein bischen komplizierter, da nun das Array über deren .Next Einträge durchsucht werden müsste. Für einen neuen Wert sucht man im Array den Eintrag der der kleinste Eintrag genau vor dem neuen Wert ist. Dessen .Next wird auf die Anzahl der im Array gespeicherten Einträge gesetzt, also auf den neuen Eintrag. Der neue Eintrag wird als letzer im Array eingefügt und dessen Next wird auf das Next des kelinesten Eintrages gesetzt. Danach wird der Counter für die Anzahl der Einträge im Array um eins hochgezählt.

Gruß Hagen

[negaH]

Also, ich glaube du verstehst nicht wie Hash-Listen funktionieren. Beiu einer Hashliste wird der große Datenwert möglichst eindeutig und gleichverteilt auf einen kleineren Datenwert runtergerechnet. Das dieser Hashwert NICHT alle Werte exakt beschreiben kann ist dann auch logisch. Somit muß bei der Verwendung einer Hashtabelle diese Hashtabelle gespeichert werden UND alle exakten Werte die diese Hashtabelle verwaltet. In deinem Falle musst du also einen HashEntry benutzen mit Int32 als HashWert + Int32 als Index ind Wertetabelle + Int64 als eigentlichen Wert. Somit würde eine Hashtabelle viel mehr Speicher benötigen und da die Komprimierung von 64Bit runter auf 32Bit viel zu gering ist, wäre die hashtabelle zudem ineffizient.

Ich weis das Hashtabellen immer wieder als Allheilmittel bezeichnet werden, aber genau dies ist niemals der Fall. Hashtabellen sind Krücken die bei großen Datenstrukturen die aber auf Grund ihrer Wahrscheinlichkeiten des Datenaufkommens nur ein extrem begrenztes Set unterstützen, Anwendung finden. D.h. einen Hashtabelle ist immer dann effizient wenn sie z.b. 1024 HashWerte auf eine mögliche Datenmenge von 256 Bit Werten von denen aber nur 2048 Werte tatsächlich vorkommen würden, mappen kann.

Gruß Hagen

[negaH]

Zitat:

1024 .. also so wenig Einträge sind es halt nicht.

Bei 1024 Einträgen würdest du nach 10 Vergleichen mit Werten aus dem Array herausfinden ob der aktuelle 64Bit Wert schon im Array ist. Bzw. in 10 Vrgleichen würdest du die EInfügeposition ermitteln können.
Bei 2048 Einträgen wären 11 Vergleiche nötig, da 2^11 = 2048. Somit bei 65535 Einträgen nut 16 Vergleiche. Die Anzahl dieser Vergleiche ist die Anzahl im Worst Case, also im schlechtesten Falle. Im Durchschnitt würden man aber bei 2^16 Elementen im Array nur 8 Vergleiche benötigen !

Schneller kann eine Hashfunktion auch nicht sein. Eine hashfunktion würde diese 2^16 Elemente durch ein Array von z.B. 1024 Word's beschreiben. D.h. 1 Eintrag im hasharray ist der Index in eine Int64 Tabelle. Man zieht vom in64 ein 16Bit Hash der dann an die Position im array positioniert. So, bei 1024 Haswerten im hasharray würden 65535/1024 = 64 Duplikate pro hashwert möglich sein. D.h. jeweils 64 Int64 Werte teilen sich ein und selben Hashwert. Somit würde die hashtabelle beim Heraussuchen von 65535 Werten a 64Bit mit einer Berechnung 63/64 aller Werte ausfiltern. Die restlichen 64 Werte müssten wiederum ber Vergleichssuche gefunden werden. Nimmt man dafür eine Binäre Suche so wären 6 Vergleiche nötig. 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.

Gruß Hagen

[negaH]

Eine sehr einfache Form einer Hashtabelle wäre folgende.
Aus dem Int64 extrahierst du die obersten 2 Bytes = Word. D.h. der Int64 wird in einmal 2 Bytes + 6 Bytes zerlegt. Nun werden 65535 Arrays of Array of TWert angelegt. Die obersten 2 Bytes sind der Index in diese Array of Array Tabelle.
So und nicht anders würde eine Fulldomain-Hashfunktion arbeiten. Wenn du dir das durchrechnest dann siehst du das eine Hashfunktion in deinem Falle ineffizienter als eine binär sortierte verlinkte Liste mit 64 Bit Werten.

Gruß Hagen

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