Generische Klassenbibliothek - Bugs, Beschreibung, Fragen, Nutzungsmöglichkeiten und Vorschläge - Seite 5

Neuer Kommentar
 
Sergey Dzyublik:

Hashes sind im Durchschnitt O(1), wenn die Größe des Wörterbuchs die Anzahl der erwarteten Elemente zulässt.
Und dann hängt es von Kollisionsbehandlung Implementierungen, kann es durch eine Liste sein, vielleicht mehr subhash....

Mein terminologisches Unwissen erschwert den Einstieg in die Thematik. Ich werde auf Beispiele warten. Ich möchte kurz und bündig sein - Optionsscheine, Zecken und dergleichen.

 
fxsaber:

Mein terminologisches Unwissen erschwert den Einstieg in die Thematik. Ich werde auf Beispiele warten. Ich möchte kurz und bündig sein - Optionsscheine, Zecken und dergleichen.


Haftbefehle kommen nicht in Frage. Ich bin an Geschäften interessiert.

 
fxsaber:

Ich habe es in der Wiki gelesen. Das ist ein Fall, bei dem man die Logik des intuitiven Denkens überhaupt nicht versteht.


365 Tage ist die Grenze für die Größe des Wörterbuchs
die Anzahl der Schüler in der Klasse ist die erwartete Anzahl von Gegenständen in der Sammlung
Das Zusammentreffen von Geburtstagen ist eine Kollision

 
Sergey Dzyublik:

365 Tage sind eine Grenze für die Größe des Wörterbuchs.
die Anzahl der Schüler in der Klasse ist die erwartete Anzahl von Gegenständen in der Sammlung
Das Zusammentreffen von Geburtstagen ist eine Kollision

Danke, diese terminologische Definition ist klarer. Ich verstehe nur nicht, was dieses "Paradoxon" mit dem Thema des Threads zu tun hat?

 
Sergey Dzyublik:

365 Tage ist die Grenze für die Größe des Wörterbuchs
Anzahl der Schüler in der Klasse ist die erwartete Anzahl der Gegenstände in der Sammlung
Das Zusammentreffen von Geburtstagen ist eine Kollision


In diesem Beispiel ist der Hash der Geburtstag des Schülers.
Wir haben einen Schrank mit 365 Fächern, in dem die Tagebücher der Schüler aufbewahrt werden.
Wir stellen jedes Tagebuch in ein Regal, das dem Geburtstag des Schülers entspricht.

Wir brauchen das Tagebuch des Schülers Petrov und wir wissen, wann er geboren wurde.
Anhand des Geburtsdatums in O(1) können wir nun leicht Petrovs Tagebuch sowie das Tagebuch eines jeden anderen Schülers finden.
Die Ausnahme ist, wenn zwei Schüler den gleichen Geburtstag haben - dies wird als Kollision bezeichnet.

Die Lösung einer Kollision besteht darin, die zusätzlichen Informationen zu nutzen, um herauszufinden, welches von zwei oder mehr Journalen wir brauchen.
Bei der Kollisionsauflösung durch eine Liste werden einfach alle Einträge in der Kollisionsliste nacheinander durchgegangen, um eine Übereinstimmung zu finden. Reißt jedes Tagebuch ab und schaut, wem es gehört.
Eine Unterrubrik organisiert eine Hash-Tabelle mit den an der Kollision beteiligten Elementen, jedoch nach einem anderen Kriterium. Zum Beispiel nach der Stunde, in der der Schüler geboren wurde.


Wenn Sie sich für das Thema interessieren, empfehle ich Ihnen einen youtube-Kurs von MailRu über Algorithmen und Datenstrukturen.

 
Sergey Dzyublik:

In diesem Beispiel ist der Hash der Geburtstag des Schülers.
Wir haben einen Schrank mit 365 Fächern, in denen die Tagebücher der Schüler liegen.
Wir stellen jedes Tagebuch in das Regal, das dem Geburtstag des Schülers entspricht.

Wir brauchen das Tagebuch von Petrov und wir wissen, wann er geboren wurde.
Anhand des Geburtsdatums in O(1) können wir nun leicht das Tagebuch von Petrov sowie das eines anderen Studenten finden.
Die Ausnahme ist, wenn zwei Schüler den gleichen Geburtstag haben - dies wird als Kollision bezeichnet.

Die Lösung eines Zusammenstoßes besteht darin, die zusätzlichen Informationen zu nutzen, um herauszufinden, welches von zwei oder mehr Journalen wir brauchen.
Bei der Kollisionsauflösung durch eine Liste werden einfach alle Einträge in der Kollisionsliste nacheinander durchgegangen, um eine Übereinstimmung zu finden. Reißt jedes Tagebuch ab und schaut, wem es gehört.
Eine Unterrubrik organisiert eine Hash-Tabelle mit den an der Kollision beteiligten Elementen, jedoch nach einem anderen Kriterium. Zum Beispiel nach der Stunde, in der ein Schüler geboren wurde.


Wenn Sie sich für das Thema interessieren, empfehle ich einen youtube-Kurs von MailRu über Algorithmen und Datenstrukturen.

So habe ich mir das ursprünglich vorgestellt. Ich verstehe nur die hervorgehobene Stelle nicht. Hash ist kein Index, so können Sie es durch Offset in einem Array von Zeigern zu finden. Trotzdem sollten wir in der Liste suchen. Und dies ist eine binäre Suche mit korrekter Sortierung.

 
fxsaber:

So habe ich es mir von Anfang an vorgestellt. Ich verstehe nur die hervorgehobene Stelle nicht. Hash ist kein Index, so können Sie es durch Offset in einem Array von Zeigern zu finden. Sie müssen allerdings in einer Liste suchen. Und dies ist eine binäre Suche mit korrekter Sortierung.


Hervorgehoben sind verbale Tippfehler)) Und bereits korrigiert.
Der Hash ist ein Index. Sie ist der Größe des Wörterbuchs zugeordnet.

Jedes Regal hat die gleiche Höhe, und anhand der Regalnummer wissen Sie genau, auf welcher Höhe Sie es suchen müssen. O(1)

 

So einfach wie möglich über assoziatives Array #1

Viele Algorithmen, die in Generic vorgestellt werden, basieren auf die eine oder andere Weise auf einem assoziativen Array oder Wörterbuch. Er ist auch einer der beiden am häufigsten verwendeten Algorithmen. Ich glaube, ich liege fast richtig, wenn ich sage, dass 90% aller Programmieraufgaben mit Arrays und Dictionaries abgedeckt werden. Bevor wir uns der Praxis zuwenden, wollen wir die Arbeit des Wörterbuchs so klar und einfach wie möglich beschreiben und dabei bewusst einige Details vereinfachen.

Wir werden das Wörterbuch an einem sehr einfachen Beispiel zeigen: einer regulären Wortliste. Nehmen wir an, wir haben nur ein paar Wörter, die alle mit verschiedenen Buchstaben des Alphabets beginnen:

string words[] = {"apple", "cat", "fog", "dog", "walk", "zero"};

Das englische Alphabet umfasst 26 Zeichen. Erstellen wir ein Array mit Strings, das 26 Elemente umfasst:

string dictionary[26];

Wenn wir uns nun darauf einigen, Wörter in Indizes zu speichern, die ihrem Anfangsbuchstaben entsprechen, erhalten wir ein einfaches Wörterbuch. Wir werden von Grund auf neu indizieren. Das Wort "Apfel" wird in unserem Wörterbuch auf dem Index 0 gespeichert, da das Zeichen "a" der erste Buchstabe des Alphabets ist, "Katze" auf dem Index 1, "Hund" auf dem Index 3, "Nebel" auf dem Index 4, "Spaziergang" auf dem Index 24 und "Null" auf dem letzten Index 25.

Beachten Sie, dass die Indizes 5 bis 23 nicht verwendet werden. Dies ist eine zusätzliche Speicherverschwendung, aber wir können z.B. sofort auf das Wort "walk" zugreifen, weil wir wissen, dass es, wenn es existiert, bei Index 24 steht.

Lassen Sie uns unser erstes leeres Wörterbuch schreiben:

//+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link      "http://www.mql5.com"
#property version   "1.00"
string words[26];

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   return words[index] != NULL;
}
bool Add(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   if(words[index] == NULL)
   {
      words[index] = word;
      return true;
   }
   return false;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   Add("apple");
   if(Contains("apple"))
      printf("Словарь содержит слово apple");
   else
      printf("Словарь не содержит слово apple");
  }
//+------------------------------------------------------------------+

Wenn man das Wort "Apfel" hinzufügt und es dann findet, wird der Suchvorgang zum Zugriff auf dieses Wort sofort ausgeführt. Denn wir kennen im Voraus den Index, mit dem dieses Wort gefunden werden kann. Es kann keine weiteren Indexvarianten geben, so dass es nicht notwendig ist, die gesamte Liste durchzugehen. Dies ist in etwa die Grundlage aller Wörterbücher.

Im folgenden Beispiel werden wir es so verbessern, dass es Wörter speichern kann, die mit demselben Buchstaben beginnen.

 

So einfach wie möglich über assoziatives Array #2

Manchmal kommt es vor, dass verschiedene Wörter mit demselben Buchstaben des Alphabets beginnen. Wenn wir "Apfel" in unser vorheriges Wörterbuch eintragen und dann versuchen, "Anwendung" dort einzutragen, funktioniert das nicht. Der Index 0 wird mit dem Wort Apfel belegt. In diesem Fall spricht man von einer Hash-Funktionskollision. Unsere Hash-Funktion ist sehr einfach - sie gibt die Nummer des ersten Zeichens des Wortes zurück, so dass es bei dieser Funktion sehr häufig zu Kollisionen kommen wird. Um verschiedene Wörter, die mit demselben Buchstaben beginnen, zu speichern, werden wir eine Addition vornehmen: Wir werden die Elemente nicht in einem Array, sondern in einem Array von Arrays speichern. In diesem Fall enthält der Index 0 ein weiteres Array mit zwei Wörtern: "apple" und "application":

//+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link      "http://www.mql5.com"
#property version   "1.00"
#include <Arrays\ArrayObj.mqh>
#include <Arrays\ArrayString.mqh>
CArrayString* WordsArray[26];

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   CArrayString* words = WordsArray[index];
   if(words == NULL)
      return false;
   for(int i = 0; i < words.Total(); i++)
      if(word == words.At(i))
         return true;
   return false;
}
bool Add(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   CArrayString* words;
   if(WordsArray[index] == NULL)
      WordsArray[index] = new CArrayString();
   words = WordsArray[index];
   for(int i = 0; i < words.Total(); i++)
      if(word == words.At(i))
         return false;
   words.Add(word);
   return true;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   //ArrayResize(WordsArray, 26);
   Add("apple");
   Add("application");
   if(Contains("application"))
      printf("Словарь содержит слово application");
   else
      printf("Словарь не содержит слово application");
  }
//+------------------------------------------------------------------+

Jetzt speichert unser Wörterbuch auch Wörter, die mit demselben Buchstaben beginnen. Aber die Kosten für den Zugriff auf Wörter mit demselben Anfangsbuchstaben steigen. Denn jetzt brauchen wir eine vollständige Suche in allen Wörtern, die mit "a" beginnen, um herauszufinden, ob das Wort "Anwendung" im Wörterbuch steht oder nicht. Wenn unsere Hash-Funktion selbst dann unterschiedliche Zahlen erzeugen würde, wenn sich die Wörter um ein Zeichen unterscheiden, dann würde die Wahrscheinlichkeit, Wörter mit denselben Indizes auszuprobieren, gegen Null tendieren, und der Zugriff auf ein beliebiges Element würde gegen o(1). In echten Wörterbüchern ist dies genau das, was passiert, Funktionen, die dort verwendet werden, sind kollisionssicher, so können wir sicher sagen, dass der Zugriff auf die Elemente in diesen Sammlungen ist sehr schnell und fast keine Brute-Force.

 
Vasiliy Sokolov:

Das assoziative Array so einfach wie möglich halten

Viele Algorithmen, die in Generic vorgestellt werden, basieren auf die eine oder andere Weise auf einem assoziativen Array oder Wörterbuch. Es ist auch einer der beiden am häufigsten verwendeten Algorithmen. Ich glaube, ich käme der Wahrheit nahe, wenn ich sagen würde, dass 90 % aller Programmieraufgaben durch Arrays und Dictionaries abgedeckt werden. Bevor wir uns der Praxis zuwenden, wollen wir die Arbeit des Wörterbuchs so klar und einfach wie möglich beschreiben und dabei bewusst einige Details vereinfachen.

Wir werden das Wörterbuch an einem sehr einfachen Beispiel zeigen: einer regulären Wortliste. Nehmen wir an, wir haben nur ein paar Wörter, die alle mit verschiedenen Buchstaben des Alphabets beginnen:

Das englische Alphabet umfasst 26 Zeichen. Erstellen wir ein Array mit Strings, das 26 Elemente umfasst:

Wenn wir uns nun darauf einigen, Wörter in Indizes zu speichern, die ihrem Anfangsbuchstaben entsprechen, erhalten wir ein einfaches Wörterbuch. Wir werden von Grund auf neu indizieren. Das Wort "Apfel" wird in unserem Index 0 gespeichert, weil das "a" der erste Buchstabe des Alphabets ist, "Katze" wird in Index 1 gespeichert, "Hund" in Index 3, "Nebel" in Index 4, "Spaziergang" in Index 24 und "Null" im letzten Index 25.

Beachten Sie, dass die Indizes 5 bis 23 nicht verwendet werden. Dies ist eine zusätzliche Speicherverschwendung, aber wir können z.B. sofort auf das Wort "walk" zugreifen, weil wir wissen, dass es, wenn es existiert, bei Index 24 steht.

Lassen Sie uns unser erstes leeres Wörterbuch schreiben:

Wenn man das Wort "Apfel" hinzufügt und es dann findet, wird der Suchvorgang zum Zugriff auf dieses Wort sofort ausgeführt. Denn wir kennen im Voraus den Index, mit dem dieses Wort gefunden werden kann. Es kann keine weiteren Indexvarianten geben, so dass es nicht notwendig ist, die gesamte Liste zu durchsuchen. Dies ist in etwa die Grundlage aller Wörterbücher.

Im nächsten Beispiel werden wir es so verbessern, dass wir Wörter speichern können, die mit demselben Buchstaben beginnen.

Diese Lösung ist perfekt. Alles ist so einfach wie möglich. Nur Funktionen, Arrays und korrekte Datenorganisation. Das ist es, wovon ich spreche.
123456789101112...38
Neuer Kommentar
Grund der Beschwerde: