Сравнение, сортировка и поиск в массивах
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[];
|
На основании соотношения первых различающихся элементов получается результат сравнения массивов array1 и array2 целиком. Если отличий не найдено и длина массивов равна, то массивы считаются одинаковыми. Если длина отличается, то более длинный массив считается больше.
Функция возвращает -1 — если array1 "меньше" array2, +1 — если array1 "больше" array2, 0 если они "равны".
В случае ошибки результат равен -2.
Рассмотрим некоторые примеры в скрипте ArrayCompare.mq5.
Прежде всего создадим простую структуру для наполнения массивов, подлежащих сравнению.
struct Dummy
|
Поля класса заполняются случайными числами (при каждом запуске скрипта будем получать новые значения).
В функции OnStart опишем небольшой массив структур и сравним последовательные элементы друг с другом (как сдвигающиеся соседние фрагменты массива длиной 1 элемент).
#define LIMIT 10
|
Ниже приведены результаты для одного из вариантов массива (для удобства анализа колонка с признаками "больше"(+1)/"меньше"(-1) добавлена непосредственно справа от содержимого массива):
[x] [y] // результат
|
Сравнение двух половин массива между собой дает -1:
// сравнение первой и второй половины
|
Далее проведем сравнение массивов строк с предопределенными данными.
string s[] = {"abc","456","$"};
|
Наконец, проверим соотношение фрагментов массивов:
PRT(ArrayCompare(s0, s1, 1, 1, 1)); // вторые элементы (с индексом 1) равны
|
bool ArraySort(void &array[])
Функция сортирует числовой массив (в том числе, возможно многомерный) по первому измерению. Порядок сортировки — по возрастанию. Если требуется сортировка по убыванию, примените к результирующему массиву функцию ArrayReverse или обходите его в обратном порядке.
Функция не поддерживает массивы строк, структур или классов.
Функция возвращает true в случае успеха или false в случае ошибки.
Если для массива установлено свойство "таймсерии" (временного ряда), то индексация элементов в нем ведется в обратном порядке (см. подробности в разделе Направление индексации массивов как в таймсерии), и это оказывает "внешний" разворотный эффект на порядок сортировки: при прямом обходе такого массива вы получите убывающие значения. На физическом уровне массив всегда сортируется по возрастанию значений, и именно так и хранится.
В скрипте ArraySort.mq5 генерируется двумерный массив размером 10 на 3 и затем сортируется с помощью ArraySort:
#define LIMIT 10
|
По выводу в журнал легко убедиться, что первая колонка отсортирована по возрастанию (конкретные числа будут меняться из-за случайной генерации):
Before sort
|
Значения в следующих колонках переместились синхронно с "ведущими" показателями в первой колонке. Иными словами, перестановке подвергаются ряды целиком, несмотря на то, что критерием сортировки выступает только первая колонка.
Что делать, если требуется сортировать двумерный массив по колонке, отличной от первой? Можно написать алгоритм самостоятельно. Один из вариантов включен в файл ArraySort.mq5 как шаблонная функция:
template<typename T>
|
Данная функция работает только с динамическими массивами, поскольку размер array удваивается для сборки промежуточных результатов во второй половине массива, а в завершении первая половина (исходная) удаляется с помощью ArrayRemove. Именно поэтому исходный тестовый массив в функции OnStart распределялся через ArrayResize.
С принципом сортировки предлагается разобраться самостоятельно (или перевернуть пару страниц).
Для массивов с большим числом измерений (например, array[][][]) потребуется реализовать что-то аналогичное.
Теперь вспомним, что в предыдущем разделе мы поднимали вопрос о том, чтобы отсортировать массив структур по произвольному полю. Как мы знаем, стандартная ArraySort этого не умеет. Попробуем придумать "обходной маневр". За основу возьмем класс из файла ArraySwapSimple.mq5 из предыдущего раздела. Скопируем его в ArrayWorker.mq5 и кое-что добавим.
В методе Worker::process предусмотрим вызов вспомогательного метода сортировки arrayStructSort, причем сортируемое поле будем задавать по номеру (как это возможно, расскажем чуть ниже):
...
|
Теперь становится понятно, почему все предыдущие режимы (значения параметра mode) в методе process были отрицательными: нулевое и положительные значения зарезервированы для сортировки — они соответствуют номеру "колонки".
Идея сортировки массива структур взята из сортировки двумерного массива. Необходимо лишь каким-то образом отобразить одиночную структуру на одномерный массив (олицетворяющий ряд двумерного массива). Для этого сперва нужно определиться, какого типа должен быть массив.
Поскольку класс Worker уже является шаблонным, логично добавить еще один параметр в шаблон, чтобы тип массива можно было гибко задавать.
template<typename T,typename R>
|
После этого уместно вспомнить про объединения, которые позволяют наложить переменные разных типов друг на друга. Таким образом, мы приходим к такой хитрой конструкции:
union Overlay
|
В этом объединении тип структуры совмещен с массивом типа R, причем его размер автоматически рассчитывается компилятором на основе соотношения размеров двух типов T и R.
Внутри метода arrayStructSort теперь можно частично продублировать код из сортировки двумерного массива.
bool arrayStructSort(const int field)
|
Вместо массива с исходными структурами мы подготавливаем массив temp[][2] типа R, расширяем его до количества записей в array, и в цикле записываем по 0-му индексу каждого ряда "отображение" требуемого поля field из структуры, а по 1-му индексу — исходный индекс этого элемента.
"Отображение" основывается на том, что поля в структурах обычно каким-то образом выровнены, поскольку используют стандартные типы. Поэтому при правильно подобранном типе R можно обеспечить полное или частичное попадание полей в элементы массива в "оверлее".
Например, в стандартной структуре MqlRates первые 6 полей имеют размер 8 байтов и потому корректно накладываются на массив double или long (это кандидаты на шаблонный тип R).
struct MqlRates
|
С двумя последними полями дело обстоит сложнее. Если до поля spread еще можно добраться, используя тип int в качестве R, то поле real_volume оказывается по смещению, некратному его собственному размеру (из-за поля типа int, то есть 4 байта, перед ним). Это издержки конкретного метода. Его можно улучшить или изобрести другой.
Но вернемся к алгоритму сортировки. После заполнения массива temp его можно сортировать обычной функцией ArraySort, а потом использовать исходные индексы, чтобы сформировать новый массив с правильным порядком структур.
...
|
Перед выходом из функции мы снова используем ArraySwap, чтобы экономным способом подменить содержимое внутриобъектного массива array на новое и упорядоченное — полученное в локальном массиве result.
Проверим класс Worker в действии: в функции OnStart определим массив структур MqlRates и запросим у терминала несколько тысяч записей.
#define LIMIT 5000
|
Функция CopyRates будет описана в отдельном разделе. Пока нам достаточно знать, что она заполняет переданный массив rates котировками символа и таймфрейма текущего графика, на котором запущен скрипт. В макросе LIMIT указано количество запрашиваемых баров: необходимо удостовериться, что это значение не больше, чем настройка вашего терминала по количеству баров в каждом окне.
Для обработки полученных данных создадим объект worker с типами T=MqlRates и R=double:
Worker<MqlRates,double> worker(rates); |
Запуск сортировки можно осуществить инструкцией вида:
worker.process(offsetof(MqlRates, open) / sizeof(double)); |
Здесь используется оператор offsetof, чтобы узнать байтовое смещение поля open внутри структуры. Далее оно делится на размер double и получается правильный номер "колонки" для сортировки по цене open. Результат сортировки можно прочитать поэлементно или получить весь массив целиком:
Print(worker[i].open);
|
Обратите внимание, что получение массива методом get перемещает его из внутреннего массива array во внешний (переданный в качестве аргумента) с помощью ArraySwap. Поэтому после этого вызовы worker.process() бесполезны: в объекте worker уже нет данных.
Для упрощения запуска сортировки по разным полям была реализована вспомогательная функция sort:
void sort(Worker<MqlRates,double> &worker, const int offset, const string title)
|
Она выводит в журнал некий заголовок и первый и последний элементы отсортированного массива. С её помощью тестирование в OnStart для трех полей выглядит следующим образом:
void OnStart() { ... 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>
|
В результате запуска скрипта можем получить примерно следующее (зависит от настроек терминала, а именно на каком символе/таймфрейме выполняется):
Sorting by open price...
|
Здесь представлены данные для EURUSD,M15.
Приведенная реализация сортировки потенциально одна из самых быстрых, потому что использует встроенную ArraySort.
Если же сложности с выравниванием полей структуры или скептическое отношение к самому подходу с "отображением" структуры в массив вынуждают отказаться от данного метода (и тем самым, от функции ArraySort), остается проверенный способ "сделай всё сам".
Существует большое количество алгоритмов сортировки, которые легко адаптировать под MQL5. Один из варианто быстрой сортировки представлен в прилагаемом к книге файле QuickSortStructT.mqh. Это усовершенствованная версия QuickSortT.mqh, который мы использовали в разделе Сравнение строк. В нем метод Compare шаблонного класса QuickSortStructT сделан чисто виртуальным и должен быть переопределен в классе наследнике, чтобы возвращать аналог операции сравнения '>' для требуемого типа и его полей. Для удобства пользователей в заголовочном файле создан макрос:
#define SORT_STRUCT(T,A,F) \
|
С помощью него для сортировки массива структур по заданном полю достаточно написать одну инструкцию. Например:
MqlRates rates[];
|
Здесь выполняется сортировка массива rates типа MqlRates по цене high.
int ArrayBsearch(const type &array[], type value)
Функция ищет в числовом массиве заданное значение. Поддерживаются массивы всех встроенных числовых типов. Массив должен быть отсортирован по возрастанию по первому измерению, в противном случае результат будет некорректным.
Функция возвращает индекс совпадающего элемента (если их несколько, то индекс первого из них) или индекс ближайшего по значению элемента (если точного совпадения нет), то есть это может быть элемент как с большим, так и с меньшим значением, чем искомое. Если искомое значение меньше первого (минимального), то возвращается 0. Если искомое значения больше последнего (максимального), возвращается его индекс.
Индекс зависит от направления нумерации элементов в массиве: прямой (он начала к концу) или обратный (от конца к началу). Его можно узнать и изменить с помощью функций, описанных в разделе Направление индексации массивов как в таймсерии.
В случае ошибки выдается -1.
Для многомерных массивов поиск ограничивается первым измерением.
В скрипте ArraySearch.mq5 приведены примеры использования функции ArrayBsearch.
void OnStart()
|
Для трех предопределенных массивов (один из них пустой) выполняются следующие инструкции:
PRTS(ArrayBsearch(array, -1)); // 0
|
Далее во вспомогательной функции populateSortedArray производится заполнение массива numbers случайными значениями, причем массив постоянно поддерживается в отсортированном состоянии с помощью ArrayBsearch.
void populateSortedArray(const int limit)
|
Каждое новое значение попадает вначале в одноэлементный массив element, потому что так его проще вставлять в результирующий массив numbers с помощью функции ArrayInsert.
ArrayBsearch позволяет определить, в какое место следует вставить новое значение.
Результат работы функции выводится в журнал:
void OnStart()
|
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
|
Скрипт выведет в журнал примерно следующее (из-за случайной генерации данных каждый запуск будет отличаться):
22242 5909 21570 5850 18026 24740 10852 2631 24549 14635
|