Biblioteca de clases genéricas - errores, descripción, preguntas, características de uso y sugerencias - página 18

Nuevo comentario
 

Ejecuta esto

#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)));
}


y conseguí esto.

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


CArrayList es más rápido que la variante hash. Me metí en las tripas de CArrayList, y hay esto

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

Ahora me siento engañado. CArrayList resultó ser una envoltura para un array habitual. Pensaba que era una lista normal con punteros Prev/Next, pero se parece a esto

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:
Además de los algoritmos de estructura en sí, también existe el problema de elegir el contenedor adecuado en función de las características específicas de la tarea.
 
Combinador:
Aparte de los algoritmos de trabajo con estructuras en sí, también está el problema de elegir el contenedor adecuado en función de las particularidades de la tarea.

Así que la interfaz puede ser la misma para diferentes implementaciones. Alguna decepción, no de la interfaz, sino de la implementación específica: el array. Comparado con el hachís, es el cielo y la tierra.

 
fxsaber:

Ahora me siento engañado. CArrayList resultó ser una envoltura para un array normal. Pensé que era una lista normal con punteros Prev/Next, pero aquí está


Foro sobre comercio, sistemas de comercio automatizados y pruebas de estrategias

Algoritmos, métodos de solución, comparación de resultados

Sergey Dzyublik, 2017.12.10 20:52


Qué clase de DBMS, qué le dices a un hombre que no sabe nada deestructuras de datos.
Si no existe el concepto de ArrayList (vector de C++), de qué podemos hablar aquí.....


Es más su falta de atención aquí...
Leer toda la lista disponible -https://www.mql5.com/ru/docs/standardlibrary/generic

CArrayList es un análogo de std::vector de C++
CLinkedList es probablemente un análogo de std::list de C++

 
fxsaber:

Ejecuta esto

y conseguí esto.

CArrayList es más rápido que la variante hash. Me metí en las tripas de CArrayList, y hay esto

Ahora me siento engañado. CArrayList resultó ser una envoltura para un array habitual. Pensaba que era una lista normal con punteros Prev/Next pero se veía así

Históricamente, la Lista no es una hoja en absoluto - es un array. Así que está bien. Si obtienes una lista en genérico, probablemente se llamará LinkedList o algo así.

 
fxsaber:

Una frustración, no con la interfaz, sino con la implementación específica: el array.

bueno... este contenedor es un array (es decir, un análogo del vector en C++), y el array nativo de mql es muy bueno, por lo que arraylist es más bien una idea de última hora, un poco más conveniente de usar.
 

Foro sobre trading, sistemas de trading automatizados y pruebas de estrategias de trading

Biblioteca de clases genéricas - errores, descripción, preguntas, peculiaridades de uso y sugerencias

Sergey Dzyublik, 2017.12.09 01:12


Hay algunas sugerencias de posibles mejoras:

1) En mi humilde opinión, la implementación contiene una elección no del todo correcta de la capacidad - tanto del tamaño inicial 3 como de los subsiguientes al reconstruir la tabla hash.
Sí, es correcto que se elija un número primo para la uniformidad de la distribución.
Sin embargo, la implementación de CPrimeGenerator no cumple las expectativas y contiene omisiones de números primos.
El objetivo de este "generador" es claro: proporcionar un factor de incremento del orden de 1,2 con la generación automática de números primos.
Sin embargo, ¿no es un coeficiente demasiado pequeño? En C++, para los vectores, el coeficiente suele ser de 1,5-2,0, dependiendo de la biblioteca (ya que afecta mucho a la complejidad media de la operación).
La salida podría ser un coeficiente constante seguido del redondeo del número a primo mediante una búsqueda binaria de una lista de números primos.
Y un tamaño inicial de 3 es demasiado pequeño, no vivimos en el siglo pasado.

2) Actualmente la tabla hash se reconstruye (Resize) sólo cuando la capacidad está llena al 100% (todas las m_entradas[] están llenas).
Debido a esto, puede haber una cantidad significativa de colisiones para las claves que no están distribuidas de manera muy uniforme.
Como opción, considere la posibilidad de introducir un factor de llenado, que reduciría el 100% en el límite necesario para la reconstrucción de la tabla hash.

1) El factor de crecimiento del volumen (capacidad) no es igual a 1,2, se utiliza el método CPrimeGenerator::ExpandPrime para calcular el nuevo volumen en CHashMap:

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);
  }

En este método, el tamaño antiguo de la colección se multiplica por dos, luego encontramos el número simple más cercano de la parte superior para el valor resultante y lo devolvemos como el nuevo volumen.

Sobre el valor inicial de la capacidad - estoy de acuerdo, es muy pequeño.

Pero por otro lado siempre hay constructores, donde se puede especificar explícitamente la capacidad inicial:

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

Así que no veo mucho sentido a cambiar nada aquí.

2) Añadir un parámetro de factor de llenado ayudaría mucho a evitar colisiones en algunos casos. Lo más probable es que se aplique.

 
Roman Konopelko:

1) El coeficiente de capacidad no es igual a 1,2, para calcular el nuevo volumen en CHashMap, se utiliza el método CPrimeGenerator::ExpandPrime:

En este método, el tamaño de la colección antigua se multiplica por dos, luego para el valor resultante encontramos el más cercano del número primo superior y lo devolvemos como el nuevo volumen.

Sobre el valor inicial de la capacidad - estoy de acuerdo, es muy pequeño.

Pero por otro lado siempre hay constructores, donde se puede especificar explícitamente la capacidad inicial:

Por eso no veo ninguna razón para cambiar algo aquí.

2) Añadir el parámetro del factor de llenado ayudará realmente a evitar colisiones en algunos casos. Lo más probable es que se aplique.

Roman, creo que te has hecho una idea equivocada. Ahora algunas clases ni siquiera contienen los métodos más necesarios. ¿Has intentado alguna vez utilizarlos? Por ejemplo, CRedBlackTree, la implementación clásica de un árbol rojo-negro. Un algoritmo bastante bueno pero sin posibilidad de iteración. ¿Qué quieres decir con eso? Hay muchas otras cosas que puede necesitar pero que nadie se ha molestado en implementar por alguna razón. Lo de GetHashCode es horrible. Lo siento, pero no está al nivel de MQ.

 
Vasiliy Sokolov:

Roman, no creo que estés haciendo lo correcto. Ahora algunas clases genéricas ni siquiera contienen los métodos más necesarios. ¿Has intentado utilizarlas? Por ejemplo, CRedBlackTree, la implementación clásica de un árbol rojo-negro. Un algoritmo bastante bueno pero sin posibilidad de iteración. ¿Qué quieres decir con eso? Hay muchas otras cosas que puede necesitar pero que nadie se ha molestado en implementar por alguna razón. Lo de GetHashCode es horrible. Lo siento, pero este no es el nivel de MQ.

Soy muy consciente de la necesidad de los iteradores para todas las colecciones de plantillas de la biblioteca Genric, pero sin la posibilidad de crear clases anidadas y la herencia múltiple de las interfaces, no se pueden implementar correctamente.

Me gustaría escuchar comentarios más específicos sobre GetHashCode.

 
Roman Konopelko:

...

En cuanto a GetHashCode, me gustaría escuchar comentarios más específicos.

Problema

Obviamente, GetHashCode no puede implementarse correctamente en un entorno MQL5 personalizado. Esto se debe a que no se puede acceder a todos los objetos. Y mientras la implementación funciona bien para miembros primitivos como double int, para objetos complejos (clases, estructuras e incluso enumeraciones) el hash se calcula por nombre. Si tenemos miles de CObjects o incluso ENUM_something_that, entonces CHashMap y CHashSet degenerarán en LinkedList:

#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) ? " присутствует " : " отсутствует ";
      //...
   }
}

No podemos evitarlo porque lo único que tenemos a nivel de usuario es el nombre del objeto:

//+------------------------------------------------------------------+
//| 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));
     }
  }

Por lo tanto, los hashes de todos los objetos de tipos complejos son iguales entre sí y este código de búsqueda implica aquí una enumeración completa del array:

//+------------------------------------------------------------------+
//| 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);
  }

De hecho, esto es tan crítico que anula el objetivo de utilizar todos los genéricos en la raíz. La cuestión es que en la mayoría de los casos es necesario asociar o almacenar objetos complejos: enumeraciones, estructuras o clases. Si necesita operar sólo con tipos simples, puede hacerlo con algo más sencillo.


Solución

Obviamente, MQL5 es un lenguaje de programación personalizado de tipo seguro que se ejecuta en una máquina virtual interna. Algo así como la red. Esto significa que el acceso necesario a los objetos sigue existiendo, pero a un nivel más de sistema. Por lo tanto,quizás escribir la función del sistema GetHashCode con el siguiente prototipo:

int GetHashCode(void sample);

¿Cómo debería funcionar? En primer lugar, debe ser omnívoro y rápido. Te da una distribución uniforme. Por ejemplo:

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

Esta función podría estar ubicada en la sección de funciones del sistema. No veo ninguna otra solución.

s.e. Haré otras sugerencias sobre interfaces, herencia múltiple y otras cosas del legado de C++ un poco más tarde.
1...111213141516171819202122232425...37
Nuevo comentario
Razón de la queja: