Função - Método para ordenar uma série de estruturas. Prêmio 10$ - página 9

Novo comentário
 
Dmitry Fedoseev:

Por quê? Temos um tópico separado para isso?

Boa idéia ))))

Deveríamos começar um tópicochamado "Frango de merda... " )))))

 

Todos acharam que o tópico estava esgotado, mas então...

Eu refiz o algoritmo de classificação QuickSort para uma matriz de estruturas. A linha inferior é que a aplicação direta de um algoritmo de classificação de matriz simples para classificar uma matriz de estruturas leva ao movimento "físico" de grandes quantidades de dados. Para evitar isso, usei uma tabela de índice, na qual todas as permutações são feitas. Ao mesmo tempo, usei outras otimizações de código. Para manter a universalidade para diferentes tipos, usei um wrapper de macro do fxsaber.

Como resultado, classificar a matriz MqlRates[30000] por 8 campos levou aproximadamente 3600 ms em vez de 14900 ms. Isso é uma aceleração de mais de 4x. Eu não verifiquei os resultados da classificação com cuidado, deixei cair nos testadores beta.

Obrigado: claro, fxsaber pelo 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: Se não for óbvio, acesse a estrutura superior na lista ordenada: MqlRates first = Rates[ RatesIdx[0] ];
123456789
Novo comentário