Библиотеки: Быстрая сортировка.

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

Быстрая сортировка.:

Функции для сортировки массивов. Позволяют сортировать строки и структуры по любому условию.

Автор: Koldun Zloy

 
Automated-Trading:

Быстрая сортировка.:

Автор: Koldun Zloy

Хорошая сортировка, быстрая, жаль не подходит для сортировки тиков :(

При сортировке переставляет местами тики с одинаковым временем.


Слева до сортировки, справа после сортировки. 

Сортировал и просто по времени и по времени тика в миллисекундах, результат одинаковый.

 
Aleksandr Slavskii #:

Хорошая сортировка, быстрая, жаль не подходит для сортировки тиков :(

При сортировке переставляет местами тики с одинаковым временем.


Слева до сортировки, справа после сортировки. 

Сортировал и просто по времени и по времени тика в миллисекундах, результат одинаковый.

Спасибо за сообщение.

Такое поведение исправил.

К сожалению, за счёт небольшого снижения скорости.

 
Koldun Zloy #:

Спасибо за сообщение.

Такое поведение исправил.

К сожалению, за счёт небольшого снижения скорости.

Ух ты, как быстро!


А я уже поставил гномью сортировку.

Мне надо сортировка тиков дней за десять, а  учитывая, что тиков с не правильным временем попадается всего штук 10-15 в день, сортируется довольно быстро.

Появится время, сравню кто быстрее)

 
Aleksandr Slavskii #:

Ух ты, как быстро!


А я уже поставил гномью сортировку.

Мне надо сортировка тиков дней за десять, а  учитывая, что тиков с не правильным временем попадается всего штук 10-15 в день, сортируется довольно быстро.

Появится время, сравню кто быстрее)

Ещё ради интереса попробуйте этот метод сортировки. Его результаты меня впечатлили.
 
Nikolai Semko #:
Ещё ради интереса попробуйте этот метод сортировки. Его результаты меня впечатлили.

Спасибо.

Судя по описанию, сортировщик просто зверь какой то)))

Сравню, обязательно сравню (но это не точно).

 
Aleksandr Slavskii #:

Сравню, обязательно сравню (но это не точно).

М-да, сравнивальщик из меня так себе.


Задача: сравнить скорость работы крутых библиотек  ArraySort(), RadixSort(), QuickSort() и функции GnomeSort(), не в гипотетической сортировке рандомных массивов, а в конкретной задаче выравнивания по времени массива структур MqlTick.

Надо сразу отметить, что этот массив может оказаться сразу отсортированным по времени, но иногда бывает стоят не по времени 10-20 тиков на 100000, а то и меньше.

Как отсортировать массив с помощью  ArraySort(), я не знаю :(

Так же я не смог отсортировать с  помощью   RadixSort(), в ООП я не силён, а примеров там нет. Если кто знает как там сортировать массивы структур, напишите.

Зато пример есть в описании библиотеки  QuickSort(), я не уверен, что я правильно его понял и применил, если не правильно, поправьте меня.

Заодно хочу спросить Koldun Zloy , а может вы можете сделать, чтоб сортировка структуры, делалась как то попроще?

Я вот не понимаю, что такое 

typedef bool (*FuncLess)(const MqlTick&, const MqlTick&);

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

Вот это для меня вообще тёмный лес

QuickSort< MqlTick, FuncLess >(arr4, Less);

Может быть можно сделать, как нибудь попроще?

Как нибудь типа:

MqlTick arr[];

QuickSort(arr, arr[0].time_msc);

Указал структуру, которую надо сортировать, вторым аргументом указал элемент структуры по которому осуществляется сортировка  или так нельзя делать? 


Ну ладно, немного отвлёкся от темы.

Итак:

#include <RadixSort.mqh>
#include <QuickSort.mqh>

MqlTick arr1[];
MqlTick arr2[];
MqlTick arr3[];
MqlTick arr4[];
MqlTick ticksArr[];
//+------------------------------------------------------------------+
typedef bool (*FuncLess)(const MqlTick&, const MqlTick&);
//+------------------------------------------------------------------+
void OnStart()
  {
   int result = CopyTicksRange(_Symbol, ticksArr, COPY_TICKS_ALL, (TimeCurrent() - 100 * 24 * 60 * 60) * 1000, TimeCurrent() * 1000);

   if(result > 0)
     {
      Write(ticksArr, "Orig");
      //ArrayCopy(arr1, ticksArr);
      //ArrayCopy(arr2, ticksArr);
      ArrayCopy(arr3, ticksArr);
      ArrayCopy(arr4, ticksArr);

      //--- ArraySort() benchmark.
      /*uint t1 = GetTickCount();
      ArraySort(arr1);
      uint ticks1 = GetTickCount() - t1;

      //--- RadixSort() benchmark.
      uint t2 = GetTickCount();
      RadixSort(arr2);
      uint ticks2 = GetTickCount() - t2;*/

      //--- GnomeSort() benchmark.
      uint t3 = GetTickCount();
      GnomeSort(arr3);
      uint ticks3 = GetTickCount() - t3;

      //--- QuickSort() benchmark.
      uint t4 = GetTickCount();
      QuickSort< MqlTick, FuncLess >(arr4, Less);
      uint ticks4 = GetTickCount() - t4;

      //Write(arr1, "ArraySort");
      //Write(arr2, "RadixSort");
      Write(arr3, "GnomeSort");
      Write(arr4, "QuickSort");

      //--- Display results.
      PrintFormat("Sorting %d integers: ", result);
      //PrintFormat("ArraySort() -> %u millisec", ticks1);
      //PrintFormat("RadixSort() -> %u millisec", ticks2);
      PrintFormat("GnomeSort() -> %u millisec", ticks3);
      PrintFormat("QuickSort() -> %u millisec", ticks4);
      PrintFormat("Speed-up factor is %.1fx", MathMax((double)ticks3, (double)ticks4) / MathMin(ticks3, ticks4));
     }
  }
//+------------------------------------------------------------------+
bool Less(const MqlTick& struct1, const MqlTick& struct2)
  {
   return struct1.time_msc < struct2.time_msc;
  }
//+------------------------------------------------------------------+
void GnomeSort(MqlTick & arr[])
  {
   int n = ArraySize(arr);
   int i = 0;
   while(i < n && !IsStopped())
     {
      if(i == 0 || (arr[i].time_msc >= arr[i - 1].time_msc))
         i++;
      else
        {
         long sw = arr[i - 1].time_msc;
         //Print(sw);
         arr[i - 1].time_msc = arr[i].time_msc;
         arr[i].time_msc = sw;
         i--;
        }
     }
  }
//+------------------------------------------------------------------+
string StrTime_msc(MqlTick& ticks)
  {
   int msc = (int)(ticks.time_msc % 1000);
   return(TimeToString(ticks.time, TIME_DATE | TIME_SECONDS) + "." + (msc < 10 ? "00" + (string)msc : msc < 100 ? "0" + (string)msc : (string)msc));
  }
//+------------------------------------------------------------------+
void Write(MqlTick& ticks[], string index = "1")
  {
   int file_handle = FileOpen(MQLInfoString(MQL_PROGRAM_NAME) + "\\"  + index + ".csv", FILE_WRITE | FILE_ANSI | FILE_CSV);
   int size = ArraySize(ticks);
   size = size > 100000 ? 100000 : size;
   for(int i = 0; i < size; i++)
      FileWrite(file_handle, StrTime_msc(ticks[i]),
                DoubleToString(ticks[i].bid, _Digits),
                DoubleToString(ticks[i].ask, _Digits),
                DoubleToString(ticks[i].last, _Digits),
                IntegerToString(ticks[i].volume),
                IntegerToString(ticks[i].time_msc),
                IntegerToString(ticks[i].flags),
                DoubleToString(ticks[i].volume_real, 0));
   FileClose(file_handle);
  }
//+------------------------------------------------------------------+
Sorting 20659820 integers: 
GnomeSort() -> 156 millisec
QuickSort() -> 3750 millisec
Speed-up factor is 24.0x


В этот раз все тики, оказались отсортированными по времени и сортировка свелась к простому перебору тиков в цикле.

Если я правильно использовал  QuickSort() , что вряд ли, то победу одержал простой гном).

  
typedef bool (*FuncLess)(const MqlTick&, const MqlTick&);

Это определение типа указателя на функцию.

QuickSort< MqlTick, FuncLess >( arr4, Less );

MqlTick и FuncLess - параметры шаблона.

Они нужны так как MQL, в отличие от C++, не может сам определить тип функции сравнения.

Возможно в будущем это исправят.


Если массив изначально неотсортирован, то Ваш гном работает бесконечно долго.

Кроме того, Ваша реализация GnomeSort(), сортирует не структуры, а поле time_msc этих структур.

Сами структуры остаются как были.


QuickSort() Вы используете правильно. Как видите, не так уж это и сложно.

 
Koldun Zloy #:

Кроме того, Ваша реализация GnomeSort(), сортирует не структуры, а поле time_msc этих структур.

Сами структуры остаются как были.

Опаньки!!! Лоханулся чуток.

Точно, так и есть, теперь вижу.

Спасибо.

 

Hello,

The ticks array is already sorted. So, using either insertion sort, bubble sort or gnome sort (actually, a variation of insertion sort) will be the fastest.

But, for example if 10 ticks are out of order, they will take ages because these algorithms has O(n^2) running time. So, they have limited practical use, except for sorting small arrays < 10-20 elements.

I prefer to randomize (shuffle) the ticks array before sorting, then sort using QuickSort, Introspective sort, modified RadixSort.

//+------------------------------------------------------------------+
//| RadixSort                                                        |
//| Sort an MqlTick[] array based on the field 'time_msc'.           |
//+------------------------------------------------------------------+
bool RadixSort(MqlTick &arr[])
  {
   MqlTick temp[];
   int n = ArraySize(arr);
   if(n < 2) return(n == 1);
   if(ArrayResize(temp, n) != n)
      return(false);
   int counts[sizeof(long)][256];
   ZeroMemory(counts);
   for(int i = 0; i < n; i++)
     {
      long ai = extract_field(arr[i]);
      for(uchar col = 0; col < sizeof(long); col++)
        {
         uchar key = extract_byte(ai, (uchar)(col << 3));
         ++counts[col][key];
        }
     }
   bool IsDynamic = ArrayIsDynamic(arr);
   for(uchar col = 0; col < sizeof(long); col++)
     {
      uchar shift = col << 3;

      //--- determine if any columns can be skipped
      if(counts[col][extract_byte(extract_field(arr[0]), shift)] == n)
         continue;
      int offset = 0;
      for(int i = 0; i < 256; i++)
        {
         int old_count = counts[col][i];
         counts[col][i] = offset;
         offset += old_count;
        }
      for(int i = 0; i < n; i++)
        {
         uchar key = extract_byte(extract_field(arr[i]), shift);
         temp[counts[col][key]++] = arr[i];
        }
#ifdef __MQL5__
      if(IsDynamic)
         ArraySwap(arr, temp);
      else
         ArrayCopy(arr, temp);
#else
      ArrayCopy(arr, temp);
#endif
     }
   return(true);
  }
//+------------------------------------------------------------------+
long extract_field(const MqlTick &st)
  {
   return st.time_msc;
  }
//+------------------------------------------------------------------+
uchar extract_byte(const long value, const uchar shift)
  {
   return (uchar)((value ^ 0x8000000000000000) >> shift);
  }

These are my results:

Shuffling ticks array before sorting..
Sorting 8645149 integers: 
QuickSort() -> 1703 millisec
Introsort() -> 1203 millisec
RadixSort() -> 641 millisec
Introsort speed-up factor is 1.4x
RadixSort speed-up factor is 2.7x

Although radix sort is faster, but quick and intro sort are easier to sort strings, objects and pointers.

Radix sort is optimized for one- or multi-dimensional arrays of numbers. (it needs some modifications for sorting structures which will make it more complex.)

The full script is uploaded.

Файлы:
sort_ticks_array.mq5  11 kb
 
amrali #:

Hello,

But, for example if 10 ticks are out of order, they will take ages because these algorithms has O(n^2) running time. 

Спасибо за ответ.

Ваш пример не корректен, так же как и мой предыдущий)

Теоретические обоснования это хорошо, но не стоит забывать о том с чем мы столкнёмся на практике.

1. Как часто вы сталкиваетесь с не отсортированными тиками?

2. Как часто эти тики перемешаны (shuffling) как после бетономешалки?


На первый вопрос я провёл тест, скачал тики за 300 дней по разным инструментам и проверил их на упорядоченность по времени.

Скачивал по 100 дней, поэтому по три ответа на каждый инструмент.

1: BR Splice, tick count 5483549, noSort 0
2: BR Splice, tick count 6033751, noSort 0
3: BR Splice, tick count 5020358, noSort 0

1: Si Splice, tick count 79145547, noSort 0
2: Si Splice, tick count 56921745, noSort 0
3: Si Splice, tick count 27226170, noSort 0

1: Si-3.23, tick count 1392971, noSort 0
2: Si-3.23, tick count 7859560, noSort 0
3: Si-3.23, tick count 20659820, noSort 0

1: NZDUSD, tick count 5360221, noSort 0
2: NZDUSD, tick count 5197399, noSort 0
3: NZDUSD, tick count 6440722, noSort 0

1: EURUSD, tick count 8075456, noSort 0
2: EURUSD, tick count 9727367, noSort 0
3: EURUSD, tick count 8662076, noSort 0

1: XAGUSD, tick count 3335460, noSort 0
2: XAGUSD, tick count 2825403, noSort 0
3: XAGUSD, tick count 3568420, noSort 0

1: SP500m, tick count 10106449, noSort 0
2: SP500m, tick count 6570729, noSort 0
3: SP500m, tick count 5307955, noSort 0


Как видите из семи инструментов ни одного не упорядоченного нет.

Как то на той неделе мне попался случай скачать не отсортированные тики, они были в начале текущёго дня и они не были сильно перемешаны, они были как бы сдвинуты пачкой немного ниже по времени, на несколько миллисекунд.

Я попробовал воссоздать тот случай. Скачал тики за 100 дней и сдвинул десяток тиков в начале последнего дня.


Ну и я всё таки вернул гнома в скрипт)

А теперь тест.

На первый взгляд  RadixSort()  выглядит как то не очень хорошо, в этом тесте, но тест ещё не закончен!

Посмотрим как справились с сортировкой другие сортировщики.

QuickSort()

Вроде после переделки сортировщик работал хорошо, почему всё красно-зелёное, я не понимаю, но сортировать тики этим сортировщиком нельзя.


Introsort() 

Как видим, результат тоже очень плохой, тики перетасованы сильнее чем до сортировки. Однозначно для сортировки тиков не подходит.


RadixSort() 


А вот RadixSort() справился со своей задачей отлично, несколько сдвинутых тиков с одинаковым временем можно не учитывать.

Для моих задач придётся писать ещё и проверку по цене, но это не страшно.


GnomeSort()


GnomeSort()  потратил на сортировку  235 millisec, это в четырнадцать раз быстрее  RadixSort()  -> 3422 millisec.


Имхо, не стоит устанавливать бетонный столб в туристической палатке, только потому, что он крепче стойки.


Файлы:
sort_ticks_array.mq5  13 kb
123
Новый комментарий
Причина обращения: