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

 
//+------------------------------------------------------------------+
//|                                              CompareFunction.mqh |
//|                   Copyright 2016-2017, MetaQuotes Software Corp. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic\Interfaces\IComparable.mqh>
//+------------------------------------------------------------------+
//| Compares two objects and returns a value indicating whether one  |
//| is less than, equal to, or greater than the other.               |
//+------------------------------------------------------------------+
int Compare(const bool x,const bool y)
  {
   if(x>y)
      return(1);
   else if(x<y)
      return(-1);
   else
      return(0);
  }


Die Funktion wird global deklariert. Aus diesem Grund gibt es einen Konflikt mit ihrem Vergleich durch die Nutzer.

'Compare' - function already defined and has body

Um Namenskonflikte zu vermeiden, könnte der Autor alle globalen generischen Hilfsfunktionen zu public-static-methods machen?

 

fxsaber:

Um Namenskonflikte zu vermeiden, könnte der Autor alle globalen generischen Hilfsfunktionen zu public-static-methods machen?

Forum zum Thema Handel, automatisierte Handelssysteme und Strategietests

Compilerfehler: 'operator=' - Struktur hat Objekte und kann nicht kopiert werden

fxsaber 2018.09.10 11:00 2018.09.10 10:00:13 RU
Alexey Navoykov:
Dies ist vorläufig. Wenn Sie die Bibliothek von jemandem einbinden wollen, werden Sie feststellen, dass der Autor genauso "primitiv" schreibt wie Sie und dieselben Namen für Klassen und Funktionen verwendet.

Ich werde sie mit Makros festnageln.

Was ist mit Makros?
 
A100:
Was ist mit Makros?

Ich habe nicht von mir selbst gesprochen.

 

Ich habe alle Seiten der Diskussion gelesen, aber ich verstehe immer noch nicht, wie man es benutzt?

Kann mir jemand einige Beispiele nennen?

 
Vladimir Pastushak:

Ich habe alle Seiten der Diskussion gelesen, aber ich verstehe immer noch nicht, wie man es benutzt?

Kann mir jemand einige Beispiele nennen?

Vergessen Sie es. So wie es jetzt ist, können Sie es nicht verwenden. Verwenden Sie stattdessen das Standard-CObject + CDictionary. Für die meisten Aufgaben ist das ausreichend.

 
Vasiliy Sokolov:


KlasseBeschreibung
CHashMapEin Schlüssel-Wert-Set. Ermöglicht das effiziente Einfügen, Abrufen und Suchen von Objekten anhand ihres Schlüssels. Der Schlüssel muss eindeutig sein. CHashMap kann zum Beispiel sofort eine Bestellung mit einer bestimmten Nummer finden, wobei die Nummer als Schlüssel verwendet wird.

Frage zum Abrufen eines Wertes nach Schlüssel. Im Bibliothekscode sieht diese Methode wie folgt aus

//+------------------------------------------------------------------+
//| Find index of entry with specified key.                          |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
int CHashMap::FindEntry(TKey key)
  {
   if(m_capacity!=NULL)
     {
      //--- get hash code from key
      int hash_code=m_comparer.HashCode(key)&0x7FFFFFFF;
      //--- search pair with specified key
      for(int i=m_buckets[hash_code%m_capacity]; i>=0; i=m_entries[i].next)
         if(m_entries[i].hash_code==hash_code && m_comparer.Equals(m_entries[i].key,key))
            return(i);
     }
   return(-1);
  }

Die ME-Navigationswerkzeuge (ALT+G und CTRL+-) funktionieren in dieser Bibliothek nicht. Daher ist es sehr schwierig, die Logik nachzuvollziehen. Insbesondere habe ich den Anfangswert in der hervorgehobenen Schleife noch nicht herausgefunden. Es besteht jedoch Einigkeit darüber, dass dieser Wert, wenn es eine Geschwindigkeit gibt, viel geringer sein sollte als die Anzahl der Schlüssel.


Bitte erläutern Sie die Idee, welche Geschwindigkeit bei dieser Funktion erreicht wird. Der Overkill ist eindeutig vorhanden. Aber offenbar ist sie aus irgendeinem Grund zu kurz.


SZ Ich bin meinen Debugger Schritt für Schritt durchgegangen. Alles klar bei Beispiel TKey = int: m_bucket[Array[i]] = i. Nur Kollisionen, wenn Array[i] == Array[j] (i != j) sind unklar.

 
fxsaber:

Die Frage ist, wie man den Wert über den Schlüssel erhält. Im Bibliothekscode sieht diese Methode wie folgt aus
Bitte klären Sie die Idee, was diese Funktion schnell macht? Das Überschwingen ist offensichtlich vorhanden. Aber offenbar ist sie aus irgendeinem Grund zu kurz.

Ich habe einmal beschrieben, wieCHashMap funktioniert
Sie müssen nach Einträgen suchen, wahrscheinlich in diesem Thread.

 

Forum zum Thema Handel, automatisierte Handelssysteme und Testen von Handelsstrategien

Generische Klassenbibliothek - Bugs, Beschreibung, Fragen, Besonderheiten der Nutzung und Vorschläge

Sergey Dzyublik, 2017.12.11 13:41

Kurz über die aktuelleCHashMap-Implementierung:

template<typename TKey,typename TValue>
class CHashMap: public IMap<TKey,TValue>
  {
protected:
   int               m_buckets[];                        
   Entry<TKey,TValue>m_entries[];
   int               m_count;
   int               m_free_list;
   int               m_free_count;
   IEqualityComparer<TKey>*m_comparer;
   bool              m_delete_comparer;

     .................................

.................................

}

Zunächst wollen wir herausfinden, wasEntry<TKey,TValue> ist.
Im Wesentlichen ist es ein Knoten wie in CLinkedList, der enthält:

- in den Container Schlüssel und Wert platziert
- zwischengespeicherter Hash-Wert für den Schlüssel - hash_code
- next - "Zeiger" auf den nächstenEintrag<TKey,TValue> mit dem Ziel der Kollisionsauflösung durch eine einfach verbundene Liste


m_entries[] - Array von "Zellen", in denen der hinzugefügte Schlüssel und Wert, Hash_code, next abgelegt werden. Die Größe des Arrays entspricht der Kapazität.
m_count - gibt den Index der ersten unbenutzten Zelle in m_entries an. Der Anfangswert ist 0 und wächst bis zur Kapazität, danach werden alle Felder mit zunehmender Kapazität und Größe neu aufgebaut.
m_buckets[] - Index-Array auf m_entries[]. Der Standardwert ist -1. Die Größe des Arrays entspricht der Kapazität.


Keine Kollision, Hinzufügen eines eindeutigen Wertes zumCHashMap-Container:

  1. Hash nach Schlüssel berechnen, Hash_code ermitteln
  2. Schlüssel, Wert, Hash_code in m_entries[] nach Index m_count eintragen. (next = -1, da das Beispiel keine Kollisionen aufweist)
  3. In m_buckets[] durch hash_code % (ArraySize(m_buckets)) den Indexwert des soeben hinzugefügten Elements in m_entries[] eintragen (dies ist m_count).
  4. m_count um +1 erhöhen

Ohne Kollisionen, Wert nach Schlüssel imCHashMap-Container erhalten:

  1. Hash aus Schlüssel berechnen, Hash_code erhalten
  2. Von m_buckets[], durch hash_code % (ArraySize(m_buckets)) den Wert erhalten, der ein Index des Arrays m_entries[] ist
  3. Verwenden Sie den erhaltenen Index m_buckets[hash_code % (ArraySize(m_buckets))], um unseren Wert aus dem Array m_entries[] zu erhalten.

Kollisionsauflösung:

Bei unterschiedlichen Schlüsseln kann es vorkommen, dass hash_code_key_1 % (ArraySize(m_buckets)) gleich hash_code_key_2 % (ArraySize(m_buckets)) ist. Dies nennt man eine Kollision.
Alle Elemente mit Kollision, die zu m_entries[] hinzugefügt werden, werden durch die einbindige Liste mit next verknüpft (siehe StrukturEntry<TKey,TValue>)
Und m_buckets[] zeigt immer auf den Index des ersten Kopfelements in dieser Kollisionsliste.
Wir erhalten nicht eine große Liste mit Kollisionen, sondern viele kleine Listen.


Kollision, Wert nach Schlüssel imCHashMap-Container erhalten:

  1. Auf dem Schlüssel berechnen wir den Hash, erhalten hash_code
  2. Mit dem Index hash_code % (ArraySize(m_buckets)) den Wert aus dem Array m_entries[] holen
  3. Wir können sehen, dass der Wert von next nicht gleich -1 ist, was bedeutet, dass es eine Kollision gibt
  4. Die aus den Elementen von m_entries[] bestehende Liste mit einem Eintrag durchgehen und den gesuchten Wert und den gespeicherten Schlüssel auf Gleichheit vergleichen


Entfernen eines Wertes aus demCHashMap-Container:

- Beim Löschen einer Zelle in m_entries[] wird keine Löschung vorgenommen; die Zelle wird als frei markiert und hash_code = -1.
- freie Zellen bilden ihre eigene Liste von freien Zellen (unter Verwendung der gleichen nächsten von Entry<TKey,TValue>),m_free_list
-
freie Zellen werden zuerst verwendet, um neue Werte zum Container hinzuzufügen.
-m_free_count wird verwendet, um die aktuelle Anzahl der freien Zellen zu kontrollieren


Neuaufbau der Hash-Tabelle (Prozess der Kapazitätssteigerung) :

- nur dann wiederherstellen, wenn die Kapazität zu 100 % gefüllt ist.
- Die nächste Kapazitätsgröße wird aus der Liste genommen:

const static int  CPrimeGenerator::s_primes[]=
  {
   3,7,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,
   1103,1327,1597,1931,2333,2801,3371,4049,4861,5839,7013,8419,10103,12143,14591,
   17519,21023,25229,30293,36353,43627,52361,62851,75431,90523,108631,130363,156437,
   187751,225307,270371,324449,389357,467237,560689,672827,807403,968897,1162687,1395263,
   1674319,2009191,2411033,2893249,3471899,4166287,4999559,5999471,7199369
  };

- Die Arrays m_entries[] und m_buckets[] werden inkrementiert.
- m_buckets[] wird auf der Grundlage der Daten aus m_entries[] (zwischengespeicherter Hash-Wert für den Schlüssel - hash_code) geleert und wieder vollständig aufgefüllt


Beschriebenes Verhalten vom2017.12.11
Aktuell, kann einige Details/Koeffizienten hinzugefügt/geändert haben.

 
Sergey Dzyublik:

Ich habe schon einmal die Funktionsweise vonCHashMap zerlegt und beschrieben
Sie müssen nach Einträgen suchen, wahrscheinlich in diesem Thread.

Ich habe es gefunden auf

Forum zum Thema Handel, automatisierte Handelssysteme und Strategietests

Generische Klassenbibliothek - Fehler, Beschreibungen, Fragen, Besonderheiten der Nutzung und Vorschläge

Sergey Dzyublik, 2017.12.07 14:21


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 liegen.
Wir stellen jedes Tagebuch in das 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.

Das Lösen 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 - ich empfehle einen Kurs von MailRu auf youtube über Algorithmen und Datenstrukturen.

Forum zum Thema Handel, automatisierte Handelssysteme und Testen von Handelsstrategien

Generische Klassenbibliothek - Fehler, Beschreibung, Fragen, Besonderheiten der Verwendung und Vorschläge

Sergey Dzyublik, 2017.12.08 14:40

Die Grundlagen zu diesem Thema sind etwas 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.


Danke, die Fehlersuche hat geholfen. Für Kollisionen gibt es kleine Listen. Ich habe das Thema durchgelesen und war entsetzt. Es stellt sich heraus, dass es zum Thema gehörte...

 
Sergey Dzyublik:
Beschriebenes Verhalten vom2017.12.11

Ab sofort können einige Details/Koeffizienten hinzugefügt/geändert werden.

Herzlichen Dank! Ihre Beschreibung war sehr hilfreich.