Generische Klassenbibliothek - Bugs, Beschreibung, Fragen, Nutzungsmöglichkeiten und Vorschläge - Seite 10
Sie verpassen Handelsmöglichkeiten:
- Freie Handelsapplikationen
- Über 8.000 Signale zum Kopieren
- Wirtschaftsnachrichten für die Lage an den Finanzmärkte
Registrierung
Einloggen
Sie stimmen der Website-Richtlinie und den Nutzungsbedingungen zu.
Wenn Sie kein Benutzerkonto haben, registrieren Sie sich
Über Hash-Funktionen
Aus den vorangegangenen Beispielen ist ersichtlich, dass die Hash-Funktion die Hauptlast trägt. Eine Hash-Funktion kann so schnell wie möglich sein, aber sie ist höchstwahrscheinlich sehr kollisionsanfällig. Umgekehrt kann eine Hash-Funktion zwar so kollisionssicher wie möglich gemacht werden, aber ihre Rechenkomplexität wird der zu erfüllenden Aufgabe nicht gerecht. Betrachten wir zwei extreme Beispiele. Beispiel 1, die schnellstmögliche Hash-Funktion:
Es wird immer dieselbe Zahl zurückgegeben. Wenn unser Wörterbuch nur ein einziges Wort speichert, dann reicht seine Arbeit aus, denn dieses Wort befindet sich bei Index 0. Wenn wir jedoch 10 Wörter haben, dann befinden sich alle zehn Wörter bei Index 0 (vergessen Sie nicht, dass wir ein Array von Arrays haben).
Für das zweite Beispiel wenden wir uns einer umkehrbaren Verschlüsselung zu, z. B. auf der Grundlage eines Feistel-Netzwerks mit einer Anzahl von Runden N. Es handelt sich dabei nicht um eine Hash-Funktion, und sie ist überhaupt nicht kollisionsgefährdet. D.h. für zwei unterschiedliche Zeichenketten erhalten wir garantiert unterschiedliche Zahlen. Die Länge der erhaltenen Zahlen ist gleich der Länge der Zeichenkette. Wenn also die Zeichenkette 1000 Zeichen lang ist, erhalten wir ein Array uchar mit der Größe 1000. Wenn wir diese Zeichenfolge in einem Wörterbuch mit drei Elementen speichern müssen, wäre es dann nicht seltsam, einen so komplexen Code zu berechnen, um ein Wort mit nur drei Elementen zu finden?
Daher sollten wir immer nach einem goldenen Mittelweg suchen (wie von fxsaber zu Recht hervorgehoben): Wir brauchen eine Funktion, die schnell Hashes berechnet und normalerweise keine Kollisionen verursacht. Schätzen wir die Wahrscheinlichkeit von Kollisionen für unsere vorherige Hash-Funktion:
Das Alphabet besteht aus 26 Zeichen. Nehmen wir an, dass die Anzahl der Wörter, die mit dem Symbol "a" beginnen, gleich der Anzahl der Wörter ist, die mit irgendeinem anderen Symbol beginnen. Wenn unser Wörterbuch also 988 Wörter enthält, beginnen 38 davon mit a, 38 mit b, 38 mit c, ... 38 für den Buchstaben w und 38 für den Buchstaben - z. Die Wahrscheinlichkeit eines Zusammenstoßes wäre in jedem Fall 1/26 oder 3,8461%. Wenn wir 988 Wörter haben, erhalten wir 988*3,8461 = 37,999 Wörter pro Index.
Es ist klar, dass es umso schwieriger ist, ein bestimmtes Wort zu finden, je mehr Wörter es für ein und denselben Buchstaben gibt. In unserem Fall müssen wir nicht nur den Index des ersten Buchstabens berechnen, sondern auch nach allen Wörtern suchen, die mit demselben Buchstaben beginnen. Um dies zu vermeiden, können wir die Hash-Funktion komplizierter gestalten:
Das heißt, wir nehmen die ersten beiden Buchstaben des Wortes. Dann sind die möglichen Kombinationen nicht 26, sondern 26^2 = 676. Es ist anzumerken, dass die Komplexität der zweiten Variante der Hashfunktion linear, d. h. um die Hälfte, gestiegen ist, während die Kollisionssicherheit nichtlinear, d. h. um ein Quadrat, zugenommen hat.
Bei der zweiten Variante käme im Durchschnitt eine Kollision auf 676 Wörter. In unserem Fall würde es bei 988 Wörtern 988/676 = 1,4615 Kollisionen pro Index geben. Das bedeutet, dass jeder Index im Durchschnitt entweder ein Wort oder 2 Wörter enthält. Im Durchschnitt gibt es also gar keine Kollisionen (ein Vergleich), oder sie sind sehr kurz (zwei Vergleiche).
Wenn das Verhältnis zwischen der Größe des Wörterbuchs und der Anzahl der Hash-Funktionen nahe bei 1,0000000 liegt, ist im Durchschnitt keine Brute-Force-Methode erforderlich, da jedes Element von selbst an seinem eigenen Index gefunden wird. Wenn eine Hash-Funktion einen sehr großen Wertebereich liefert, wird das Verhältnis zwischen der Größe des Wörterbuchs und den möglichen Kombinationen der Hash-Funktion immer kleiner als 1,0 sein. Wenn zum Beispiel eine Hash-Funktion 2^32 Kombinationen erzeugt, dann gilt für jede Größe N kleiner als 2^32 das Verhältnis N/2^32 < 1,0. Wenn N sehr klein ist, normalisieren wir einfach die von der Hash-Funktion erhaltene Zahl, so dass sie immer im Grenzwert von N liegt:
int index = GetHashCode(word)%ArraySize(m_array);
Wenn die Hash-Funktion gleichmäßig Ergebnisse erzeugt, erhalten wir im Durchschnitt ein Verhältnis von 1,000, d.h. es gibt nur ein Wort in einem Array-Index. Ein Wörterbuch ist also ein Spezialfall eines Arrays mit einem Schlüssel anstelle eines Indexes.
Die Größe des Arrays kann leicht an die Größe des Wörterbuchs angepasst werden.
Ich berücksichtige keine unendlichen Varianten.
Das Problem ist, dass der Umfang des Wörterbuchs oft unbekannt ist. Ein einfaches Beispiel: Nehmen wir an, wir haben einen Expert Advisor, der Handel treibt. Es verfolgt die durchgeführten Geschäfte. Sobald ein Handel in der Historie erscheint, müssen wir diesen Handel mit der Medjik des EAs verbinden. Hierfür ist es logisch, das Wörterbuch zu verwenden. Dabei wird die Handelsnummer als Schlüssel (eindeutiger Bezeichner) und die magische Zahl des Expert Advisors als Wert verwendet. Das Problem ist, dass wir beim Start des EA nicht im Voraus bestimmen können, ob wir 100, 1000 oder gar keine Trades haben werden. Egal, wie viel Speicher Sie im Voraus zuweisen, es wird entweder zu wenig oder zu viel sein.
Das ist das Problem: Der Umfang des Wörterbuchs ist oft unbekannt. Ein einfaches Beispiel: Nehmen wir an, wir haben einen Berater, der handelt. Sie verfolgt die ausgeführten Geschäfte. Wenn ein Handel in der Historie erscheint, müssen wir diesen Handel mit dem Medjack des Expert Advisors verbinden. Hierfür ist es logisch, das Wörterbuch zu verwenden. Dabei wird die Handelsnummer als Schlüssel (eindeutiger Bezeichner) und die magische Zahl des Expert Advisors als Wert verwendet. Das Problem ist, dass wir beim Start des EA nicht im Voraus bestimmen können, ob wir 100, 1000 oder gar keine Trades haben werden. Egal, wie viel Speicher Sie vorher zuweisen, es wird immer entweder zu wenig oder zu viel sein.
Natürlich gibt es unterschiedliche Aufgaben.
Ich habe eine Aufgabe gelöst, bei der ich ein praktisches Wörterbuch für eine menschliche Sprache erstellen musste. Die Größe meines Arrays ist nicht exakt, aber wo ist das Problem, wenn ich es an die Anzahl der Wörter einer bestimmten Sprache anpasse? Er kann dort problemlos untergebracht werden.
Zum Beispiel eine russische Sprache. Angenommen, sie enthält 10 000 Grundwörter. Alle diese Wörter passen gut in meine Reihe.
Die erste Dimension - 66 Buchstaben (klein und groß), die zweite Dimension - die Anzahl der Buchstaben in dem Wort (bis zu 25 zum Beispiel), die dritte Dimension - entspricht dem ersten Buchstaben und die Anzahl der Buchstaben - 50.
Die ganze Sprache wird passen.
//----------------------------
Ursprünglich war ich dabei, genau dieses Problem zu lösen. Sie ersetzen jetzt das ursprüngliche Problem durch ein anderes und sagen, dass die Lösung nicht gut ist.
Egal, wie viel Speicher Sie vorher zuweisen, es wird entweder zu wenig oder zu viel sein.
Richtig.
Genauso wenig wie es eine Universallösung für alle Aufgaben gibt.
Das stimmt.
Es stimmt auch, dass es keine Einheitslösung gibt, die für alle passt.
Völlig unbestreitbar.
Sprechen Sie leise, Genosse. Niemand ist vor Fehlern gefeit, auch Sie nicht. Seien Sie also so freundlich, die Fehler der anderen in einem sanfteren Ton aufzuzeigen. Ich werde sie jetzt korrigieren.
Wird der Richtige ein Geheimnis bleiben?
Es kann keine prinzipiell richtige Variante von Hash-Tabellen und Hashes geben - alles hängt von spezifischen Zwecken und Anwendungsbedingungen ab.
Das ist wie ein Sandwich zu machen. Vielleicht isst jemand weder Mayonnaise noch Ketchup, oder er ist Veganer....
Aber Ketchup auf den Tisch zu stellen und Brot darauf zu legen - das ist irgendwie klar, dass es nicht....
Grundlagen zum Thema für Faule:
https://www.slideshare.net/mkurnosov/6-32402313
In Wirklichkeit ist es viel komplizierter und wird in der einschlägigen Literatur oder in guten "Algorithmen und Datenstrukturen"-Kursen behandelt.
Kurz gesagt, die Hash-Funktion sollte erstens schnell funktionieren und zweitens ist es nicht nötig, etwas sehr Kompliziertes zu erfinden, da das Auftreten gleicher Werte im Wörterbuch normalerweise mit direkter roher Gewalt gelöst wird. Das Wichtigste ist, dass es nicht zu viele Kollisionen gibt, das ist alles. In Generic ist eine Reihe von Funktionen in der Datei HashFunction.mqh für den Hash von Funktionen von Basistypen zuständig. Um sicherzugehen, dass dort alles einfach ist, sehen wir uns an, wie es organisiert ist:
Die ganzzahligen Typen werden entweder so zurückgegeben, wie sie sind, oder für kurze ganzzahlige Typen werden nicht komplizierte bitweise Umwandlungsoperationen verwendet. Für Typen, die nicht in 32 Ziffern passen, wird ein exklusives oder gefolgt von einer Links-Rechts-Verknüpfung verwendet. Bei Zeichenketten wird ein unkomplizierter Hash auch direkt mit roher Gewalt berechnet. Für reelle Zahlen wird eine Bit-Darstellung mit Union genommen und als Hash verwendet.
Algorithmen vom Typ Wörterbuch werden üblicherweise in zwei Teile unterteilt:
Was ist ein CHashSet? Es handelt sich um eine Sammlung (von Natur aus ein Array), in der jedes Element eindeutig ist. Eine solche Sammlung kann zum Beispiel die Zahlen 2,5,1,7,10,15,1024 enthalten. Aber keine zwei Zahlen können gleich sein. Sie kann auch Zeichenketten, reelle Zahlen und sogar benutzerdefinierte komplexe Typen enthalten (dazu später mehr). Aber die Regel ist dieselbe für jeden Typ - es kann keinen anderen des gleichen Typs im Wörterbuch geben.
Was ist CHashMap? Es handelt sich um eine Sammlung (von Natur aus auch ein Array), bei der jedes Element ein komplexer Schlüssel-Wert-Typ ist:
Sie ist fast genau wie CHashMap strukturiert, erlaubt aber eine Korrespondenz zwischen zwei Mengen, so dass ein Element der Menge 1 einem Element der Menge 2 entspricht. Das ist eine sehr praktische Sache, mit der man sehr effiziente Abfragealgorithmen mit einer durchschnittlichen Ausführungszeit von O(1) schreiben kann.
Später werden wir anhand von Beispielen sehen, wie man eine Art von Korrespondenz aufbauen kann.
Interessanterweise stellt jedes Schlüssel-Wert-Wörterbuch natürlich eine solche nicht-triviale Beziehung her, nämlicheins zu vielen. Wir haben zum Beispiel eine Reihe von historischen Aufträgen und eine Reihe von Geschäften, die auf der Grundlage dieser Aufträge ausgeführt wurden. Jedes Geschäft entspricht nur einem Auftrag, aber ein Auftrag kann mehreren Geschäften entsprechen. Das Wörterbuch einer solchen Beziehung kann als Schlüssel die Nummer des Geschäfts und als Wert die Nummer des Auftrags, mit dem es eröffnet wurde, speichern.