Хорошая сортировка, быстрая, жаль не подходит для сортировки тиков :(
При сортировке переставляет местами тики с одинаковым временем.
Слева до сортировки, справа после сортировки.
Сортировал и просто по времени и по времени тика в миллисекундах, результат одинаковый.
Хорошая сортировка, быстрая, жаль не подходит для сортировки тиков :(
При сортировке переставляет местами тики с одинаковым временем.
Слева до сортировки, справа после сортировки.
Сортировал и просто по времени и по времени тика в миллисекундах, результат одинаковый.
Спасибо за сообщение.
Такое поведение исправил.
К сожалению, за счёт небольшого снижения скорости.
Спасибо за сообщение.
Такое поведение исправил.
К сожалению, за счёт небольшого снижения скорости.
Ух ты, как быстро!
А я уже поставил гномью сортировку.
Мне надо сортировка тиков дней за десять, а учитывая, что тиков с не правильным временем попадается всего штук 10-15 в день, сортируется довольно быстро.
Появится время, сравню кто быстрее)
Ух ты, как быстро!
А я уже поставил гномью сортировку.
Мне надо сортировка тиков дней за десять, а учитывая, что тиков с не правильным временем попадается всего штук 10-15 в день, сортируется довольно быстро.
Появится время, сравню кто быстрее)
Сравню, обязательно сравню (но это не точно).
М-да, сравнивальщик из меня так себе.
Задача: сравнить скорость работы крутых библиотек 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() Вы используете правильно. Как видите, не так уж это и сложно.
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.
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.
Имхо, не стоит устанавливать бетонный столб в туристической палатке, только потому, что он крепче стойки.
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования
Быстрая сортировка.:
Функции для сортировки массивов. Позволяют сортировать строки и структуры по любому условию.
Автор: Koldun Zloy