Функция - Метод сортировки массива структур. Приз 10$ - страница 9

Новый комментарий
 
Dmitry Fedoseev:

А что? Отдельную тему для этого заводить?

Хорошая мысля ))) 

Надо открыть тему "Тёрки..." )))))

 

Все думали, тема исчерпана, а тут ...

Я переделал алгоритм сортировки QuickSort для массива структур. Суть в том, что прямолинейное применение алгоритма сортировки простого массива к сортировке массива структур приводит к "физическому" перемещению больших объёмов данных. Чтобы избежать этого, я применил индексную таблицу, в которой и производятся все перестановки. Заодно использовал другие оптимизации кода. Чтобы сохранить универсальность для разных типов, использовал макросную обёртку от fxsaber.

В результате сортировка массива MqlRates[30000] по 8 полям заняла примерно 3600 мс вместо 14900 мс. То есть ускорение более 4x. Результаты сортировки проверял не тщательно, пусть это ляжет на бета-тестеров.

Благодарности: конечно, fxsaber за универсальный код.

// 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: Если это не очевидно, доступ к верхней в отсортированном списке структуре: MqlRates first = Rates[RatesIdx[0]];
123456789
Новый комментарий