Fan sayfamıza katılın
Öyleyse bir link gönderin -
başkalarının da faydalanmasını sağlayın
- Görüntülemeler:
- 2588
- Derecelendirme:
- Yayınlandı:
- 2022.03.27 21:56
- Güncellendi:
- 2023.02.10 13:31
-
Bu koda dayalı bir robota veya göstergeye mi ihtiyacınız var? Freelance üzerinden sipariş edin Freelance'e git
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
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](https://c.mql5.com/i/code/indicator.png)
This indicator displays the percentage of price movement per candle, as an average of the latest candles.
![Currency Strength Meter MT5](https://c.mql5.com/i/code/indicator.png)
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](https://c.mql5.com/i/code/indicator.png)
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](https://c.mql5.com/i/code/indicator.png)
'RSI' line, 'RSI' line smoothed with 'MA'. Fill areas between these two lines.