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

 

Seit dem 6. Dezember 2017 enthält die Standardauslieferung von MetaTrader 5 sogenannte Generic-Klassen, die effiziente Algorithmen für die Speicherung und den Abruf von Daten implementieren. Dieser Thread wurde erstellt, um diese Klassen, Beispiele für die Arbeit mit ihnen und Vorschläge zur Verbesserung ihrer Arbeit zu beschreiben.

Was ist generisch? Generische Klassen sind spezielle Vorlagenklassen, die benutzerdefinierte Datentypen speichern können. Die Typidentifizierung erfolgt zur Kompilierzeit, was zu einer hohen Leistung führt.

Warum generisch? Programmieranfänger sind in der Regel nur mit einem einzigen Auflistungstyp vertraut: einem Array. Es gibt jedoch viele Aufgaben, bei denen die Arbeit mit einem Array ineffizient ist. Stellen Sie sich vor, wir haben ein Array, das aus einer Million eindeutiger Bezeichner besteht, zum Beispiel tausend Bestellungen. Wie können wir prüfen, ob es in diesen tausend Bestellungen eine Bestellung mit der Nummer N gibt? Wenn wir eine der generischen Klassen verwenden, kann diese Aufgabe fast augenblicklich durchgeführt werden, und zwar für eine konstante Zeit, die nicht von der Anzahl der Elemente abhängt, unter denen die Suche stattfinden wird. Es gibt andere Aufgaben, bei denen der richtige Algorithmus aus der generischen Sammlung schneller sein kann als der von einem Programmierer erfundene Algorithmus.

Generische Algorithmen. Nachfolgend finden Sie eine Tabelle der generischen Klassen mit einer kurzen Beschreibung ihrer Aufgaben:

KlasseBeschreibung
CArrayList.Ein Array, mit automatischer Größenaufteilung. Ermöglicht die Nutzung eines Arrays, ohne dass man das Verlassen des Arrays kontrollieren muss.
CHashMapEin Schlüssel-Wert-Set. Ermöglicht effizientes Einfügen, Abrufen und Suchen von Elementen 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.
CHashSetEine Menge von eindeutigen Elementen. Ermöglicht die gleichen Funktionen wie CHashMap, erfordert jedoch keinen Schlüssel. Die in dieser Sammlung gespeicherten Elemente dürfen sich nicht wiederholen. Sie ermöglicht auch das sofortige Suchen, Abrufen und Hinzufügen eines Elements.
CLinkedListEine doppelt verknüpfte Liste. Ermöglicht das einfache Einfügen und Löschen von Elementen. Es dauert jedoch linear von der Anzahl der Elemente in der Liste abhängige Zeit, das gewünschte Element zu finden.
CQueueHeap. Organisiert eine Warteschlange vom Typ FIFO
CStackStapel. Organisiert eine Warteschlange vom Typ LIFO
CRedBlackTreeRedBlackTree. Ermöglicht das schnelle (in logarithmischer Zeit) Einfügen, Extrahieren und Suchen von Elementen. Im Gegensatz zu CHashMap und CHashSet ermöglicht es die effiziente Implementierung zusätzlicher Beziehungsalgorithmen wie mehr als, weniger als, zwischen, usw.
CSortedMapNach Schlüssel sortierte Menge. Speichert Schlüssel-Wert-Werte. In diesem Fall ist der Schlüssel sortiert.
CSortedSetEine nach Wert sortierte Menge. Speichert eine geordnete Menge von Werten.

Später werden wir fortfahren und uns die Implementierungsmerkmale dieser Klassen ansehen.

 
Vasiliy Sokolov:

Stellen Sie sich vor, wir haben ein Array mit einer Million eindeutiger Bezeichner, zum Beispiel tausend Bestellungen. Wie können wir überprüfen, ob es in diesen tausend Aufträgen einen Auftrag mit der Nummer N gibt? Wenn wir eine der generischen Klassen verwenden, kann diese Aufgabe fast sofort erledigt werden, in einer konstanten Zeitspanne, die nicht von der Anzahl der gesuchten Elemente ab hängt.

Ich bin mit diesem Thema überhaupt nicht vertraut. Aber das Hervorgehobene klingt unlogisch.

 

Leider wurde die Bibliothek gerade erst freigegeben und ist noch unbearbeitet. Ich habe bereits den ersten Fehler darin gefunden (ich werde die Fehler durch Markierungen hervorheben):

Fehler in CSortedSet:

//+------------------------------------------------------------------+
//| Class CSortedSet<T>.                                             |
//| Usage: Represents a collection of objects that is maintained in  |
//|        sorted order.                                             |
//+------------------------------------------------------------------+
template<typename T>
class CSortedSet: public ISet<T>
  {
   ...
   bool              TryGetMin(T &min)    { return(m_tree.TryGetMin(min)); }
   bool              TryGetMax(T &max)    { return(m_tree.TryGetMin(max)); }
   ...
  }

Die Methode TryGetMax liefert das minimale Element anstelle des maximalen Elements, ebenso wie TryGetMin

 
fxsaber:

... Aber das Hervorgehobene klingt unlogisch.

Warum ist das so?

 
Vasiliy Sokolov:

Warum ist das so?

Erstellen von Hashes, Sortieren in aufsteigender Reihenfolge. Aber es wird auf jeden Fall eine Durchsuchung geben.

 
fxsaber:

Ich bin mit diesem Thema überhaupt nicht vertraut. Aber das Hervorgehobene klingt unlogisch.

durchschnittliche Zeit O(1) schlimmstenfalls O(n) und die Leistung ist stark abhängig vom Hash.
 
fxsaber:

Hashes erstellen ...

Lassen Sie uns die Terminologie definieren. Nichts ist augenblicklich. Jede Operation braucht Zeit. Wenn ich sage " sofort", dann vereinfache ich das so, dass auch Programmieranfänger mich verstehen. Streng genommen gibt es mehrere Klassen von Komplexität, von denen wir uns hauptsächlich mit den folgenden befassen werden:

  • Konstante Komplexität cO(1).
  • Logarithmisch: cO(log n).
  • Linear: cO (n).
  • Algorithmen, die eine nichtlineare Laufzeit erfordern.

Ich habe absichtlich ein c-Zeichen eingeführt - als eine Art Konstante, die bei der Berechnung von Hash und anderen technischen Manipulationen auftritt. Aber in diesem Fall ist die Diskussion über die Optimierung von konstantemc außerhalb des Themas dieses Threads. Wir interessieren uns hier nur für die generischen Klassen und ihre Anwendung in der Praxis.

 
fxsaber:

Erstellen Sie Hashes und sortieren Sie sie in aufsteigender Reihenfolge. Aber es wird so oder so eine Suche geben.

Kombinator:
Durchschnittliche Zeit O(1) schlimmstenfalls O(n) und die Leistung ist stark abhängig vom Hash.

+

p.s. Zur Veranschaulichung hier ein Beispiel, bei dem dieselbe Leistung auf O(n) sinkt, wenn Sie CHashMap nicht korrekt behandeln.

 

Ich schlage vor, die Namen zu vereinfachen - sie logischer zu gestalten. Zum Beispiel ist CArrayList ein Array oder Liste in mql5 eine Implementierung von beiden?

Dies alles führt zu Fragen und Verwirrung. IMHO sollten wir stl und nicht C# oder Java verwenden. Oder entfernen Sie C vor dann, lassen Sie es nur ArrayList sein.


Wenn Sie normale Namen machen:

- wird die Lesbarkeit um ein Vielfaches erhöht.

- werden Sie Ihren eigenen mql5-Stil haben.

- Anfänger können sich sofort im Code zurechtfinden (da stl im Standard enthalten ist)

 
Vasiliy Sokolov:

...

Wenn Sie Beispiele nennen können, zum Beispiel die Suche unter Tausenden von Angeboten.