Скачать MetaTrader 5

Сортировка по кастомному условию

Авторизуйтесь или зарегистрируйтесь, чтобы добавить комментарий
lob32371
508
lob32371  

Как реализовать на MQL4++?

 

Мне нужно сортировать массив сигналов по кастомному условию. В С++ за счет указателей на функцию это делается легко.

 

Подскажите, как это простое желание исполнить на MQL4++ без копи-пасты исходников "Быстрой сортировки" для каждого (наперед неизвестного) условия? Снова макрос?

lob32371
508
lob32371  
Использование такого макроса для рекурсивной реализации алгоритма "Быстрой сортировки" невозможно, к сожалению.
Sergey Dzyublik
5114
Sergey Dzyublik  

используйте массив указателей и сортируйте его. 
#include <Arrays\ArrayObj.mqh> 

Быстрая сортировка там реализована но так как элемент для сравнения выбирается не рандомно, а центральный элемент, то можно нарваться на худший случай из возможных.

lob32371
508
lob32371  
ALXIMIKS:

используйте массив указателей и сортируйте его. 
#include <Arrays\ArrayObj.mqh> 

Быстрая сортировка там реализована но так как элемент для сравнения выбирается не рандомно, а центральный элемент, то можно нарваться на худший случай из возможных.

Спасибо, но вы не поняли, что такое кастомное условие сортировки.
Sergey Dzyublik
5114
Sergey Dzyublik  

Спасибо, но вы не поняли как их забивать в 

virtual int       Compare(const CObject *node,const int mode=0) const { return(0);      } 

 mode - это кастомное условие, точнее номер, который вы ему определите и обработаете.

Sergey Dzyublik
5114
Sergey Dzyublik  
Разобрались что к чему? Там немного ООП, которое вы так любите.

А так как документаций нет, то что бы понять что тот или этот метод в реальности делает, надо вскрывать внутренности и разбирать все самому.
lob32371
508
lob32371  
ALXIMIKS:
Разобрались что к чему? Там немного ООП, которое вы так любите.

А так как документаций нет, то что бы понять что тот или этот метод в реальности делает, надо вскрывать внутренности и разбирать все самому.

Вскрыл и даже разобрался, спасибо. Это один из первых методов, что пришел мне в голову. И почти сразу был отметен из-за своей ущербности/кривизны.

Попробую представить решение куда правильнее. Пока только на уровне идеи витает. 

lob32371
508
lob32371  

Сделал симуляцию указателей на функцию. Sort.mqh:

#property strict

class SORT
{
private:
  template <typename T>
  static void Swap( T &Array[], const int i, const int j )
  {
    const T Temp = Array[i];

    Array[i] = Array[j];
    Array[j] = Temp;

    return;
  }

  template<typename T1, typename T2>
  static int Partition( T1 &Array[], const T2 &Compare, const int Start, const int End )
  {
    int Marker = Start;

    for (int i = Start; i <= End; i++)
      if (Compare.Compare(Array[i], Array[End]) <= 0)
      {
        Swap(Array, i, Marker);

        Marker++;
      }

     return(Marker - 1);
  }

  template<typename T1, typename T2>
  static void QuickSort( T1 &Array[], const T2 &Compare, const int Start, const int End )
  {
    if (Start < End)
    {
      const int Pivot = Partition(Array, Compare, Start, End);

      QuickSort(Array, Compare, Start, Pivot - 1);
      QuickSort(Array, Compare, Pivot + 1, End);
    }

    return;
  }

public:
  /* синтаксис почти соответствует MQL-штатной ArraySort:
       void&       array[]                   // массив для сортировки
       void&       Compare                   // условие сортировки (с направлением)
       int         count = WHOLE_ARRAY,      // количество элементов
       int         start = 0,                // начальный индекс
  */
  template<typename T1, typename T2>
  static void Sort( T1 &Array[], const T2 Compare, int Count = WHOLE_ARRAY, const int Start = 0 )
  {
    if (Count == WHOLE_ARRAY)
      Count = ArraySize(Array);

    if (CheckPointer(Compare) != POINTER_INVALID)
      QuickSort(Array, Compare, Start, Start + Count - 1);

    if (CheckPointer(Compare) == POINTER_DYNAMIC)
      delete Compare;

    return;
  }
};

class COMPARE
{
private:
  const int Mode;

protected:
  template <typename T>
  T SetMode( T Value ) const
  {
    if (Mode != MODE_ASCEND)
      Value = -Value;

    return(Value);
  }

public:
  COMPARE( const int iMode = MODE_ASCEND ): Mode(iMode)
  {
  }

  template<typename T>
  T Compare( const T First, const T Second ) const
  {
    return(SetMode(First - Second));
  }
};

Вот так теперь можно делать кастомную сортировку массивов из любых объектов:

#property strict

#include <Sort.mqh>

template <typename T>
void PrintArray( const T &Array[] )
{
  const int Size = ArraySize(Array);
  string Str = "";

  for (int i = 0; i < Size; i++)
    Str = Str + " " + (string)Array[i];

  Print(Str);
}

class CompareByAbs : public COMPARE
{
public:
  template<typename T>
  T Compare( const T First, const T Second ) const
  {
    return(SetMode(
           MathAbs(First) - MathAbs(Second) // условие сортировки
           ));
  }

  CompareByAbs( const int iMode = MODE_ASCEND ) : COMPARE(iMode) // можно не прописывать (для возможности обратной сортировки)
  {
  }
};

void OnStart( void )
{
  int Array[] = {2, -45, 1, -5, 7, 9};

  SORT::Sort(Array, new COMPARE);
  PrintArray(Array); // -45 -5 1 2 7 9


  SORT::Sort(Array, new CompareByAbs(MODE_DESCEND));
  PrintArray(Array); // -45 9 7 -5 2 1

  return;
}
Sergey Dzyublik
5114
Sergey Dzyublik  

1. Там (в стандартной библиотеке) выбирался центральный элемент массива как опорный, у вас еще хуже вариант.
Дает O(n^2) если сортировать отсортированное не в ту сторону. Например (9 8 7 6 5 4 3 2 1    с MODE_ASCEND)

 

2. Используется лишняя рекурсия в  вызове (удар по времени и памяти).

      QuickSort(Array, Compare, Start, Pivot - 1);
      QuickSort(Array, Compare, Pivot + 1, End);

 Оптимальнее зациклить вторую рекурсию

3. Что бы поменять мод сортировки я должен удалить "объект-функтор"  и создать новый

class COMPARE
{
privateconst int Mode; 


Может еще что, особо в код не всматривался - просто пробежался.

П.С. А, точно, как же освобождение памяти от new ?

Комбинатор
16173
Комбинатор  
lob32371:

Сделал симуляцию указателей на функцию. Sort.mqh:

А почему SetMode? Обычно определяют что-то типа оператора "меньше". С возвращаемым булевским значением, чтобы можно было сравнивать не только простые типы. Не у любого объекта есть перегруженный оператор "-". Ну и на работу с массивом объектов тоже проверить бы.

Вобщем похоже на годно, но требует доработки.

lob32371
508
lob32371  
ALXIMIKS:

1. Там (в стандартной библиотеке) выбирался центральный элемент массива как опорный, у вас еще хуже вариант.
Дает O(n^2) если сортировать отсортированное не в ту сторону. Например (9 8 7 6 5 4 3 2 1    с MODE_ASCEND)

 

2. Используется лишняя рекурсия в  вызове (удар по времени и памяти).

 Оптимальнее зациклить вторую рекурсию

Да, не оптимизировал алгоритм самой сортировки. Скиньте сюда, оптимальный с вашей точки зрения, MQL-вариант "быстрой сортировки" для целочисленного массива. Нужно было решить обозначенную в теме проблему. Найденный подход доказал свою робастность.

3. Что бы поменять мод сортировки я должен удалить "объект-функтор"  и создать новый


Может еще что, особо в код не всматривался - просто пробежался.

П.С. А, точно, как же освобождение памяти от new ?

По-моему, гораздо проще (дешево и сердито) написать такой универсальный вызов:

SORT::Sort(Array, new COMPARE);
Чем под каждое условие сортировки городить функцию сортировки. "Объект-функтор" удаляется автоматом.
123
Авторизуйтесь или зарегистрируйтесь, чтобы добавить комментарий