功能 - 对一个结构数组进行排序的方法。奖金10元 - 页 9

新评论
 
Dmitry Fedoseev:

为什么？我们是否有一个单独的话题来讨论这个问题？

好主意 ))))

我们应该建立一个名为 "鸡肋"的话题。" )))))

 

所有人都以为话题已经讲完了，但随后……

我为结构数组重新编写了 QuickSort 排序算法。底线是简单的数组排序算法直接应用于对结构数组进行排序会导致大量数据的“物理”移动。为了避免这种情况，我使用了一个索引表，其中进行了所有排列。同时，我使用了其他代码优化。为了保持不同类型的通用性，我使用了 fxsaber 的宏包装器。

因此，按 8 个字段对 MqlRates[30000] 数组进行排序大约需要 3600 毫秒而不是 14900 毫秒。那是超过 4 倍的加速度。我没有仔细检查排序结果，让它落在beta测试者身上。

谢谢：当然，通用代码的 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
新评论