数组的比较、排序和搜索
MQL5 API 包含若干函数，可用于比较和排序数组，以及在数组中搜索最大值、最小值或任何特定值。
int ArrayCompare(const void &array1[], const void &array2[], int start1 = 0, int start2 = 0, int count = WHOLE_ARRAY)
该函数返回比较两个数组的比较结果，可以是内置类型数组或具有内置类型字段的结构体数组（字符串除外）。不支持类对象数组。此外，不能比较包含动态数组、类对象或指针的结构体数组。
默认情况下，为整个数组执行比较，但如果必要，可以指定数组的某一部分，为此，可以使用参数 start1（在第一个数组中的开始位置）、start2（在第二个数组中的开始位置）以及 count。
数组可以是固定或动态数组，也可以是多维数组。在比较期间，多维数组被表示为等效一维数组（例如，对于二维数组，第二行的元素跟随第一行的元素，第三行的元素跟随第二行，依此类推）。因此，用于多维数组的 start1、start2 和 count 参数通过元素编号指定，而不是通过沿第一维度的索引指定。
使用各种 start1 和 start2 偏移，可以比较同一数组的不同部分。
逐元素比较数组，直至找到第一个不一致，或者直至到达某个数组的末尾。两个元素（在两个数组中的位置相同）之间的关系取决于类型：对于数字，使用运算符 '>'、'<'、'=='，而对于字符串，使用 StringCompare 函数。结构体通过逐字节比较，等效于为每对元素执行以下代码：
uchar bytes1[], bytes2[];
StructToCharArray(array1[i], bytes1);
StructToCharArray(array2[i], bytes2);
int cmp = ArrayCompare(bytes1, bytes2);
|
基于第一批差异元素的比率，获得 array1 和 array2 数组的批量比较结果。如果未找到差异，并且数组的长度相等，则数组被视为相同。如果长度不同，则较长的数组被视为更大。
如果 array1 小于 array2，函数返回 -1；如果 array1 大于 array2，返回 +1；如果相等，返回 0。
如果出错，结果为 -2。
我们看看 ArrayCompare.mq5 脚本中的一些示例。
我们创建一个简单结构，用引填充要比较的数组。
struct Dummy
{
int x;
int y;
Dummy()
{
x = rand() / 10000;
y = rand() / 5000;
}
};
|
类字段填充了随机数字（每次运行该脚本，我们将接收到新值）。
在 OnStart 函数中，我们描述一个小结构体数组，并逐个比较连续元素（以 1 元素的长度移动数组的相邻片断）。
#define LIMIT 10
void OnStart()
{
Dummy a1[LIMIT];
ArrayPrint(a1);
// pairwise comparison of neighboring elements
// -1: [i] < [i + 1]
// +1: [i] > [i + 1]
for(int i = 0; i < LIMIT - 1; ++i)
{
PRT(ArrayCompare(a1, a1, i, i + 1, 1));
}
...
|
下面是其中一个数组选项的结果（为方便分析，具有“大于”(+1)/“小于”(-1) 符号的列直接被添加到数组内容的右边）：
[x] [y] // result
[0] 0 3 // -1
[1] 2 4 // +1
[2] 2 3 // +1
[3] 1 6 // +1
[4] 0 6 // -1
[5] 2 0 // +1
[6] 0 4 // -1
[7] 2 5 // +1
[8] 0 5 // -1
[9] 3 6
|
比较数组的两个对半部分，给出的结果为 -1：
// compare first and second half
PRT(ArrayCompare(a1, a1, 0, LIMIT / 2, LIMIT / 2)); // -1
|
接下来，我们将比较具有预定义数据的字符串数组。
string s[] = {"abc", "456", "$"};
string s0[][3] = {{"abc", "456", "$"}};
string s1[][3] = {{"abc", "456", ""}};
string s2[][3] = {{"abc", "456"}}; // last element omitted: it is null
string s3[][2] = {{"abc", "456"}};
string s4[][2] = {{"aBc", "456"}};
PRT(ArrayCompare(s0, s)); // s0 == s, 1D and 2D arrays contain the same data
PRT(ArrayCompare(s0, s1)); // s0 > s1 since "$" > ""
PRT(ArrayCompare(s1, s2)); // s1 > s2 since "" > null
PRT(ArrayCompare(s2, s3)); // s2 > s3 due to different lengths: [3] > [2]
PRT(ArrayCompare(s3, s4)); // s3 < s4 since "abc" < "aBc"
|
最后，我们检查数组片断比率：
PRT(ArrayCompare(s0, s1, 1, 1, 1)); // second elements (with index 1) are equal
PRT(ArrayCompare(s1, s2, 0, 0, 2)); // the first two elements are equal
|
bool ArraySort(void &array[])
该函数按第一维度对数字数组（包括可能的多维数组）排序。排序顺序为升序。要将数组降序排序，将 ArrayReverse 函数应用到生成的数组，或者以逆序处理数组。
该函数不支持由字符串、结构或类构成的数组。
如果成功，该函数返回 true，如果出错，则返回 false。
如果为数组设置了“时间序列”属性，则其中的元素以逆序索引（详见章节 数组中时间序列的索引方向），这对排序顺序具有“外部”逆反效应：当直接处理此类数组时，将会获得降序值。在物理层面，数组始终以升序排序，这也是数组的存储方式。
在 ArraySort.mq5 脚本中，生成一个 10 × 3 的二维数组并使用 ArraySort 排序：
#define LIMIT 10
#define SUBLIMIT 3
void OnStart()
{
// generating random data
int array[][SUBLIMIT];
ArrayResize(array, LIMIT);
for(int i = 0; i < LIMIT; ++i)
{
for(int j = 0; j < SUBLIMIT; ++j)
{
array[i][j] = rand();
}
}
Print("Before sort");
ArrayPrint(array); // source array
PRTS(ArraySort(array));
Print("After sort");
ArrayPrint(array); // ordered array
...
}
|
根据日志，第一列以升序排序（由于是随机生成，具体数字会变化）：
Before sort
[,0] [,1] [,2]
[0,] 8955 2836 20011
[1,] 2860 6153 25032
[2,] 16314 4036 20406
[3,] 30366 10462 19364
[4,] 27506 5527 21671
[5,] 4207 7649 28701
[6,] 4838 638 32392
[7,] 29158 18824 13536
[8,] 17869 23835 12323
[9,] 18079 1310 29114
ArraySort(array)=true / status:0
After sort
[,0] [,1] [,2]
[0,] 2860 6153 25032
[1,] 4207 7649 28701
[2,] 4838 638 32392
[3,] 8955 2836 20011
[4,] 16314 4036 20406
[5,] 17869 23835 12323
[6,] 18079 1310 29114
[7,] 27506 5527 21671
[8,] 29158 18824 13536
[9,] 30366 10462 19364
|
后续列中的值已与第一列中的“先导”值同步移动。换言之，全部行都进行置换，尽管仅第一列是排序标准。
但如果你想对一个二维数组排序，但又不想将第一个列作为排序标准，那该怎么办？可以为此编写一个专门算法。其中一个选项作为模板函数包括在 ArraySort.mq5 文件中：
template<typename T>
bool ArraySort(T &array[][], const int column)
{
if(!ArrayIsDynamic(array)) return false;
if(column == 0)
{
return ArraySort(array); // standard function
}
const int n = ArrayRange(array, 0);
const int m = ArrayRange(array, 1);
T temp[][2];
ArrayResize(temp, n);
for(int i = 0; i < n; ++i)
{
temp[i][0] = array[i][column];
temp[i][1] = i;
}
if(!ArraySort(temp)) return false;
ArrayResize(array, n * 2);
for(int i = n; i < n * 2; ++i)
{
ArrayCopy(array, array, i * m, (int)(temp[i - n][1] + 0.1) * m, m);
/* equivalent
for(int j = 0; j < m; ++j)
{
array[i][j] = array[(int)(temp[i - n][1] + 0.1)][j];
}
*/
}
return ArrayRemove(array, 0, n);
}
|
给定函数仅对动态数组有效，因为 array 的大小翻倍以容纳数组后半部分中的中间结果，并且最后，使用 ArrayRemove 移除前半部分（原始部分）。这就是为什么 OnStart 函数中的原始测试数组通过 ArrayResize 分配空间。
我们鼓励你自己研究排序原理（或者查阅相关资料）。
对于具有大量维度的数组（如 array[][][]），应实施相似的操作。
回想在前一节中，我们提出了按任意字段对结构体数组排序的问题。如我们所知，标准 ArraySort 函数无法完成这一任务。我们尝试找到一种变通路线。我们以前一节中 ArraySwapSimple.mq5 文件中的类为基础。我们将其拷贝到 ArrayWorker.mq5，并添加需要的代码。
在 Worker::process 方法中，我们将提供对辅助排序方法 arrayStructSort 的调用，要排序的字段将以编号指定（具体操作将在下文中介绍）：
...
bool process(const int mode)
{
...
switch(mode)
{
...
case -1:
ArrayReverse(array);
break;
default: // sorting by field number 'mode'
arrayStructSort(mode);
break;
}
return true;
}
private:
bool arrayStructSort(const int field)
{
...
}
|
现在应该明白为什么在 process 方法中所有之前的模式（mode 参数的值）均为负数了：零和正数值保留用于排序，并对应于“列”号。
对结构体数组排序的概念来自于对二维数组排序。我们只需要以某种方式将单个结构体映射到一维数组（代表二维数组的一行）。为此，首先要决定数组应为哪种类型。
由于 worker 类已经是模板，我们将向该模板再添加一个参数，以便可以灵活设置数组类型。
template<typename T, typename R>
class Worker
{
T array[];
...
|
现在，我们回到 联合体，联合体将不同类型的变量相互重叠。这样，我们得到以下巧妙的构造：
union Overlay
{
T r;
R d[sizeof(T) / sizeof(R)];
};
|
在该联合体中，结构体的类型与一个 R 类型的数组组合，其大小由编译器根据两种类型 T 和 R 的大小比率自动计算。
现在，在 arrayStructSort 方法中，我们能够部分复制二维数组排序的代码。
bool arrayStructSort(const int field)
{
const int n = ArraySize(array);
R temp[][2];
Overlay overlay;
ArrayResize(temp, n);
for(int i = 0; i < n; ++i)
{
overlay.r = array[i];
temp[i][0] = overlay.d[field];
temp[i][1] = i;
}
...
|
我们弃用了原始结构的数组，而是准备了 R 类型的 temp[][2] 数组，将其扩展至 array 中的记录数，并在循环中写入以下内容：每行第 0 个索引处“显示”必须的 field 字段，在第 1 个索引处“显示”该元素的原始索引。
该“显示”基于以下事实：结构体中的字段通常以某种方式对齐，因为它们使用标准型。因此，对于适当选择的 R 类型，能够在“重叠”的数组元素中提供全部或部分字段命中。
例如，在标准结构 MqlRates 中，前 6 个字段大小为 8 字节，因此正确映射到 double 或 long 数组（这些是 R 模板类型的候选）。
struct MqlRates
{
datetime time;
double open;
double high;
double low;
double close;
long tick_volume;
int spread;
long real_volume;
};
|
对于最后两个字段，情况更复杂。如果使用 int 类型作为 R 仍然能访问 spread 字段，则 real_volume 字段的偏移量就不是自身大小倍数（因为其前面的字段类型是 int，即 4 字节）。这些是特定方法的问题。可以改进这些方法，或者创造另一种方法。
我们继续讨论排序算法。填充了 temp 数组之后，可以使用常规函数 ArraySort 对其排序，然后原始索引可用于以正确结构顺序形成新的数组。
...
if(!ArraySort(temp)) return false;
T result[];
ArrayResize(result, n);
for(int i = 0; i < n; ++i)
{
result[i] = array[(int)(temp[i][1] + 0.1)];
}
return ArraySwap(result, array);
}
|
在退出该函数之前，我们再次使用 ArraySwap，以高效利用资源的方式，用某些新的有序内容替换内部对象数组 array 的内容，这些内容在局部数组 result 中获得。
我们在操作中检查 worker 类：在函数 OnStart 中，我们定义结构体数组 MqlRates，并向终端请求数千条记录。
#define LIMIT 5000
void OnStart()
{
MqlRates rates[];
int n = CopyRates(_Symbol, _Period, 0, LIMIT, rates);
...
|
CopyRates 函数将在 单独章节中介绍。目前而言，我们只需要知道，该函数用交易品种报价和对当前图表运行脚本的时间范围来填充传递的 rates 数组。LIMIT 宏指定请求的柱数量：你需要确保该值不大于你的终端对于每个窗口中的柱数量的设置。
为处理接收的数据，我们将创建一个类型为 T=MqlRates 和 R=double 的对象 worker：
Worker<MqlRates, double> worker(rates);
|
可以使用以下格式的指令开始排序：
worker.process(offsetof(MqlRates, open) / sizeof(double));
|
这里我们使用 offsetof 运算符获取结构体内 open 字段的字节偏移。它进一步除以 double 大小，并提供正确的“列”号用于按 open 价格排序。可以逐元素读取排序结果，也可以获取整个数组：
Print(worker[i].open);
...
worker.get(rates);
ArrayPrint(rates);
|
请注意，通过 get 方法获取数组会使用 ArraySwap 将其从内部数组 array 中移除到外部数组（作为自变量传递）。因此，在此之后的 worker.process() 调用没有意义：在对象 worker 中没有更多数据。
为简化按不同字段的排序启动过程，实现了辅助函数 sort：
void sort(Worker<MqlRates, double> &worker, const int offset, const string title)
{
Print(title);
worker.process(offset);
Print("First struct");
StructPrint(worker[0]);
Print("Last struct");
StructPrint(worker[worker.size() - 1]);
}
|
该函数向日志输出一个标头以及已排序数组的第一个和最后一个元素。在该函数的帮助下，在 OnStart 中对三个字段的测试如下：
voidOnStart()
{
...
Worker<MqlRates,double>worker(rates);
sort(worker,offsetof(MqlRates,open) /sizeof(double),"Sorting by open price...");
sort(worker,offsetof(MqlRates,tick_volume) /sizeof(double),"Sorting by tick volume...");
sort(worker,offsetof(MqlRates,time) /sizeof(double),"Sorting by time...");
}
|
遗憾的是，标准函数 print 不支持打印单个结构体，并且在 MQL5 中没有内置函数 StructPrint。因此，我们必须基于 ArrayPrint 自己编写：事实上，将结构体放在一个大小为 1 的数组中即可。
template<typename S>
void StructPrint(const S &s)
{
S temp[1];
temp[0] = s;
ArrayPrint(temp);
}
|
运行该脚本之后，我们可以获得类似如下的结果（取决于终端设置，即其执行所针对的交易品种/时间范围）：
Sorting by open price...
First struct
[time] [open] [high] [low] [close] [tick_volume] [spread] [real_volume]
[0] 2021.07.21 10:30:00 1.17557 1.17584 1.17519 1.17561 1073 0 0
Last struct
[time] [open] [high] [low] [close] [tick_volume] [spread] [real_volume]
[0] 2021.05.25 15:15:00 1.22641 1.22664 1.22592 1.22618 852 0 0
Sorting by tick volume...
First struct
[time] [open] [high] [low] [close] [tick_volume] [spread] [real_volume]
[0] 2021.05.24 00:00:00 1.21776 1.21811 1.21764 1.21794 52 20 0
Last struct
[time] [open] [high] [low] [close] [tick_volume] [spread] [real_volume]
[0] 2021.06.16 21:30:00 1.20436 1.20489 1.20149 1.20154 4817 0 0
Sorting by time...
First struct
[time] [open] [high] [low] [close] [tick_volume] [spread] [real_volume]
[0] 2021.05.14 16:15:00 1.21305 1.21411 1.21289 1.21333 888 0 0
Last struct
[time] [open] [high] [low] [close] [tick_volume] [spread] [real_volume]
[0] 2021.07.27 22:45:00 1.18197 1.18227 1.18191 1.18225 382 0 0
|
这里是 EURUSD,M15 的数据。
上述排序实现可能是最快的方式之一，因为它使用内置的 ArraySort。
然而，如果难以对齐结构体字段，或者对于将结构“映射”到数组的方法存疑，从而迫使我们放弃这一方法（继而放弃 ArraySort 函数），则经证实的 DIY 方法仍然可使用。
有大量的排序算法可轻松适配 MQL5。本书随附的 QuickSortStructT.mqh 文件中提供了一种快速排序选择。它就是改进版的 QuickSortT.mqh，我们在 字符串比较的章节中介绍。它具有模板类 QuickSortStructT 的 Compare 方法，其完全是虚拟的，必须在子代类中重新定义，以便为要求的类型及其字段返回比较运算符 '>' 的类似结果。为方便用户，在头文件中创建了一个宏：
#define SORT_STRUCT(T, A, F) \
{ \
class InternalSort : public QuickSortStructT<T> \
{ \
virtual bool Compare(const T &a, const T &b) override \
{ \
return a.##F > b.##F; \
} \
} sort; \
sort.QuickSort(A); \
}
|
使用该宏，要按给定字段对结构数组排序，编写一条指令就行了。例如：
MqlRates rates[];
CopyRates(_Symbol, _Period, 0, 10000, rates);
SORT_STRUCT(MqlRates, rates, high);
|
其中，MqlRates 类型的 rates 数组按 high 价格排序。
int ArrayBsearch(const type &array[], type value)
该函数在数值数组中搜索给定值。支持所有内置数值类型的数组。数组必须按第一维度以升序排序，否则结果将不正确。
该函数返回匹配元素的索引（如果有多个匹配元素，对返回其中第一个的索引）或者值最接近的元素的索引（如果没有完全匹配项），也就是说，可能是值大于或小于搜索值的元素。如果期望值小于第一个（最小值），则返回 0。如果搜索值大于最后一个（最大值），则返回其索引。
该索引取决于数组中元素的编号方向：正向（从开头到末尾）或反向（从末尾到开头）。可以使用 数组中时间序列的索引方向一节中描述的函数确认和更改。
如果出错，则返回 -1。
对于多维数组，搜索限于第一维度。
在 ArraySearch.mq5 脚本中，可以找到 ArrayBsearch 函数的用法示例。
void OnStart()
{
int array[] = {1, 5, 11, 17, 23, 23, 37};
// indexes 0 1 2 3 4 5 6
int data[][2] = {{1, 3}, {3, 2}, {5, 10}, {14, 10}, {21, 8}};
// indexes 0 1 2 3 4
int empty[];
...
|
对于三个预定义数组（其中一个为空），执行以下语句：
PRTS(ArrayBsearch(array, -1)); // 0
PRTS(ArrayBsearch(array, 11)); // 2
PRTS(ArrayBsearch(array, 12)); // 2
PRTS(ArrayBsearch(array, 15)); // 3
PRTS(ArrayBsearch(array, 23)); // 4
PRTS(ArrayBsearch(array, 50)); // 6
PRTS(ArrayBsearch(data, 7)); // 2
PRTS(ArrayBsearch(data, 9)); // 2
PRTS(ArrayBsearch(data, 10)); // 3
PRTS(ArrayBsearch(data, 11)); // 3
PRTS(ArrayBsearch(data, 14)); // 3
PRTS(ArrayBsearch(empty, 0)); // -1, 5053, ERR_ZEROSIZE_ARRAY
...
|
此外，在 populateSortedArray 辅助函数中，numbers 数组以随机值填充，并且使用 ArrayBsearch 将该数组持续保持为已排序状态。
void populateSortedArray(const int limit)
{
double numbers[]; // array to fill
doubleelement[1];// new value to insert
ArrayResize(numbers, 0, limit); // allocate memory beforehand
for(int i = 0; i < limit; ++i)
{
// generate a random number
element[0] = NormalizeDouble(rand() * 1.0 / 32767, 3);
// find where its place in the array
int cursor = ArrayBsearch(numbers, element[0]);
if(cursor == -1)
{
if(_LastError == 5053) // empty array
{
ArrayInsert(numbers, element, 0);
}
else break; // error
}
else
if(numbers[cursor] > element[0]) // insert at 'cursor' position
{
ArrayInsert(numbers, element, cursor);
}
else // (numbers[cursor] <= value) // insert after 'cursor'
{
ArrayInsert(numbers, element, cursor + 1);
}
}
ArrayPrint(numbers, 3);
}
|
每个新值首先进入一个元素的数组 element，因为这样更方便将其插入生成的 numbers 数组中（使用函数 ArrayInsert）。
ArrayBsearch 可让你确定应插入新值的位置。
该函数的结果显示在日志中：
void OnStart()
{
...
populateSortedArray(80);
/*
example (will be different on each run due to randomization)
[ 0] 0.050 0.065 0.071 0.106 0.119 0.131 0.145 0.148 0.154 0.159
0.184 0.185 0.200 0.204 0.213 0.216 0.220 0.224 0.236 0.238
[20] 0.244 0.259 0.267 0.274 0.282 0.293 0.313 0.334 0.346 0.366
0.386 0.431 0.449 0.461 0.465 0.468 0.520 0.533 0.536 0.541
[40] 0.597 0.600 0.607 0.612 0.613 0.617 0.621 0.623 0.631 0.634
0.646 0.658 0.662 0.664 0.670 0.670 0.675 0.686 0.693 0.694
[60] 0.725 0.739 0.759 0.762 0.768 0.783 0.791 0.791 0.791 0.799
0.838 0.850 0.854 0.874 0.897 0.912 0.920 0.934 0.944 0.992
*/
|
int ArrayMaximum(const type &array[], int start = 0, int count = WHOLE_ARRAY)
int ArrayMinimum(const type &array[], int start = 0, int count = WHOLE_ARRAY)
ArrayMaximum 和 ArrayMinimum 函数分别在数值数组中搜索具有最大值和最小值的元素。搜索索引范围由 start 和 count 参数设置：如果是默认值，则搜索整个数组。
该函数返回找到的元素的位置。
如果为数组设置了“系列”属性（“时间序列”），则以反序对元素进行索引，这会影响该函数的结果（参见示例）。用于处理“系列”属性的内置函数在 下一章节讨论。有关“系列”数组的更多细节将在关于 时间序列 和 指标的章节中讨论。
在多维数组中，对第一维度执行搜索。
如果在具有最大值或最小值的数组中有若干个相同的元素，则函数将返回其中第一个的索引。
函数用法示例在 ArrayMaxMin.mq5 文件中提供。
#define LIMIT 10
void OnStart()
{
// generating random data
int array[];
ArrayResize(array, LIMIT);
for(int i = 0; i < LIMIT; ++i)
{
array[i] = rand();
}
ArrayPrint(array);
// by default, the new array is not a timeseries
PRTS(ArrayMaximum(array));
PRTS(ArrayMinimum(array));
// turn on the "serial" property
PRTS(ArraySetAsSeries(array, true));
PRTS(ArrayMaximum(array));
PRTS(ArrayMinimum(array));
}
|
该脚本将记录类似下列字符串的内容（由于数据随机生成，每次运行都不同）：
22242 5909 21570 5850 18026 24740 10852 2631 24549 14635
ArrayMaximum(array)=5 / status:0
ArrayMinimum(array)=7 / status:0
ArraySetAsSeries(array,true)=true / status:0
ArrayMaximum(array)=4 / status:0
ArrayMinimum(array)=2 / status:0
|