Función - Método para ordenar una matriz de estructuras. Premio 10$ - página 9

[[Eliminado]]

Dmitry Fedoseev:

¿Por qué? ¿Tenemos un tema aparte para eso?

Buena idea ))))

Deberíamos empezar un temallamado "Chickenshit... " )))))

[Edgar Akhmadeev]

Todos pensaron que el tema se había agotado, pero luego...

Rehice el algoritmo de clasificación QuickSort para una matriz de estructuras. La conclusión es que la aplicación directa de un algoritmo de clasificación de matriz simple para clasificar una matriz de estructuras conduce al movimiento "físico" de grandes cantidades de datos. Para evitar esto, utilicé una tabla de índice, en la que se realizan todas las permutaciones. Al mismo tiempo, utilicé otras optimizaciones de código. Para mantener la universalidad de los diferentes tipos, utilicé un contenedor de macros de fxsaber.

Como resultado, ordenar la matriz MqlRates[30000] por 8 campos tomó aproximadamente 3600 ms en lugar de 14900 ms. Eso es una aceleración de más de 4x. No revisé los resultados de la clasificación con cuidado, dejé que recayera en los probadores beta.

Gracias: por supuesto, fxsaber por el código universal.

 // QSort.mq5
#property copyright "(c)2020 Edgar Akhmadeev, fxsaber"
#property link        "https://www.mql5.com/en/users/dali"
#property strict
#property version    "1.00"
// 2020.06.18



#define MAX_SIZE 30000



MqlRates         Rates[];
int              RatesIdx[];



// Сортировка массива структур и указателей на объекты по (под-) полю/методу.
#define ArraySortStruct(T, ARRAY, FIELD)                                         \
{                                                                                \
   class SORT                                                                     \
  {                                                                              \
   private :                                                                       \
     static void Swap( T &Array[], const int i, const int j )                     \
    {                                                                            \
       const T Temp = Array[i];                                                   \
                                                                                 \
      Array[i] = Array[j];                                                       \
      Array[j] = Temp;                                                           \
                                                                                 \
       return ;                                                                    \
    }                                                                            \
                                                                                 \
     static int Partition( T &Array[], const int Start, const int End )           \
    {                                                                            \
       int Marker = Start;                                                        \
                                                                                 \          
       for ( int i = Start; i <= End; i++)                                         \
         if (Array[i]. ##FIELD <= Array[End]. ##FIELD)                               \
        {                                                                        \
          SORT::Swap(Array, i, Marker);                                          \
                                                                                 \
          Marker++;                                                              \
        }                                                                        \
                                                                                 \
       return (Marker - 1 );                                                       \
    }                                                                            \
                                                                                 \
     static void QuickSort( T &Array[], const int Start, const int End )          \
    {                                                                            \
       if (Start < End)                                                           \
      {                                                                          \
         const int Pivot = Partition(Array, Start, End);                          \
                                                                                 \
        SORT::QuickSort(Array, Start, Pivot - 1 );                                \
        SORT::QuickSort(Array, Pivot + 1 , End);                                  \
      }                                                                          \
                                                                                 \
       return ;                                                                    \
    }                                                                            \
                                                                                 \
   public :                                                                        \
     static void Sort( T &Array[], int Count = WHOLE_ARRAY , const int Start = 0 ) \
    {                                                                            \
       if (Count == WHOLE_ARRAY )                                                  \
        Count = :: ArraySize (Array);                                              \
                                                                                 \
      SORT::QuickSort(Array, Start, Start + Count - 1 );                          \
                                                                                 \
       return ;                                                                    \
    }                                                                            \
  };                                                                             \
                                                                                 \
  SORT::Sort(ARRAY);                                                             \
}



#define StructArraySort(T, ARRAY, INDEX, FIELD) {                                               \
         class SORT {                                                                            \
         private :                                                                                \
                 static void                                                                      \
                Swap( int &Index[], const int i, const int j) {                                  \
                         const int idx = Index[i];                                               \
                        Index[i] = Index[j];                                                    \
                        Index[j] = idx;                                                         \
                         return ;                                                                 \
                }                                                                               \
                                                                                                \
                 static int                                                                       \
                Partition(T &Array[], int &Index[], const int Start, const int End) {           \
                         int Marker = Start;                                                     \
                                                                                                \
                         for ( int i = Start; i <= End; ++i)                                      \
                                 if ((i == End) || (Array[i]. ##FIELD <= Array[End]. ##FIELD)) {   \
                                         if (i != Marker)                                        \
                                                SORT::Swap(Index, i, Marker);                   \
                                        ++Marker;                                               \
                                }                                                               \
                                                                                                \
                         return Marker - 1 ;                                                      \
                }                                                                               \
                                                                                                \
                 static void                                                                      \
                QuickSort(T &Array[], int &Index[], const int Start, const int End) {           \
                         const int Pivot = Partition(Array, Index, Start, End);                  \
                         if (Start < Pivot - 1 )                                                  \
                                SORT::QuickSort(Array, Index, Start, Pivot - 1 );                \
                         if (Pivot + 1 < End)                                                    \
                                SORT::QuickSort(Array, Index, Pivot + 1 , End);                  \
                }                                                                               \
                                                                                                \
         public :                                                                                 \
                 static void                                                                      \
                Sort(T &Array[], int &Index[], int Count = WHOLE_ARRAY , const int Start = 0 ) {  \
                         if (Count == WHOLE_ARRAY )                                               \
                                Count = :: ArraySize (Array);                                     \
                                                                                                \
                        SORT::QuickSort(Array, Index, Start, Start + Count - 1 );                \
                }                                                                               \
        };                                                                                      \
                                                                                                \
        SORT::Sort(ARRAY, INDEX);                                                               \
}



#define StructArrayIndex(T, ARRAY, INDEX) {                                                     \
         class IDX {                                                                             \
         public :                                                                                 \
                 static void                                                                      \
                Idx(T &Array[], int &Index[]) {                                                 \
                         int cnt = ArraySize (Array);                                             \
                         ArrayResize (Index, cnt);                                                \
                         for ( int i = cnt - 1 ; i >= 0 ; --i)                                      \
                                Index[i] = i;                                                   \
                }                                                                               \
        };                                                                                      \
                                                                                                \
        IDX::Idx(ARRAY, INDEX);                                                                 \
}



void 
OnStart () {
         int cnt = CopyRates ( _Symbol , PERIOD_M1 , 0 , MAX_SIZE, Rates);
         Print (cnt, " bars copied" );

         uint start = GetTickCount ();
        ArraySortStruct( MqlRates , Rates, open);
        ArraySortStruct( MqlRates , Rates, high);
        ArraySortStruct( MqlRates , Rates, low);
        ArraySortStruct( MqlRates , Rates, close);
        ArraySortStruct( MqlRates , Rates, tick_volume);
        ArraySortStruct( MqlRates , Rates, real_volume);
        ArraySortStruct( MqlRates , Rates, time);
        ArraySortStruct( MqlRates , Rates, spread);
         Print ( "Test orig: " , GetTickCount () - start, " ms" );

        start = GetTickCount ();
        StructArrayIndex( MqlRates , Rates, RatesIdx);
        StructArraySort( MqlRates , Rates, RatesIdx, open);
        StructArraySort( MqlRates , Rates, RatesIdx, high);
        StructArraySort( MqlRates , Rates, RatesIdx, low);
        StructArraySort( MqlRates , Rates, RatesIdx, close);
        StructArraySort( MqlRates , Rates, RatesIdx, tick_volume);
        StructArraySort( MqlRates , Rates, RatesIdx, real_volume);
        StructArraySort( MqlRates , Rates, RatesIdx, time);
        StructArraySort( MqlRates , Rates, RatesIdx, spread);
         Print ( "Test my: " , GetTickCount () - start, " ms" );
}

UPD: si no es obvio, acceda a la estructura superior en la lista ordenada: MqlRates first = Rates[ RatesIdx[0] ];