Funktion - Methode zum Sortieren eines Arrays von Strukturen. Preis 10$ - Seite 9

[[Gelöscht]]

Dmitry Fedoseev:

Warum? Haben wir dafür ein eigenes Thema?

Gute Idee ))))

Wir sollten ein Themamit dem Titel "Chickenshit" starten... " )))))

[Edgar Akhmadeev]

Alle dachten, das Thema sei erschöpft, aber dann ...

Ich habe den QuickSort- Sortieralgorithmus für ein Array von Strukturen überarbeitet. Die Quintessenz ist, dass die einfache Anwendung eines einfachen Array-Sortieralgorithmus zum Sortieren eines Arrays von Strukturen zur "physischen" Bewegung großer Datenmengen führt. Um dies zu vermeiden, habe ich eine Indextabelle verwendet, in der alle Permutationen vorgenommen werden. Gleichzeitig habe ich andere Code-Optimierungen verwendet. Um die Universalität für verschiedene Typen zu erhalten, habe ich einen Makro-Wrapper von fxsaber verwendet.

Infolgedessen dauerte das Sortieren des Arrays MqlRates[30000] nach 8 Feldern etwa 3600 ms statt 14900 ms. Das ist eine Beschleunigung von mehr als 4x. Ich habe die Sortierergebnisse nicht genau überprüft, ließ es auf Betatester fallen.

Danke: natürlich fxsaber für den universellen Code.

 // 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: Wenn es nicht offensichtlich ist, Zugriff auf die oberste Struktur in der sortierten Liste: MqlRates first = Rates[ RatesIdx[0] ];