От начального до среднего уровня: Очереди, списки и деревья (I)

Введение

В предыдущей статье, "От начального до среднего уровня: Словно мыльные пузыри" мы показали, как можно реализовать очень простой механизм сортировки. Хотя это может быть не так эффективно с точки зрения времени выполнения, во многих случаях данный подход подходит для самого широкого спектра ситуаций, когда целью является упорядочивание ряда данных и, таким образом, упрощение задачи их интерпретации и выполнения по ним простого поиска.

Механизм, описанный в предыдущей статье, не всегда действует самостоятельно. Чаще всего системы сортировки и поиска связаны с механизмами других типов. В данной статье мы рассмотрим один из этих механизмов.

Действительно, хотя мы всё ещё ориентируемся на базовые темы, но некоторым может показаться более продвинутым то, что будет рассмотрено здесь. Однако всё это связано с основами, которые должен знать каждый профессиональный программист.

Хорошо, чтобы начать правильно, перейдем к новой теме. Помните, что если у вас возникнут трудности с пониманием изложенного здесь или речь пойдет об элементах, которые не объясняются в этой статье, вам следует обратиться к предыдущим статьям. В них вы найдете всю необходимую информацию для понимания данной статьи.

Очереди, списки и деревья (I)

Существует тип материала, которым многие новички в итоге пренебрегают, поскольку считают его ненужным, хотя на самом деле его следует очень хорошо усвоить и понять. Данный материал, который недооценивают новички, имеет своей целью как раз обеспечение адекватного анализа и структурирования данных.

Внимание, уважаемый читатель! Нет никакого смысла изучать, как создать советника или даже простой индикатор, если вы не умеете правильно анализировать все данные, которые генерирует приложение. А теперь остановитесь и подумайте немного. Если вы поймете, как анализировать и классифицировать данные, которые получает приложение, вы сможете упростить его работу, и, как следствие, оно будет работать быстрее.

В настоящее время наблюдается большой ажиотаж вокруг машинного обучения и подобных тем. Однако даже системы искусственного интеллекта представляют собой не что иное, как простые классификаторы и системы статистического анализа данных. Ни при каких обстоятельствах в этих системах нет реального интеллекта, способного превзойти человеческое творчество и способность понимания определенной темы.

То есть, в конечном счете, хотя искусственный интеллект или машинное обучение, которые многие считают вершиной технологий, и могут казаться удивительными, они представляют собой не более чем алгоритмы, способные использовать ряд основ, которыми должен владеть каждый хороший программист. Понимание того, как и, главное, почему следует использовать именно эту модель реализации, а не другую, может иметь решающее значение. Овладеть этим искусством вы сможете только со временем, благодаря хорошей практике и опыту. Цель этих статей — не в том, чтобы сказать вам, когда использовать ту или иную модель реализации, а в том, чтобы представить эти модели и показать, как их можно использовать с помощью MQL5, чтобы MetaTrader 5 выдавал результаты.

Итак, существует определенная логическая последовательность, если это можно так назвать, в представлении материала, который мы здесь рассмотрим. И поскольку я хочу быть максимально наглядным, и некоторые новички могут не понять важности материала, давайте начнём с самой простой реализации, а именно с очередей.

В принципе, очередь эквивалентна массиву. Несмотря на это сходство, очередь может принимать различные формы, некоторые из которых сильно отличаются друг от друга. Таким образом, эти формы могут преследовать совершенно разные цели в зависимости от конкретного случая и способа их реализации. Именно из-за их большого сходства с массивами данных, многие новички часто путают их с массивами, и не без причины. Однако очереди не обязательно являются массивами, поскольку их назначение и способы обработки существенно отличаются от способов обработки и назначения самих массивов.

Поскольку очереди могут обладать весьма выраженными и в то же время довольно интересными характеристиками, и даже могут иметь весьма экзотические реализации в зависимости от ресурсов, предлагаемых языком, мы начнем с чего-то очень простого. Дело в том, что концепция и функционирование класса ещё не объяснены. Тем не менее, уже было изложено достаточно материала, чтобы мы могли реализовать различные структуры без особых трудностей. Таким образом, мы можем написать, или, точнее, реализовать показанный ниже код.

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. template <typename T> struct stFIFO
05. {
06.     private:
07. //+----------------+
08.         T   value[];
09. //+----------------+
10.     public:
11. //+----------------+
12.     T Restore(void)
13.     {
14.         T local = NULL;
15. 
16.         if (value.Size() > 0)
17.         {
18.             local = value[0];
19.             ArrayRemove(value, 0, 1);
20.         };
21.         return local;
22.     };
23. //+----------------+
24.     void Stock(T arg)
25.     {
26.         T local[1];
27.         local[0] = arg;
28.         ArrayInsert(value, local, value.Size());
29.     }
30. //+----------------+
31. };
32. //+------------------------------------------------------------------+
33. void OnStart(void)
34. {
35.     stFIFO <char> fifo;
36. 
37.     fifo.Stock(10);
38.     fifo.Stock(84);
39.     fifo.Stock(-6);
40. 
41.     Print(fifo.Restore());
42.     Print(fifo.Restore());
43.     Print(fifo.Restore());
44.     Print(fifo.Restore());
45. }
46. //+------------------------------------------------------------------+

Код 01

Итак, это наш первый шаг к более широкому пониманию этих структур, известных в программировании как очереди, списки и деревья. Теперь, уважаемый читатель, я хочу, чтобы вы обратили внимание на некоторые детали этого кода. Обратите внимание, что в строке 08 мы объявляем динамический массив, и этот массив может быть любого типа, как можно понять, просто взглянув на объявление в строке 08.

Этот массив не следует воспринимать так же, как те, что мы видели до настоящего момента. Причина кроется в функции строки 12 и процедуре строки 24. Данные процедуры и функции могут иметь любое название. На самом деле важно то, как они работают. Поэтому внимательно следите за дальнейшим объяснением. Это связано с тем, что в зависимости от задействованных функций и процедур то, что реализуется, может быстро меняться. Это может привести к изменению типа очереди или даже вызвать радикальные перемены, вплоть до того, что вместо очереди мы реализуем список или даже дерево.

Это самая простая часть. Если вы посмотрите на код функции Restore в строке 12, то увидите, что когда в массиве, объявленном в строке 08, есть данные, мы всегда сохраняем данные из индекса 0 этого массива, чтобы затем вернуть их вызывающей стороне. Самое важное здесь — это то, что именно будет делать строка 19. Её цель — удалить элемент с нулевым индексом. "Но подождите немного. Я не понял. Если мы всегда будем возвращать содержимое нулевого индекса, то при удалении этого самого индекса мы в итоге создадим определенную несогласованность в коде. Потому что при следующем вызове нулевой индекс не будет содержать никаких данных".

Что ж, уважаемый читатель, на самом деле всё произойдёт не совсем так. Как я уже говорил, многие новички путают понятия именно потому, что лишь поверхностно изучают код, не понимая происходящего внутри. Но я вам гарантирую, что вы скоро всё поймёте лучше. Просто внимательно послушайте то, что я сейчас объясню.

Итак, теперь мы знаем, что функция в строке 12 всегда будет возвращать содержимое, находящееся по нулевому индексу массива. А как насчет процедуры для строки 24? Что она делает? Хорошо, в этом случае данная процедура сохраняет отправленные ей данные в массиве. Однако эти же данные всегда будут храниться в конце массива. "Хм, я не понял. Не могли бы вы объяснить это немного подробнее?"

Да, уважаемый читатель. Вы уже знаете, что массив может содержать различные индексы, от нуля до любого значения. Когда первые данные отправляются в процедуру Stock в строке 24, они сохраняются по нулевому индексу. До этого момента всё в порядке, поскольку при использовании функции Restore мы будем считывать именно содержимое нулевого индекса. Именно здесь многие начинающие программисты путаются. Следующие данные, отправленные в Stock, будут сохранены в индексе один. Это происходит так, потому что данные по нулевому индексу уже имеются. Следующий элемент будет сохранен по индексу два по той же причине: данные уже есть по индексу 1. И так далее.

Однако в любой из этих ситуаций функция Restore всегда будет продолжать считывать содержимое нулевого индекса. Но вот здесь объяснение становится интересным. При использовании функции Restore индекс уменьшается на одну единицу. Так мы создаём очередь обработки. Чтобы увидеть это на практике, давайте посмотрим список команд процедуры OnStart, начиная со строки 33. При выполнении строк с 37 по 39 будет создана очередь, в точности в том порядке, в котором мы объявили значения. Напротив, при выполнении строк с 41 по 44 мы прочитаем то, что было вставлено в очередь. Это может показаться немного странным, но работает. Результат выполнения показан на следующем изображении.

Изображение 01

Обратите внимание, что на изображении 01 выделен другой элемент. Его возвращает функция Restore, поскольку в очереди больше нет элементов. Это происходит, потому что в строке 14 мы объявляем, какое значение будет возвращаться, когда в массиве, объявленном в строке 08, нет данных.

Можно четко заметить, что хотя в функции Restore мы всегда обращаемся к нулевому индексу, мы всё равно можем видеть данные, которые были вставлены в очередь. Этот тип очереди имеет особое название: FIFO — означает, первым вошёл — первым вышел. Попробуйте провести несколько тестов, чтобы лучше это понять. Например, добавить несколько значений в очередь, прочитать некоторые из них, а затем добавить ещё значения. Постарайтесь понять, как работает процесс чтения и написания.

Этот тип очереди очень полезен в различных ситуациях, когда нам необходимо анализировать данные в определенном порядке и нельзя упускать его из виду. Поэтому перед переходом ко следующему варианту целесообразно попрактиковаться и понять, как работает этот первый фрагмент кода.

В приведенном ниже коде, который можно увидеть чуть позже, мы создадим очередь другого типа с совершенно иной задачей, нежели та, которую мы рассматривали ранее. Но прежде чем пытаться понять, что произойдет в следующем коде, я настоятельно рекомендую вам, уважаемый читатель, уделить некоторое время тому, чтобы действительно разобраться в том, что было показано в коде 01, и в том, как это работает. Это позволит избежать путаницы с тем, что мы увидим в следующем коде.

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. template <typename T> struct stQueue
05. {
06.     private:
07. //+----------------+
08.         T       value[];
09.         uint    c_Pos,
10.                 c_Max;
11. //+----------------+
12.     public:
13. //+----------------+
14.     void Init(uint arg)
15.     {
16.         ArrayResize(value, arg + 1);
17.         c_Pos = c_Max = 0;
18.     }
19. //+----------------+
20.     bool GetInfo(T &arg)
21.     {
22.         if (c_Pos == c_Max)
23.             return false;
24.         c_Pos = (c_Pos < value.Size() - 1 ? c_Pos + 1 : 0);
25.         arg = value[c_Pos];
26. 
27.         return true;
28.     }
29. //+----------------+
30.     void Stock(const T arg)
31.     {
32.         c_Max = (c_Max < value.Size() - 1 ? c_Max + 1 : 0);
33.         c_Pos = (c_Pos == c_Max ? (c_Pos < value.Size() - 1 ? c_Pos + 1 : 0) : c_Pos);
34.         value[c_Max] = arg;
35.     }
36. //+----------------+
37. };
38. //+------------------------------------------------------------------+
39. void OnStart(void)
40. {
41.     stQueue <char> Queue;
42. 
43.     Queue.Init(5);
44. 
45.     Queue.Stock(10);
46.     Queue.Stock(84);
47.     Queue.Stock(-6);
48.     Queue.Stock(15);
49.     Queue.Stock(-35);
50.     Queue.Stock(40);
51.     Queue.Stock(-35);
52. 
53.     for (char info; Queue.GetInfo(info);)
54.         Print(info);
55. }
56. //+------------------------------------------------------------------+

Код 02

В этом коде 02 мы реализуем другой тип очереди, известный среди программистов как круговая очередь. Хотя такой тип реализации проще при использовании классов, ничто не мешает нам реализовать его с помощью ресурсов, уже описанных в предыдущих статьях. Когда реализация будет выполнена с помощью классов, вы увидите, что всё станет намного проще — как при её создании, так и при использовании представленной здесь реализации. Но это тема для другого разговора. Давайте сосредоточимся на том, что у нас есть прямо сейчас.

А теперь, уважаемый читатель, обратите ещё больше внимания. Если код 01 показался вам немного запутанным и сложным, то код 02 дезориентирует вас ещё больше, поскольку здесь мы делаем то, что многим может показаться чистым безумием. Хотя на практике это может быть очень полезно во многих случаях. Обратите внимание, что часть структуры, объявленной в строке 04 кода 02, весьма похожа на то, что было сделано в коде 01. В нём даже содержатся очень похожие фрагменты. Однако реализованный здесь вариант существенно отличается от того, что было сделано в коде 01. И не только это. В данном случае, при использовании кода 02, в отличие от кода 01, могут быть потеряны некоторые данные.

"Но подождите минутку. Как вообще возможно, чтобы данные были потеряны? Разве это не создаёт проблему для кода?" Нет, на самом деле нет, уважаемый читатель. Бывают ситуации, когда это ожидаемо, или, другими словами, мы можем потерять данные, не опасаясь, что это повлияет на конечный результат. Возможно, это покажется чем-то странным для многих из вас. Но давайте рассмотрим случай скользящих средних, которые используются на графике. Скользящие средние в некотором смысле функционируют как очередь значений, где самые старые отбрасываются. Например, 20-периодная скользящая средняя хранит 20 значений: первое — самое новое, а последнее будет отброшено, как только в очередь поступит более новое значение.

Теперь обратите внимание, потому что это важно. Поскольку у нас есть фиксированный интервал значений и они заменяются более новыми, мы должны называть этот тип структуры не списком, а очередью. Списки значений выполняют другую функцию; очереди же, напротив, имеют очень простую и практичную цель. Нередко эти два термина путают. Но чтобы у нас не возникло проблем с интерпретацией, мы называем показанную здесь структуру очередью. Хотя на первый взгляд это может показаться просто списком значений.

Хорошо, теперь обратите внимание, что в случае круговой очереди нам нужен способ ограничить диапазон или количество значений в очереди. Это делается с помощью процедуры, описанной в строке 14. Здесь мы указываем количество значений, которые будет содержать очередь; это число может быть любым значением больше нуля. Таким образом, в строке 16 мы выделяем достаточно памяти для того, чтобы динамический массив, созданный в строке 08, был сохранен в памяти. Однако, поскольку мы инициализируем нашу круговую очередь, нам также необходимо инициализировать два дополнительных значения. Это делается в строке 17. Таким образом, очередь сформирована и готова к приему или чтению данных.

Теперь наступает момент, когда многие люди, впервые столкнувшись с подобным подходом, часто испытывают сильное замешательство. Поскольку нам необходимо считывать элементы из очереди, мы реализовали функцию в строке 20. Эта функция возвращает любой элемент из очереди. Какой элемент? Ну, это зависит от обстоятельств, уважаемый читатель. Чтобы понять причину моего ответа, обратите внимание, что в строке 22 выполняется проверка. Если значение c_Pos, которое указывает на текущую позицию для чтения, равно значению c_Max, которое указывает на текущую позицию для записи, то элементов для возврата нет. Поэтому проверка строки 22 в некоторых случаях может вернуть значение false.

Если этого не происходит, это означает, что есть какое-то значение, доступное для чтения. В этой ситуации мы используем строку 24 для вычисления новой позиции чтения внутри очереди. Зачем нам нужен этот расчет? Разве не проще было бы увеличивать значение счетчика c_Pos? Нет, на самом деле нет, уважаемый читатель. Это связано с тем, что мы работаем с круговой очередью: если ее размер меньше полного диапазона значений типа uint, индекс необходимо циклически возвращать к началу, как это и делается в строке 24. В результате счетчик c_Pos будет указывать обратно на индекс 01 из массива, как только достигнет верхнего предела очереди. Вот так и создается круговая очередь. Остальная часть кода проста.

Итак, перейдем к процедуре в строке 30, поскольку она отвечает за весьма интересную и в то же время очень интригующую операцию. Обратите внимание на следующее: в строке 32 мы находим логику, очень похожую на логику строки 24, с той лишь разницей, что изменяется переменная, подлежащая корректировке. Но цель остается той же: вернуться к началу массива, как только в строке 16 будет достигнуто максимальное количество выделенных элементов.

"Подождите секунду, теперь ситуация действительно осложняется. Я говорю это, потому что замечаю, что такое же значение c_Max используется в строке 34 для указания индекса, по которому будет сохранено указанное нами значение. Однако вы утверждаете, что строка 32 будет периодически возвращаться к нулевому индексу. Ведь если у нас есть возможность хранить 20 элементов, а мы сохраняем 21 (то есть на один больше лимита, определенного в строке 16), сможем ли мы прочитать только один элемент?" Нет, уважаемый читатель. Мы по-прежнему сможем прочитать 20 уже сохранённых элементов. Однако первый элемент, сохраненный в очереди, будет заменен этим новым элементом — 21-м элементом. "Какое запутанное объяснение. Я не понимаю, как мы сможем это сделать". Не волнуйтесь, скоро вы всё поймёте. Но для того, чтобы гарантировать сохранение этой возможности чтения по всей круговой очереди, необходимо реализовать строку 33. Эта строка продвигает очередь вперёд без необходимости сдвигать элементы массива.

Обратите внимание: когда c_Max равно c_Pos, это означает, что очередь полностью заполнена. В противном случае эти значения никогда не будут равны. Поскольку очередь уже заполнена, мы принудительно перемещаем позицию c_Pos на следующую. Но для того, чтобы гарантировать, что c_Pos указывает на следующую допустимую позицию в очереди, мы используем второй тернарный оператор, обеспечивая тем самым соблюдение границ круговой очереди. Следовательно, этот второй тернарный оператор в точности совпадает с оператором в строке 24. Поскольку я знаю, что большинство из вас — новички и у вас могут возникнуть определенные трудности с пониманием кода 02, в приложении вы найдете немного измененный код. Код показан ниже:

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. template <typename T> struct stQueue
05. {
06.     #define macro_AdjustLimit(A) (A < value.Size() - 1 ? A + 1 : 0)
07. //+----------------+
08.     private:
09. //+----------------+
10.         T       value[];
11.         uint    c_Pos,
12.                 c_Max;
13. //+----------------+
14.     public:
15. //+----------------+
16.     void Init(uint arg)
17.     {
18.         ArrayResize(value, arg + 1);
19.         c_Pos = c_Max = 0;
20.     }
21. //+----------------+
22.     bool GetInfo(T &arg)
23.     {
24.         if (c_Pos == c_Max)
25.             return false;
26.         c_Pos = macro_AdjustLimit(c_Pos);
27.         arg = value[c_Pos];
28. 
29.         return true;
30.     }
31. //+----------------+
32.     void Stock(const T arg)
33.     {
34.         c_Max = macro_AdjustLimit(c_Max);
35.         c_Pos = (c_Pos == c_Max ? macro_AdjustLimit(c_Pos) : c_Pos);
36.         value[c_Max] = arg;
37.     }
38. //+----------------+
39.     #undef macro_AdjustLimit
40. //+----------------+
41. };
42. //+------------------------------------------------------------------+
43. void OnStart(void)
44. {
45.     stQueue <char> Queue;
46. 
47.     Queue.Init(5);
48. 
49.     Queue.Stock(10);
50.     Queue.Stock(84);
51.     Queue.Stock(-6);
52.     Queue.Stock(15);
53.     Queue.Stock(-35);
54.     Queue.Stock(40);
55.     Queue.Stock(-35);
56. 
57.     for (char info; Queue.GetInfo(info);)
58.         Print(info);
59. }
60. //+------------------------------------------------------------------+

Код 03

Код 03 делает то же самое, что и код 02. Единственное отличие заключается в определении макроса в строке 06, в данном коде 03. Однако это несколько упрощает понимание строки 33 из кода 02. Так происходит, потому что строка 35 из кода 03 читается гораздо легче. Хотя это та же строка, что и строка 33 из кода 02, её легче читать.

Однако нас больше интересует, как работает данная структура, как она создает и поддерживает так называемую круговую очередь. Для проверки этой структуры, создающей круговую очередь, мы используем содержимое процедуры OnStart.

Теперь давайте сосредоточимся на коде 03. Таким образом, мы сможем следовать указанным строкам. Первым делом мы определяем саму очередь. Определение приведено в строке 45. Далее мы определяем, сколько элементов будет содержать очередь. В данном случае это определяется в строке 47. Обратите внимание, что в данном случае мы определяем, что количество элементов будет МАКСИМУМ пять.

Теперь начинается самое интересное — использование круговой очереди. Для этого мы использовали строки с 49 по 55. Обратите внимание на следующее: у нас есть очередь, которая может содержать максимум пять элементов. Однако мы просим добавить в эту очередь семь элементов. Вопрос: что здесь произойдёт? Ответ: некоторые элементы будут исчезать и заменяться по мере продвижения очереди. Как мы можем быть в этом уверены? Итак, для этого мы используем строку 57, где появляется цикл, который на первый взгляд может показаться интригующим. Однако в другой статье я точно объяснил, как мы можем работать с командой for для создания циклов с весьма интересными целями. Это один из таких случаев. Обратите внимание, что сам цикл создает необходимые условия для выполнения и завершения. Нас интересует выполнение строки 58. Данная строка позволяет увидеть, какие элементы были удалены, а какие остались в очереди.

Итак, когда мы запускаем этот код 03 или код 02, мы получаем результат, показанный на следующем изображении:

Изображение 02

Вот и всё, уважаемый читатель. Я хочу, чтобы вы остановились на минуту и задумались о результате, показанном на этом изображении 02. И сравните это с содержимым кода 03, между строками 49 и 55. Вы понимаете, что здесь происходит? Можете ли вы выявить какую-либо связь между тем, что было показано в коде 01, где мы реализовали FIFO-очередь (первым пришел — первым ушел), и этой круговой очередью, которая реализуется в коде 03?  Да? Нет? Может быть. Вы, наверное, не видите этой взаимосвязи, но существует взаимосвязь между тем, что было объяснено в начале этой статьи, и тем, что мы видим здесь. Суть в следующем: первый элемент в очереди всегда отображается первым. Точно так же последний элемент очереди — это последний элемент, который отображается. В отличие от прежних методов, здесь мы ограничиваем количество элементов, которые могут находиться в очереди. Данное ограничение определяется в строке 47 из кода 03.

Вот тут-то и возникает путаница, которую многие не понимают. Когда мы начинаем программировать, мы теряем много времени, пытаясь создать или реализовать что-то. Однако весьма вероятно, что реализация того, что мы пытаемся сделать, уже где-то существует. Теперь подумайте о следующем: предположим, вы создаете советника для анализа скользящей средней с периодом X. "Зачем хранить более X значений цен? Это бессмысленно". Аналогично, нет смысла изменять данные о ценах, чтобы постоянно поддерживать актуальность массива с X значениями цен. Достаточно просто создать или реализовать такую структуру данных, как круговая очередь. Сама реализация позаботится о том, чтобы цены всегда оставались обновленными, практически без операций сдвига, так как используемые нами счетчики индексов сделают этот сдвиг за нас. Таким образом, исполняемый код работает намного быстрее и его проще поддерживать.

Заключительные идеи

В этой статье мы начали изучать одну из наименее известных тем среди начинающих программистов. Часто люди отчаянно хотят научиться программировать, но не пытаются понять основные понятия. На мой взгляд, правильное понимание этих концепций гораздо важнее и более необходимо, чем бесконечное написание кода. Потому что правильное понимание определенных концепций может помочь нам создавать код, который будет намного безопаснее, быстрее и проще в обслуживании.

Итак, уважаемый читатель, спокойно изучайте и применяйте на практике то, что вы узнали из этой статьи. Мне потребовалось немало времени, чтобы усвоить эти основы, которые я пытаюсь донести до вас. Когда я изучал эту тему, никто не обращал на неё особого внимания. Все требовали от нас только результатов, независимо от способа их достижения. Но здесь я показываю вам этот путь. Вам предстоит научиться ориентироваться в этом. Таким образом, ваше обучение будет максимально плавным и последовательным. Без спешки. Изучите и примените на практике то, что мы узнали из этой статьи. В следующей статье мы продолжим обсуждение очередей, списков и деревьев.

Файл	Описание
Code 01	Простая очередь
Code 02	Простая очередь