Fonction - Méthode pour trier un tableau de structures. Prix 10$. - page 9

Nouveau commentaire
 
Dmitry Fedoseev:

Pourquoi ? Avons-nous un sujet séparé pour cela ?

Bonne idée ))))

Nous devrions commencer un sujetappelé "Chickenshit... " )))))

 

Tout le monde pensait que le sujet était épuisé, mais bon...

J'ai refait l'algorithme de tri QuickSort pour un tableau de structures. L'essentiel est que l'application directe d'un algorithme de tri de tableau simple pour trier un tableau de structures conduit au mouvement "physique" de grandes quantités de données. Pour éviter cela, j'ai utilisé une table d'index, dans laquelle toutes les permutations sont faites. En parallèle, j'ai utilisé d'autres optimisations de code. Pour conserver l'universalité des différents types, j'ai utilisé un macro wrapper de fxsaber.

Par conséquent, le tri du tableau MqlRates[30000] par 8 champs a pris environ 3600 ms au lieu de 14900 ms. C'est une accélération de plus de 4x. Je n'ai pas vérifié attentivement les résultats du tri, je l'ai laissé tomber sur les bêta-testeurs.

Merci : bien sûr, fxsaber pour le code universel.

 // 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 ce n'est pas évident, accédez à la structure supérieure dans la liste triée : MqlRates first = Rates[ RatesIdx[0] ] ;
123456789
Nouveau commentaire