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

Neuer Kommentar
 

Dies ausführen

#include <Generic\ArrayList.mqh>
#include <Generic\HashMap.mqh>

CHashMap<int, int> MagicsByDeals;

#define  AMOUNT 1000000

template <typename T>
int Test( T &Object )
{
  int Res = 0;
  
  for(int i = 0; i < AMOUNT; i++)
  {
    int Tmp = 0;
    
    if (Object.TryGetValue(i, Tmp))    
      Res += Tmp;
  }
  
  return(Res);
}

#define  BENCH(A)                                                              \
{                                                                             \
  const ulong StartTime = GetMicrosecondCount();                              \
  A;                                                                          \
  Print("Time[" + #A + "] = " + (string)(GetMicrosecondCount() - StartTime)); \
} 

void OnStart()
{   
  CArrayList<int> CollectionList;
  CHashMap<int, int> CollectionHash;
  
  for(int i = 0; i < AMOUNT; i++)
  {      
    CollectionHash.Add(i, i);
    CollectionList.Add(i);
  }
  
  BENCH(Print(Test(CollectionList)));
  BENCH(Print(Test(CollectionHash)));
}


und erhielt dies.

1783293664
Time[Print(Test(CollectionList))] = 24819
1783293664
Time[Print(Test(CollectionHash))] = 91270


CArrayList ist schneller als die Hash-Variante. Ich bin in die Eingeweide von CArrayList eingedrungen, und dort gibt es folgendes

template<typename T>
class CArrayList: public IList<T>
  {
protected:
   T                 m_items[];
   int               m_size;

Ich fühle mich jetzt betrogen. CArrayList erwies sich als Wrapper für ein gewöhnliches Array. Ich dachte, es sei eine normale Liste mit Prev/Next-Zeigern, aber sie sieht so aus

template<typename T>
bool CArrayList::TryGetValue(const int index,T &value)
  {
//--- check index
   if((uint)index<(uint)m_size)
     {
      //--- get value by index
      value=m_items[index];
      return(true);
     }
   return(false);
  }
 
fxsaber:
Neben den eigentlichen Algorithmen für die Arbeit mit Strukturen stellt sich das Problem der Auswahl des richtigen Containers je nach den Besonderheiten der Aufgabe.
 
Kombinator:
Abgesehen von den Algorithmen, die bei der Arbeit mit Strukturen zum Einsatz kommen, stellt sich auch das Problem der Auswahl des richtigen Containers je nach den Besonderheiten der Aufgabe.

Die Schnittstelle kann also bei verschiedenen Implementierungen dieselbe sein. Eine Enttäuschung, nicht von der Schnittstelle, sondern von der spezifischen Implementierung - dem Array. Verglichen mit dem Haschisch ist das der Himmel auf Erden.

 
fxsaber:

Ich fühle mich jetzt betrogen. CArrayList erwies sich als Wrapper für ein normales Array. Ich dachte, es handele sich um eine normale Liste mit Prev/Next-Zeigern, aber hier ist sie


Forum zum Thema Handel, automatisierte Handelssysteme und Strategietests

Algorithmen, Lösungsmethoden, Leistungsvergleich

Sergey Dzyublik, 2017.12.10 20:52


Was für ein DBMS, sagen Sie zu einem Mann, der nichts überDatenstrukturen weiß.
Wenn es kein Konzept von ArrayList (Vektor aus C++) gibt, worüber können wir dann hier sprechen.....


Es geht eher um Ihre Unaufmerksamkeit...
Alle verfügbaren Listen lesen -https://www.mql5.com/ru/docs/standardlibrary/generic

CArrayList ist ein Analogon zu std::vector aus C++
CLinkedList ist höchstwahrscheinlich ein Analogon zu std::list aus C++

 
fxsaber:

Dies ausführen

und erhielt dies.

CArrayList ist schneller als die Hash-Variante. Ich bin in die Eingeweide von CArrayList eingedrungen, und dort gibt es folgendes

Ich fühle mich jetzt betrogen. CArrayList erwies sich als Wrapper für ein gewöhnliches Array. Ich dachte, es sei eine normale Liste mit Prev/Next-Zeigern, aber sie sah so aus

Historisch gesehen ist List gar kein Blatt, sondern ein Array. Es ist also alles in Ordnung. Wenn Sie eine Liste im generischen Format erhalten, wird sie wahrscheinlich LinkedList oder so ähnlich heißen.

 
fxsaber:

Eine gewisse Frustration, nicht mit der Schnittstelle, sondern mit der spezifischen Implementierung - dem Array.

Nun... dieser Container ist ein Array (d.h. ein Analogon des Vektors in C++), und natives Mql-Array ist sehr gut, also ist arraylist eher ein nachträglicher Einfall, ein bisschen bequemer zu verwenden.
 

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.09 01:12


Es gibt einige Vorschläge für mögliche Verbesserungen:

1) Meiner bescheidenen Meinung nach enthält die Implementierung eine nicht ganz korrekte Wahl der Kapazität - sowohl der anfänglichen Größe 3 als auch der nachfolgenden beim Wiederaufbau der Hashtabelle.
Ja, es ist richtig, dass für eine gleichmäßige Verteilung eine Primzahl gewählt werden sollte.
Die Implementierung von CPrimeGenerator entspricht jedoch nicht den Erwartungen und enthält Auslassungen von Primzahlen.
Der Zweck eines solchen "Generators" ist klar: Er soll einen Steigerungsfaktor in der Größenordnung von 1,2 mit automatischer Generierung von Primzahlen liefern.
Aber ist dieser Koeffizient nicht zu klein? In C++ für Vektoren beträgt der Koeffizient normalerweise 1,5-2,0, je nach Bibliothek (da er die durchschnittliche Komplexität der Operation stark beeinflusst).
Der Ausweg könnte ein konstanter Koeffizient sein, gefolgt von einer Rundung der Zahl auf eine Primzahl über eine binäre Suche in einer Liste von Primzahlen.
Und eine Anfangsgröße von 3 ist zu klein, wir leben nicht im letzten Jahrhundert.

2) Derzeit wird die Hash-Tabelle nur dann neu aufgebaut (Resize), wenn die Kapazität zu 100% voll ist (alle m_entries[] sind gefüllt).
Aus diesem Grund kann es bei nicht sehr gleichmäßig verteilten Schlüsseln zu einer erheblichen Anzahl von Kollisionen kommen.
Als Option kann die Einführung eines Füllfaktors in Betracht gezogen werden, der 100 % um den für den Wiederaufbau der Hash-Tabelle erforderlichen Grenzwert reduziert.

1) Der Volumenwachstumsfaktor (Kapazität) ist nicht gleich 1,2, die Methode CPrimeGenerator::ExpandPrime wird zur Berechnung des neuen Volumens in CHashMap verwendet:

int CPrimeGenerator::ExpandPrime(const int old_size)
  {
   int new_size=2*old_size;
   if((uint)new_size>INT_MAX && INT_MAX>old_size)
      return INT_MAX;
   else
      return GetPrime(new_size);
  }

Bei dieser Methode wird die alte Sammlungsgröße mit zwei multipliziert, dann wird für den resultierenden Wert die nächstgelegene von der obersten Primzahl gefunden und als neues Volumen zurückgegeben.

Was den Anfangswert der Kapazität betrifft, so stimme ich zu, dass er sehr gering ist.

Andererseits gibt es immer Konstruktoren, bei denen man die Anfangskapazität explizit angeben kann:

class CHashMap: public IMap<TKey,TValue>
  {
public:
                     CHashMap(const int capacity);
                     CHashMap(const int capacity,IEqualityComparer<TKey>*comparer);
  }

Ich sehe also nicht viel Sinn darin, hier etwas zu ändern.

2) Das Hinzufügen eines Füllfaktors würde in einigen Fällen wirklich helfen, Kollisionen zu vermeiden. Am wahrscheinlichsten ist, dass sie umgesetzt werden.

 
Roman Konopelko:

1) Der Kapazitätskoeffizient ist ungleich 1,2, zur Berechnung des neuen Volumens in CHashMap wird die Methode CPrimeGenerator::ExpandPrime verwendet:

Bei dieser Methode wird die alte Sammlungsgröße mit zwei multipliziert, dann wird für den resultierenden Wert die nächstgelegene von der obersten Primzahl gefunden und als neues Volumen zurückgegeben.

Was den Anfangswert der Kapazität betrifft, so stimme ich zu, dass er sehr gering ist.

Andererseits gibt es immer Konstruktoren, bei denen man die Anfangskapazität explizit angeben kann:

Deshalb sehe ich auch keinen Grund, hier etwas zu ändern.

2) Die Hinzufügung des Parameters Füllfaktor wird in einigen Fällen wirklich helfen, Kollisionen zu vermeiden. Höchstwahrscheinlich wird sie umgesetzt werden.

Roman, ich glaube, Sie haben da einen falschen Eindruck gewonnen. Nun enthalten einige Klassen nicht einmal die notwendigsten Methoden. Haben Sie jemals versucht, sie zu benutzen? Nehmen wir zum Beispiel CRedBlackTree, die klassische Implementierung eines rot-schwarzen Baums. Ziemlich cooler Algorithmus, aber ohne die Möglichkeit der Iteration. Was meinen Sie damit? Es gibt noch viele andere Dinge, die Sie vielleicht brauchen, aber niemand hat sich die Mühe gemacht, sie aus irgendeinem Grund zu implementieren. Das GetHashCode-Zeug ist furchtbar. Tut mir leid, aber das ist nicht auf dem Niveau von MQ!

 
Vasiliy Sokolov:

Roman, ich glaube nicht, dass du hier das Richtige tust. Nun enthalten einige generische Klassen nicht einmal die notwendigsten Methoden. Haben Sie schon einmal versucht, sie zu benutzen? Nehmen Sie zum Beispiel CRedBlackTree - eine klassische Implementierung eines rot-schwarzen Baums. Ziemlich cooler Algorithmus, aber ohne die Möglichkeit der Iteration. Was meinen Sie damit? Es gibt noch viele andere Dinge, die Sie vielleicht brauchen, aber niemand hat sich die Mühe gemacht, sie aus irgendeinem Grund zu implementieren. Das GetHashCode-Zeug ist furchtbar. Entschuldigung, aber das ist nicht das Niveau von MQ!

Ich bin mir der Notwendigkeit von Iteratoren für alle Vorlagensammlungen der Genric-Bibliothek durchaus bewusst, aber ohne die Möglichkeit, verschachtelte Klassen und Mehrfachvererbung von den Schnittstellen zu erstellen, kann man sie nicht richtig implementieren.

Ich würde gerne genauere Kommentare zu GetHashCode hören.

 
Roman Konopelko:

...

Was GetHashCode betrifft, so würde ich gerne genauere Bemerkungen hören.

Problem

Offensichtlich kann GetHashCode in einer benutzerdefinierten MQL5-Umgebung nicht richtig implementiert werden. Dies liegt daran, dass nicht auf alle Objekte zugegriffen werden kann. Und während die Implementierung für primitive Mitglieder wie double int gut funktioniert, wird der Hash für komplexe Objekte (Klassen, Strukturen und sogar Aufzählungen) nach Namen berechnet. Wenn wir Tausende von CObjects oder sogar ENUM_something_that haben, dann werden CHashMap und CHashSet zu LinkedList degenerieren:

#include <Generic\HashSet.mqh>
//+------------------------------------------------------------------+
//| Безобидное перечисление, но может быть класс или структура       |
//+------------------------------------------------------------------+
enum ENUM_NUMBER
{
   NUMBER_FIRTS,  // First
   NUMBER_SECOND, // Second
   NUMBER_THIRD   // Third
};
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
{
   CHashSet<ENUM_NUMBER> set_enum;
   for(int i = 0; i < 3; i++)
      set_enum.Add((ENUM_NUMBER)i);
   //-- Поздравляю, мы выродились в LinkedList.... 
   for(int i = 0; i < 3; i++)
   {
      //-- Здесь дикий оверхед по производительности, который тчательно скрывается...
      string is = set_enum.Contains((ENUM_NUMBER)i) ? " присутствует " : " отсутствует ";
      //...
   }
}

Dies lässt sich nicht vermeiden, da wir auf der Benutzerebene nur den Namen des Objekts kennen:

//+------------------------------------------------------------------+
//| Returns a hashcode for custom object.                            |
//+------------------------------------------------------------------+
template<typename T>
int GetHashCode(T value)
  {
//--- try to convert to equality comparable object  
   IEqualityComparable<T>*equtable=dynamic_cast<IEqualityComparable<T>*>(value);// <-- Здесь будет получено название класса, структуры или перечисление
   if(equtable)
     {
      //--- calculate hash by specied method   
      return equtable.HashCode();
     }
   else
     {
      //--- calculate hash from name of object
      return GetHashCode(typename(value));
     }
  }

Daher sind die Hashes aller Objekte komplexer Typen einander gleich, und dieser Suchcode hier beinhaltet eine vollständige Array-Aufzählung:

//+------------------------------------------------------------------+
//| Determines whether a set contains the specified element.         |
//+------------------------------------------------------------------+
template<typename T>
bool CHashSet::Contains(T item)
  {
//--- check buckets
   if(ArraySize(m_buckets)!=0)
     {
      //--- get hash code for item      
      int hash_code=m_comparer.HashCode(item);
      //--- search item in the slots       
      for(int i=m_buckets[hash_code%ArraySize(m_buckets)]-1; i>=0; i=m_slots[i].next)
         if(m_slots[i].hash_code==hash_code && m_comparer.Equals(m_slots[i].value,item))
            return(true);
     }
   return(false);
  }

Dies ist sogar so wichtig, dass es den Sinn der Verwendung aller Generika an der Wurzel zunichte macht. Der Punkt ist, dass Sie in den meisten Fällen komplexe Objekte assoziieren oder speichern müssen: Aufzählungen, Strukturen oder Klassen. Wenn Sie nur mit einfachen Typen arbeiten müssen, können Sie mit etwas Einfacherem auskommen.


Lösung

Offensichtlich ist MQL5 eine typsichere benutzerdefinierte Programmiersprache, die in einer internen virtuellen Maschine läuft. Etwas wie Net. Das bedeutet, dass der notwendige Zugang zu den Objekten weiterhin besteht, allerdings auf einer höheren Systemebene. Folglich,vielleicht die Systemfunktion GetHashCode schreiben mit dem nächsten Prototyp:

int GetHashCode(void sample);

Wie soll das funktionieren? Erstens sollte er ein Allesfresser und schnell sein. Sie erhalten eine gleichmäßige Verteilung. Zum Beispiel:

int hash = GetHashCode(3);
// hash = 3

hash = GetHashCode(3.14159);
// hash = 2039485

enum EType{E1, E2, E3};
hash = GetHashCode(E2);
// hash = 2

class C1{};
C1* class1 = new C1();
hash = GetHashCode(class1);
//hash = 39203847

struct S1{};
S1 struct1;
hash = GetHashCode(struct1);
//hash = 83928342

Diese Funktion könnte im Bereich der Systemfunktionen zu finden sein. Ich sehe keine anderen Lösungen.

s.e. Ich werde andere Vorschläge über Schnittstellen, Mehrfachvererbung und andere C++-Legacy-Sachen ein wenig später machen.
1...111213141516171819202122232425...38
Neuer Kommentar
Grund der Beschwerde: