거래 로봇을 무료로 다운로드 하는 법을 시청해보세요
당사를 Telegram에서 찾아주십시오!
당사 팬 페이지에 가입하십시오
스크립트가 흥미로우신가요?
그렇다면 링크 to it -
하셔서 다른 이들이 평가할 수 있도록 해보세요
스크립트가 마음에 드시나요? MetaTrader 5 터미널에서 시도해보십시오
라이브러리

Radix sort (The fastest numeric sort) - MetaTrader 5용 라이브러리

조회수:
2575
평가:
(41)
게시됨:
2022.03.27 21:56
업데이트됨:
2023.02.10 13:31
\MQL5\Scripts\RadixSort\
RadixSort.mqh (37.14 KB) 조회
MQL5 프리랜스 이 코드를 기반으로 한 로봇이나 지표가 필요하신가요? 프리랜스로 주문하세요 프리랜스로 이동

RadixSort Algorithm

RadixSort sorts numeric data (integers or float) by considering a string of numbers where digit by digit sort starting from least significant digit position to most significant digit position.

The algorithm is better explained on that Wikipedia page https://en.wikipedia.org/wiki/Radix_sort


Time Complexity and Performance

Radix sort has linear time complexity, it operates in O(n * k) time, where:

    n = the number of elements to sort
    k = the maximum element width (number of bytes) of the elements to sort

The algorithm iterates over k byte places in LSD (least significant digit) order; for each byte place, it iterates over all n elements to sort them by the k-th byte.


RadixSort Implementation in MQL

This is a highly-optimized implementation of LSD RadixSort in MQL using radix 256 (8-bits). This could be useful for sorting huge arrays with millions of numbers.

This implementation is based on radix sort by Pierre Terdiman, published at http://codercorner.com/RadixSortRevisited.htm, with select optimizations published by Michael Herf at http://stereopsis.com/radix.html and by Eddy L O Jansson at https://github.com/eloj/radix-sorting.

The function is at least 3-10 times faster than MQL's built-in ArraySort() function. 

The function accepts any-dimensional arrays of simple type (char, uchar, short, ushort, int, uint, long, ulong, bool, color, datetime, float, double) as a parameter. However, sorting is always applied to the first (zero) dimension. 

An array is always sorted in the ascending order irrespective of the AS_SERIES flag value.

Note that, the algorithm falls back to ArraySort() if the array contains less than some threshold of items (currently 128).

Radix sort should be the default for sorting numeric data as it operates in O(n * k) time. Comparison-based sorting algorithms (like quicksort, mergesort and heapsort) run in O(n * log n) time. Thus, Radix sort is comparatively faster, the larger the array size. The downside of radix sort is that it needs more memory (temporary array) to do its work.

 

//+------------------------------------------------------------------+
//| RadixSort                                                        |
//+------------------------------------------------------------------+
//| Sorts the values in the first dimension of a multidimensional    |
//| numeric array in the ascending order.                            |
//|                                                                  |
//| Arguments:                                                       |
//| array[]                                                          |
//|   [in][out] : Numeric array for sorting.                         |
//|                                                                  |
//| Return value: true if successful, otherwise false.               |
//|                                                                  |
//| Note:                                                            |
//|   An array is always sorted in the ascending order irrespective  |
//|   of the AS_SERIES flag value.                                   |
//|                                                                  |
//|   The function accepts any-dimensional arrays of simple type     |
//|   (char, uchar, short, ushort, int, uint, long, ulong, bool,     |
//|   color, datetime, float, double) as a parameter.  However,      |
//|   sorting is always applied to the first (zero) dimension.       |
//|                                                                  |
//| Performance:                                                     |
//|   This is a highly-optimized implementation of LSD RadixSort     |
//|   in MQL using radix 256 (8-bits). This could be useful for      |
//|   sorting huge numeric arrays with millions of numbers.          |
//|   It is at least 3-10 times faster than built-in ArraySort().    |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSort(T &arr[]);


//+------------------------------------------------------------------+
//| RadixSort                                                        |
//+------------------------------------------------------------------+
//| Sorts the values in the first dimension of a multidimensional    |
//| numeric array in the ascending order.                            |
//|                                                                  |
//| Function overload for higher-dimensional numeric arrays.         |
//|                                                                  |
//| Arguments:                                                       |
//| array[]                                                          |
//|   [in][out] : Numeric array for sorting.                         |
//|                                                                  |
//| Return value: true if successful, otherwise false.               |
//+------------------------------------------------------------------+
// Sorts two-dimensional numeric arrays.
template<typename T>
bool RadixSort(T &arr[][]);


// Sorts three-dimensional numeric arrays.
template<typename T>
bool RadixSort(T &arr[][][]);

// Sorts four-dimensional numeric arrays.
template<typename T>
bool RadixSort(T &arr[][][][]);


//+------------------------------------------------------------------+
//| RadixSortIndices                                                 |
//+------------------------------------------------------------------+
//| Populate an array of indices[] in the order that would sort      |
//| the values of a numeric array[] in the ascending order.          |
//|                                                                  |
//| Arguments:                                                       |
//| array[]     : Array with numeric values to sort                  |
//| indices[]   : Array for sorted indices                           |
//|                                                                  |
//| Return value: true if successful, otherwise false.               |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSortIndices(const T &arr[], int &indices[]);


//+------------------------------------------------------------------+
//| ParallelRadixSort                                                |
//+------------------------------------------------------------------+
//| The function sorts array[] and items[] simultaneously using      |
//| RadixSort algorithm. After sorting the items[] array is sorted   |
//| by the numeric values of array[] in the ascending order.         |
//|                                                                  |
//| Arguments:                                                       |
//| array[]     : Array with numeric keys to sort                    |
//| items[]     : Array for items to sort based on keys              |
//|                                                                  |
//| Return value: true if successful, otherwise false.               |
//+------------------------------------------------------------------+
template<typename T,typename TItem>
bool ParallelRadixSort(T &arr[], TItem &items[]);



This is a benchmark script that demonstrates the speed advantage of RadixSort() over MQL's ArraySort():

//+------------------------------------------------------------------+
//|                                          RadixSort_benchmark.mq5 |
//|                                        Copyright © 2018, Amr Ali |
//|                             https://www.mql5.com/en/users/amrali |
//+------------------------------------------------------------------+
#include "RadixSort.mqh"

#define SIZE 10*1000*1000  // 10 millions
int     arr1[SIZE];
int     arr2[SIZE];
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
void OnStart()
  {
//--- Prepare unsorted arrays.
   for(int i = 0; i < SIZE; i++)
     {
      arr1[i] = MathRand();
      arr2[i] = arr1[i];
     }

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

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

//--- Display results.
   PrintFormat("Sorting %d integers: ", SIZE);
   PrintFormat("ArraySort() -> %u millisec", ticks1);
   PrintFormat("RadixSort() -> %u millisec", ticks2);
   PrintFormat("Speed-up factor is %.1fx", (double)ticks1/ticks2);
   PrintFormat("%s", ArrayCompare(arr1, arr2) ? "RadixSort: invalid sort order.": "");
  }
//+------------------------------------------------------------------+

// sample output:
/*
 Sorting 10000000 integers:
 ArraySort() -> 953 millisec
 RadixSort() -> 62 millisec
 Speed-up factor is 15.4x
*/


To replace MQL's ArraySort() by RadixSort() in your old mq5 or mqh files, just add these two lines at the top of the file:

#include "RadixSort.mqh"

#define ArraySort(a) RadixSort(a)




Percentage of price movement per candle - Simple and Crucial Percentage of price movement per candle - Simple and Crucial

This indicator displays the percentage of price movement per candle, as an average of the latest candles.

Currency Strength Meter MT5 Currency Strength Meter MT5

Currency Strength Meter for MetaTrader 5 with configurable timeframe parameter, It was converted from "Currency Strength Giraia 28 pairs TRO MODIFIED" MetaTrader 4 version

Alert Crossing Three MAs Alert Crossing Three MAs

The indicator shows signals ('Arrow' objects) of the 'Moving Average' indicator crossings. The peculiarity of the indicator: if there was an intersection of 'MAs' (on bar #0), and then the intersection disappeared, the signal remains on the chart

RSI_MAonRSI_Filling RSI_MAonRSI_Filling

'RSI' line, 'RSI' line smoothed with 'MA'. Fill areas between these two lines.