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

 

Desde el 6 de diciembre de 2017, la entrega estándar de MetaTrader 5 incluye las llamadas clases Genéricas que implementan algoritmos eficientes para el almacenamiento y recuperación de datos. Este hilo se crea para describir estas clases, ejemplos de trabajo con ellas y sugerencias para mejorar su trabajo.

¿Qué son las clases genéricas? Las clases genéricas son clases de plantilla especiales que pueden almacenar tipos de datos personalizados. La identificación del tipo se realiza en tiempo de compilación, lo que se traduce en un alto rendimiento.

¿Por qué genéricas? Por regla general, los programadores noveles sólo están familiarizados con un tipo de colección: un array. Pero hay muchas tareas en las que trabajar con un array es ineficiente. Imaginemos que tenemos un array formado por un millón de identificadores únicos, por ejemplo, mil pedidos. ¿Cómo podemos comprobar si en ese millar de pedidos hay uno con el número N? Si utilizamos una de las clases genéricas, esta tarea se puede realizar casi instantáneamente, por un tiempo constante, que no dependerá del número de elementos entre los que se vaya a realizar la búsqueda. Hay otras tareas en las que el algoritmo correcto de la colección genérica puede ser más rápido que el algoritmo inventado por un programador.

Algoritmos genéricos. A continuación se muestra una tabla de clases genéricas, con una breve descripción de lo que hacen:

ClaseDescripción
CArrayList.Un array, con repartición automática del tamaño. Permite aprovechar un array sin tener que controlar salir de él.
CHashMapUn conjunto clave-valor. Permite la inserción, recuperación y búsqueda eficiente de elementos por su clave. La clave debe ser única. Por ejemplo, CHashMap puede encontrar instantáneamente un pedido con un número especificado cuando el número se utiliza como clave.
CHashSetConjunto de elementos únicos. Permite hacer las mismas cosas que CHashMap, pero no requiere una clave. Los elementos almacenados en esta colección no deben repetirse. También permite buscar, recuperar y añadir un elemento al instante.
CLinkedListUna lista doblemente enlazada. Permite insertar y eliminar elementos fácilmente. Sin embargo, se tarda un tiempo que depende linealmente del número de elementos de la lista en encontrar el elemento deseado.
CQueueCola. Organiza una cola de tipo FIFO
CStackPila. Organiza una cola de tipo LIFO
CRedBlackTreeRedBlackTree. Permite rápidamente (en tiempo logarítmico) insertar elementos, extraerlos y encontrarlos. A diferencia de CHashMap y CHashSet permite implementar eficientemente algoritmos de relación adicionales como más que, menos que, entre, etc.
CSortedMapConjunto ordenado por clave. Almacena valores clave-valor. En este caso, la clave está ordenada.
CSortedSetConjunto ordenado por valor. Almacena un conjunto ordenado de valores.

Más adelante continuaremos y veremos las características de implementación de estas clases.

 
Vasiliy Sokolov:

Imaginemos que tenemos una matriz con un millón de identificadores únicos, por ejemplo, mil pedidos. ¿Cómo podemos comprobar si en este millar de pedidos hay un pedido con el número N? Si utilizamos una de las clases genéricas, esta tarea se puede realizar casi instantáneamente, en un tiempo constante, que no depende del número de elementos que estemos buscando.

No estoy familiarizado con el tema en absoluto. Pero lo destacado suena ilógico.

 

Desgraciadamente, la biblioteca acaba de salir a la luz y todavía está en bruto. Ya he encontrado el primer error en él (destacaré los errores con un marcador):

Error en 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)); }
   ...
  }

El método TryGetMax devuelve el elemento mínimo en lugar del máximo, al igual que TryGetMin

 
fxsaber:

... Pero lo destacado suena ilógico.

¿Por qué?

 
Vasiliy Sokolov:

¿Por qué?

Haciendo hashes, clasificándolos en orden ascendente. Pero la búsqueda estará ahí de todos modos.

 
fxsaber:

No estoy familiarizado con el tema en absoluto. Pero lo destacado suena ilógico.

tiempo medio O(1) peor O(n) y el rendimiento depende en gran medida del hash.
 
fxsaber:

Haciendo hashes ...

Definamos la terminología. Nada es instantáneo. Cualquier operación lleva su tiempo. Cuando digo instantáneo lo estoy simplificando para que me entiendan los programadores novatos. Estrictamente hablando, hay varias clases de complejidad, las principales que trataremos son las siguientes:

  • Complejidad constante cO(1).
  • Logarítmico: cO(log n).
  • Lineal: cO (n).
  • Algoritmos que requieren un tiempo de ejecución no lineal.

He introducido deliberadamente el signo c, como una especie de constante que se produce al calcular el hash y otras manipulaciones técnicas. Pero en este caso, la discusión sobre la optimización de la constantec está fuera del tema de este hilo. Aquí sólo nos interesan las clases genéricas y su aplicación en la práctica.

 
fxsaber:

Haz los hashtags, ordénalos en orden ascendente. Pero habrá una búsqueda de cualquier manera.

Combinador:
Tiempo medio O(1) peor O(n) y el rendimiento depende en gran medida del hash.

+

p.d. Para ilustrar, aquí hay un ejemplo donde este mismo rendimiento caerá a O(n) si no se maneja CHashMap correctamente.

 

Sugiero que se simplifiquen los nombres, que sean más lógicos. Por ejemplo, ¿es CArrayList un Array o una Lista en mql5 una implementación de ambos?

Todo esto da lugar a preguntas y confusión. En mi opinión, deberíamos utilizar stl y no C# o Java. O eliminar C delante entonces, que sea sólo ArrayList.


Si haces nombres normales:

- la legibilidad aumentará muchas veces.

- tendrás tu propio estilo específico de mql5.

- los principiantes podrán navegar inmediatamente por el código (porque el stl está incluido en el estándar)

 
Vasiliy Sokolov:

...

Si puede dar ejemplos, por ejemplo sobre la búsqueda entre miles de ofertas.