Рецепты MQL5 - Реализуем ассоциативный массив или словарь для быстрого доступа к данным
9 500
28
Оглавление
- ВВЕДЕНИЕ
- ГЛАВА 1. ТЕОРИЯ ОРГАНИЗАЦИИ ДАННЫХ
- ГЛАВА 2. ТЕОРИЯ ОРГАНИЗАЦИИ АССОЦИАТИВНОГО МАССИВА
- ГЛАВА 3. РАЗРАБОТКА АССОЦИАТИВНОГО МАССИВА НА ПРАКТИКЕ
- ГЛАВА 4. ИССЛЕДОВАНИЕ ПРОИЗВОДИТЕЛЬНОСТИ
- ГЛАВА 5. ДОКУМЕНТАЦИЯ КЛАССА CDICTIONARY
- ЗАКЛЮЧЕНИЕ
Введение
Эта статья описывает удобный класс для хранения информации - ассоциативный массив или словарь. Благодаря этому классу можно получать доступ к информации по ее ключу.
Ассоциативный массив напоминает обычный массив, однако вместо индекса он использует некий уникальный ключ, например, перечисление ENUM_TIMEFRAMES или какой-либо текст. Что конкретно является ключом - не важно, важно чтобы этот ключ был уникальным. Благодаря такому алгоритму хранения данных многие аспекты программирования значительно упрощаются.
Например, функция, которая бы принимала код ошибки и печатала текстовой эквивалент этой ошибки, могла бы выглядеть так:
//+------------------------------------------------------------------+ //| Выводит описание полученной ошибки в терминал. | //| Если идентификатор ошибки неизвестен, выводит "Unknown error" | //+------------------------------------------------------------------+ void PrintError(int error) { Dictionary dict; CStringNode* node = dict.GetObjectByKey(error); if(node != NULL) printf(node.Value()); else printf("Unknown error"); }
Позже мы разберем специфику данного кода.
Прежде чем подойти к непосредственному описанию внутренней логики ассоциативного массива, мы подробно рассмотрим два основных способа хранения данных - массивы и списки. Наш словарь будет базироваться именно на основе этих двух типах данных, поэтому специфику их работы необходимо хорошо представлять. Описанию типов данных посвящена глава 1. Вторая глава посвящена описанию ассоциативного массива и способа работы с ним.
Глава 1. Теория организации данных
1.1. Алгоритмы организации данных. Поиск оптимального контейнера для хранения данных
Поиск, хранение и представление информации - важнейшие функции, возложенные на современный компьютер. Как правило, наше взаимодействие с компьютером, это либо поиск какой-либо информации, либо ее создание и сохранение для дальнейшего использования. Информация - не абстрактное понятие. На практике за этим словом всегда скрывается конкретное понятие. Например, для любого трейдера источником информации является история котировок инструмента, на котором он совершает, либо планирует совершать сделки. Для программиста источником информации может быть документация по языку программирования, либо исходный код какой-либо программы.
Для людей, не связанных с программированием и трейдингом, информацией может послужить какой-либо графический файл, например, фотография, сделанная на их цифровых фотоаппаратах. Очевидно, что информация, представленная в качестве этих примеров, имеет различную структуру и свою собственную природу. Следовательно, алгоритмы хранения, представления и обработки этой информации будут различны.
Например, графический файл легче представить как двухмерную матрицу (двухмерный массив), каждый элемент или ячейка которой будет хранить информацию о цвете маленькой области изображения - пикселе. Данные о котировках имеют иную природу. По сути, это поток однотипных данных в формате OHLCV. Его лучше всего представить в виде массива или упорядоченной последовательности структур - специальном типе данных в языке программирования, объединяющих несколько типов данных вместе. Документация или исходный код программы - это, как правило, простой текст. Этот тип данных можно представить и хранить как упорядоченную последовательность строк, где каждая строка - это произвольная последовательность символов.
В зависимости от типа данных выбирается тот или иной тип контейнера, в котором эти данные хранятся. Контейнер для данных проще всего представить в терминах объектно-ориентированного программирования как некий класс, который хранит внутри себя эти данные и обладает специальными алгоритмами (методами), позволяющими ими удобно манипулировать. Существует несколько таких классов-контейнеров для хранения данных. В их основе лежит разная организация данных. Однако некоторые алгоритмы организации данных позволяют комбинировать разные парадигмы хранения информации, таким образом становится возможным объединить положительные свойства всех типов хранения вместе.
В зависимости от того, как предполагается работать с данными и какая природа данных лежит в их основе, выбирается тот или иной контейнер для их хранения, обработки и получения. Важно понимать, что одинаково эффективных контейнеров данных не существует. Слабые стороны одного контейнера данных являются обратной стороной его сильных сторон.
Например, в массиве можно очень быстро получить доступ к любому из его элементов. А вот вставить элемент в произвольное место массива занимает довольно трудоемкая операция, ведь в этом случае потребуется полная переразметка массива. Напротив, вставка элемента в односвязном списке эффективная и быстрая операция, а вот доступ к произвольному элементу занимает в нем много времени. Если требуется часто вставлять новые элементы, при этом доступ к самим элементам требуется нечастый, то предпочтительным контейнером будет односвязный список. Если требуется частый доступ к произвольным элементам, предпочтительным классом для организации данных будет массив.
Для того чтобы понимать, какой тип хранения данных выбрать, необходимо разбираться в том, как устроен тот или иной контейнер. Данная статья посвящена описанию ассоциативного массива или словаря - специального контейнера для хранения данных, в основе которого лежит комбинация массива со списком. Замечу, однако, что словарь может быть реализован по-разному в зависимости от конкретного языка программирования, его языковых средств, возможностей и принятых норм программирования.
Например, в C# словарь реализован иначе, нежели в C++. Не стоит ожидать и того, что в данной статье будет описана адаптированная реализация словаря на С++. Описываемая версия ассоциативного массива создана "с нуля" специально для языка программирования MQL5, учитывая специфику и общую практику программирования, принятую в нем. Однако общие свойства словарей и методы работы с ними должны быть схожими, несмотря на разную реализацию. В этом смысле описываемая версия обладает этими свойствами и методами в полной мере.
Мы будем создавать алгоритм словаря постепенно, параллельно рассуждая о природе алгоритмов хранения данных. В итоге, к концу статьи, мы получим завершенную версию алгоритма и полное понимание его работы.
Одинаково эффективных контейнеров для разных типов данных не существует. Рассмотрим простой пример: бумажную записную книжку. Она является своеобразным классом-контейнером в нашей реальной жизни. Все записи в ней производятся согласно заранее составленному списку, в данном случае алфавиту. Зная имя абонента, очень легко найти его номер, ведь в этом случае достаточно открыть книжку.
1.2. Массивы и прямая адресация к данным
Массив является самым простым и в тоже время наиболее эффективным по многим параметрам видом хранения информации. Массивом в программировании называется набор однотипных элементов, расположенных в памяти непосредственно друг за другом. Благодаря этим свойствам, можно рассчитать адрес каждого элемента массива.
В самом деле, ведь если все элементы имеют один и тот же тип, то у каждого элемента будет один и тот же размер, что и у всех остальных элементов. Так как данные в массиве располагаются непрерывно, то зная размер базового элемента, можно рассчитать адрес произвольного элемента и обратиться к нему напрямую. Общая формула расчета адреса зависит от типа данных и индекса.
Например, можно рассчитать адрес пятого элемента в массиве элементов типа uchar по общей формуле, вытекающей из свойств организации данных в массиве:
адрес произвольного элемента = адрес первого элемента + (индекс произвольного элемента в массиве * размер типа массива)
Адресация в массивах начинается с нуля, поэтому адрес первого элемента соответствует адресу элемента массива с индексом 0. Соответственно, пятый элемент будет иметь индекс 4. Предположим, что массив хранит элементы типа uchar, этот тип является базовым типом данных во многих языках программирования. Например, он есть во всех Си-подобных языках. MQL5 не является исключением. В массиве типа uchar каждый элемент занимает ровно 1 байт или 8 бит.
Например, адрес 5 элемента в массиве uchar согласно предыдущей формуле будет:
адрес 5 элемента = адрес первого элемента + (4 * 1 байт);
Иными словами, 5 элемент массива uchar будет на 4 байта старше самого первого элемента. Во время исполнения программы к каждому элементу массива можно обращаться по его непосредственному адресу. Такая адресная арифметика позволяет получить очень быстрый доступ к каждому элементу массива. Но у такой организации данных есть свои недостатки.
Одним из недостатков массива является то, что в нем невозможно хранить элементы разных типов. Это ограничение является следствием прямой адресации. Ведь разные типы данных различаются по своему размеру, а значит, узнать адрес конкретного элемента по формуле выше не представлялось бы возможным. Однако это ограничение можно изящно обойти, если в массиве хранить не сами элементы, а указатели на них.
Проще всего указатель представить как ссылку (как ярлыки в Windows). Указатель ссылается на некий объект, размещенный в памяти, при этом самим этим объектом он не является. Указатель в MQL5 может ссылаться только на класс. Классом в объектно-ориентированном программировании называется специальный тип данных, который может включать в себя произвольный набор данных и методов и создаваться самим пользователем для эффективного структурирования программы.
Каждый класс - это уникальный пользовательский тип данных. Указатели, ссылающиеся на разные классы, не могут размещаться в одном массиве. Однако указатель, независимо от того, на какой класс он ссылается, всегда имеет один и тот же размер, поскольку он содержит лишь адрес объекта в адресном пространстве операционной системы, которое является единым для всех размещенных в нем объектов.
1.3. Понятие узла на примере простого класса CObjectCustom
Теперь мы знаем достаточно для проектирования нашего первого универсального указателя. Идея в том, чтобы создать массив универсальных указателей, каждый из которых ссылался бы на свой индивидуальный тип. Фактические типы отличались бы друг от друга, однако благодаря тому, что на них ссылался бы один и тот же указатель, их можно было бы хранить в едином контейнере-массиве. Давайте создадим первую версию нашего указателя.
Этим указателем будет простейший класс, который мы назовем CObjectCustom:
class CObjectCustom
{
}; Класс, более простой, чем CObjectCustom, придумать было бы действительно сложно, ведь CObjectCustom не содержит никаких данных и методов. Но пока нам достаточно именно такой реализации.
Теперь воспользуемся одной из основных концепций объектно-ориентированного программирования: наследованием. Наследование позволяет устанавливать тождество между объектами специальным образом. Например, мы можем сказать компилятору о том, что любой класс является производным от CObjectCustom.
Например, класс людей (СHuman), класс торговых экспертов (CExpert) и класс погоды (CWeather) одновременно являются более общим понятием класса CObjectCustom. Возможно, в реальной жизни между этими понятиями фактической связи нет: погоду ничто не связывает с людьми, а торговых экспертов с погодой. Однако в мире программирования связи устанавливаем мы сами, и если для наших алгоритмов такие связи будут удобны, ничто не мешает нам их создать.
Аналогичным образом создадим еще несколько классов: класс автомобиля (CCar), класс, представляющий число (CNumber), класс ценового бара (CBar), класс котировок (CQuotes), класс компании MetaQuotes (CMetaQuotes), и класс, описывающий морской корабль (CShip). Как и в случае с предыдущими классами, реальной связи между ними нет, однако все они являются наследниками CObjectCustom.
Создадим нашу библиотеку классов этих объектов, объединив все эти классы в одном файле: ObjectsCustom.mqh:
//+------------------------------------------------------------------+ //| ObjectsCustom.mqh | //| Copyright 2015, Vasiliy Sokolov. | //| https://www.mql5.com | //+------------------------------------------------------------------+ #property copyright "Copyright 2015, Vasiliy Sokolov." #property link "https://www.mql5.com" //+------------------------------------------------------------------+ //| Базовый класс CObjectCustom | //+------------------------------------------------------------------+ class CObjectCustom { }; //+------------------------------------------------------------------+ //| Класс, описывающий человека. | //+------------------------------------------------------------------+ class CHuman : public CObjectCustom { }; //+------------------------------------------------------------------+ //| Класс, описывающий погоду. | //+------------------------------------------------------------------+ class CWeather : public CObjectCustom { }; //+------------------------------------------------------------------+ //| Класс, описывающий торгового эксперта. | //+------------------------------------------------------------------+ class CExpert : public CObjectCustom { }; //+------------------------------------------------------------------+ //| Класс, описывающий автомобиль. | //+------------------------------------------------------------------+ class CCar : public CObjectCustom { }; //+------------------------------------------------------------------+ //| Класс, описывающий число. | //+------------------------------------------------------------------+ class CNumber : public CObjectCustom { }; //+------------------------------------------------------------------+ //| Класс, описывающий ценовой бар. | //+------------------------------------------------------------------+ class CBar : public CObjectCustom { }; //+------------------------------------------------------------------+ //| Класс, описывающий котировки. | //+------------------------------------------------------------------+ class CQuotes : public CObjectCustom { }; //+------------------------------------------------------------------+ //| Класс, описывающий компанию MetaQuotes. | //+------------------------------------------------------------------+ class CMetaQuotes : public CObjectCustom { }; //+------------------------------------------------------------------+ //| Класс, описывающий корабль. | //+------------------------------------------------------------------+ class CShip : public CObjectCustom { };
Теперь настало время объединить все эти разрозненные классы в единый массив.
1.4. Массивы указателей на узлы на примере класса CArrayCustom
Для объединения нам понадобиться специально сконструированный массив.
В простейшем случае достаточно просто написать:
CObjectCustom array[];
Это строка создает динамический массив, который хранит элементы типа CObjectCustom. Благодаря тому, что все классы, придуманные нами в предыдущем разделе, происходят от CObjectCustom, мы можем хранить в этом массиве любой из этих классов. Например, мы можем разместить в нем людей, машины и корабли, но чтобы сделать это, простого объявления масcива CObjectCustom недостаточно.
Дело в том, что при классическом объявлении массива все его элементы заполняются автоматически в момент инициализации массива. Таким образом, после того, как мы этот массив объявим, все элементы в нем уже будут заняты классом CObjectCustom.
Убедиться в этом нам поможет небольшая модификация CObjectCustom:
//+------------------------------------------------------------------+ //| Базовый класс CObjectCustom | //+------------------------------------------------------------------+ class CObjectCustom { public: void CObjectCustom() { printf("Object #"+(string)(count++)+" - "+typename(this)); } private: static int count; }; static int CObjectCustom::count=0;
Запустим тестовый код в виде скрипта, проверяющий эту особенность:
//+------------------------------------------------------------------+ //| Test.mq5 | //| Copyright 2015, Vasiliy Sokolov. | //| https://www.mql5.com | //+------------------------------------------------------------------+ #property copyright "Copyright 2014, Vasiliy Sokolov." #property link "https://www.mql5.com" #property version "1.00" //+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { //--- CObjectCustom array[3]; }
В функции OnStart() мы инициализировали массив из трех элементов CObjectCustom.
Компилятор сразу заполнил этот массив соответствующими объектами, убедиться в этом можно, прочитав лог в терминале:
2015.02.12 12:26:32.964 Test (USDCHF,H1) Object #2 - CObjectCustom
2015.02.12 12:26:32.964 Test (USDCHF,H1) Object #1 - CObjectCustom
2015.02.12 12:26:32.964 Test (USDCHF,H1) Object #0 - CObjectCustom
Это значит, что массив заполняется самим компилятором, и мы уже не можем разместить в нем какие-либо другие элементы, например CWeather или CExpert.
Данный код не скомпилируется:
#include "ObjectsCustom.mqh" //+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { //--- CObjectCustom array[3]; CWeather weather; array[0] = weather; }
Компилятор выдаст ошибку:
'=' - structure have objects and cannot be copied Test.mq5 18 13
Это означает, что массив уже имеет объекты, и новые объекты не могут быть в него скопированы.
Однако выход из сложившейся ситуации есть! Для этого, как уже было сказано выше, достаточно работать не с объектами, а с указателями на них.
Перепишем код в функции OnStart() таким образом, чтобы он уже мог работать с указателями:
#include "ObjectsCustom.mqh" //+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { //--- CObjectCustom* array[3]; CWeather* weather = new CWeather(); array[0] = weather; }
Теперь код компилируется нормально, ошибки не появляются. Что же произошло? Мы заменили инициализацию массива CObjectCustom на инициализацию массива указателей на CObjectCustom.
В этом случае компилятор уже не создает новые объекты CObjectCustom при инициализации массива, а оставляет его пустым. Во-вторых, вместо объекта CWeather мы стали использовать указатель на этот объект. С помощью ключевого слова new мы создали объект CWeather и приравняли его к нашему указателю weather, после чего разместили указатель weather (но не сам объект) в массиве.
Теперь разместим оставшиеся объекты в массиве аналогичным образом.
Для этого напишем следующий код:
#include "ObjectsCustom.mqh" //+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { //--- CObjectCustom* arrayObj[8]; arrayObj[0] = new CHuman(); arrayObj[1] = new CWeather(); arrayObj[2] = new CExpert(); arrayObj[3] = new CCar(); arrayObj[4] = new CNumber(); arrayObj[5] = new CBar(); arrayObj[6] = new CMetaQuotes(); arrayObj[7] = new CShip(); }
Приведенный код будет работать, однако он довольно опасный, ведь мы манипулируем индексами массива напрямую.
Стоит нам ошибиться с выделенным размером для нашего массива arrayObj или обратиться не по тому индексу, наша программа завершится критической ошибкой. Однако для наших демонстрационных целей такой код подойдет.
Представим расположение этих элементов на схеме:
Рис. 1. Схема хранения данных в массиве указателей
Элементы, создаваемые оператором new, хранятся в специальном месте оперативной памяти, называемой кучей. Они находятся в ней в неупорядоченном виде, что хорошо видно на схеме выше.
Наш массив указателей arrayObj имеет строгую индексацию, что позволяет очень быстро получать доступ к любому из элементов по его индексу. Однако получить доступ к такому элементу недостаточно, ведь сам массив указателей не знает, на какой конкретно объект он указывает. Ведь указатель на CObjectCustom может указывать и на CWeather и на CBar и на CMetaQuotes, ведь все они являются также CObjectCustom. Поэтому, чтобы получить тип элемента, необходимо явное приведение объекта к его фактическому типу.
Например, это можно сделать так:
#include "ObjectsCustom.mqh" //+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { //--- CObjectCustom* arrayObj[8]; arrayObj[0] = new CHuman(); CObjectCustom * obj = arrayObj[0]; CHuman* human = obj; }
В данном коде мы создали объект CHuman и разместили его в массиве arrayObj под видом CObjectCustom. Затем мы извлекли CObjectCustom и преобразовали его в в CHuman, чем он по сути и является. В этом примере преобразование сработало без ошибок, т.к. мы сами запомнили тип. В реальных условиях при программировании крайне сложно отслеживать тип каждого объекта, так как таких типов может быть сотни, а количество объектов достигать миллионов.
Поэтому наш класс ObjectCustom необходимо снабдить дополнительным методом Type(), который возвращает модификатор фактического типа нашего объекта. Модификатор - это некое уникальное число, которое описывает наш объект позволяя обращаться к типу по имени. Например, мы можем определить модификаторы с помощью директивы #define препроцессора. Зная тип объекта, указанный модификатором, можно всегда безопасно преобразовывать его тип к фактическому. Итак, мы вплотную приблизились к созданию безопасных типов.
1.5. Контроль и безопасность типов
Как только мы начинаем преобразовывать один тип в другой, безопасность такого преобразования становится краеугольным камнем нашего программирования. Очень не хотелось бы, чтобы во время исполнения программы она вдруг завершилась критической ошибкой. Мы уже придумали, на чем будет базироваться безопасность наших типов - на специальных модификаторах. Зная модификатор, мы можем преобразовывать его в нужный тип, для этого необходимо дополнить наш класс CObjectCustom несколькими дополнениями.
Во-первых, введем идентификаторы типов, чтобы обращаться к ним по имени, для чего создадим отдельный файл с необходимыми перечислениями:
//+------------------------------------------------------------------+ //| Types.mqh | //| Copyright 2015, Vasiliy Sokolov. | //| https://www.mql5.com | //+------------------------------------------------------------------+ #property copyright "Copyright 2015, Vasiliy Sokolov." #property link "https://www.mql5.com" #define TYPE_OBJECT 0 // Общий для всех тип CObjectCustom #define TYPE_HUMAN 1 // Класс CHuman #define TYPE_WEATHER 2 // Класс CWeather #define TYPE_EXPERT 3 // Класс CExpert #define TYPE_CAR 4 // Класс CCar #define TYPE_NUMBER 5 // Класс CNumber #define TYPE_BAR 6 // Класс CBar #define TYPE_MQ 7 // Класс CMetaQuotes #define TYPE_SHIP 8 // Класс CShip
Теперь изменим код классов, добавив в CObjectCustom переменную, храняющую тип объекта в виде числа. Скроем ее в секции private, чтобы никто не смог ее изменить.
Помимо этого, добавим специальный конструктор, доступный для производных классов от CObjectCustom. Этот конструктор позволит объектам указывать их тип во время создания.
Общий код будет следующим:
//+------------------------------------------------------------------+ //| Базовый класс CObjectCustom | //+------------------------------------------------------------------+ class CObjectCustom { private: int m_type; protected: CObjectCustom(int type){m_type=type;} public: CObjectCustom(){m_type=TYPE_OBJECT;} int Type(){return m_type;} }; //+------------------------------------------------------------------+ //| Класс, описывающий человека. | //+------------------------------------------------------------------+ class CHuman : public CObjectCustom { public: CHuman() : CObjectCustom(TYPE_HUMAN){;} void Run(void){printf("Human run...");} }; //+------------------------------------------------------------------+ //| Класс, описывающий погоду. | //+------------------------------------------------------------------+ class CWeather : public CObjectCustom { public: CWeather() : CObjectCustom(TYPE_WEATHER){;} double Temp(void){return 32.0;} }; ...
Как видно, каждый тип, производный от CObjectCustom, теперь задает свой тип в своем конструкторе во время создания. После того, как тип задан, изменить его уже невозможно, т.к. поле, в котором он хранится, является приватным и недоступно никому, кроме самого CObjectCustom. Это оградит нас от неверных манипуляций с типами. Если класс не вызовет protected конструктор CObjectCustom, его тип будет типом по умолчанию - TYPE_OBJECT.
Итак, настало время научиться извлекать наши типы из arrayObj и правильно их обрабатывать. Для этого классы CHuman и CWeather снабдим открытыми методами Run() и Temp() соответственно. После того как мы извлечем класс из arrayObj, мы преобразуем его в нужный нам тип и начнем работать с ним соответствующим образом.
Если тип, который хранится в массиве CObjectCustom, нам неизвестен, мы пропустим его, написав соответствующее сообщение "unknown type":
#include "ObjectsCustom.mqh" //+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { //--- CObjectCustom* arrayObj[3]; arrayObj[0] = new CHuman(); arrayObj[1] = new CWeather(); arrayObj[2] = new CBar(); for(int i = 0; i < ArraySize(arrayObj); i++) { CObjectCustom* obj = arrayObj[i]; switch(obj.Type()) { case TYPE_HUMAN: { CHuman* human = obj; human.Run(); break; } case TYPE_WEATHER: { CWeather* weather = obj; printf(DoubleToString(weather.Temp(), 1)); break; } default: printf("unknown type."); } } }
Этот код выведет следующее сообщение:
2015.02.13 15:11:24.703 Test (USDCHF,H1) unknown type.
2015.02.13 15:11:24.703 Test (USDCHF,H1) 32.0
2015.02.13 15:11:24.703 Test (USDCHF,H1) Human run...
Итак, мы добились того, чего хотели. Теперь в массиве CObjectCustom мы можем хранить объекты любых типов, быстро получая к ним доступ по их индексу в массиве и правильно преобразовывая их к фактическому типу для работы. Однако многое нам по-прежнему не хватает, нам необходимо корректное удаление объектов после завершения выполнения программы, ведь объекты размещенные в куче нужно удалять самостоятельно с помощью специального оператора delete.
К тому же нам необходим механизм безопасной переразметки массива в случае его заполнения. Но не будем придумывать велосипед, в стандартную поставку MetaTrader 5 входят классы, реализующие все эти возможности.
В основе этих классов лежит универсальный класс-контейнер CObject. Аналогично нашему классу, он имеет метод Type(), возвращающий фактический тип класса, а также еще два важных указателя типа CObject: m_prev и m_next. О том, для чего они нужны, мы поговорим в следующем разделе, где уже на примере стандартного контейнера CObject и класса CList обсудим еще один способ хранения данных: двусвязный список.
1.6. Класс CList как пример двусвязного списка
У массива элементов произвольного типа лишь один существенный недостаток: вставить новый элемент в такой массив очень трудоемкая операция, особенно если элемент вставляется в середину. Ведь индексы идут друг за другом, поэтому при вставке требуется, во-первых, переразметить массив, чтобы общее количество элементов увеличилось на единицу, а затем перегруппировать все элементы, следуемые за вставляемым объектом, чтобы их индекс соответствовал новому значению.
Предположим, что мы имеем массив из 7 элементов и хотим вставить в него еще один новый элемент на 4 место, тогда приблизительная схема вставки будет следующая:
Рис. 2. Схема переразметки массива и вставки в него нового элемента
Есть схема хранения данных, которая делает вставку и удаление элементов очень быстрой и эффективной операцией. Такая схема называется односвязным или двусвязным списком. Список напоминает обычную очередь. Когда мы стоим в такой очереди, нам достаточно знать человека, за которым мы стоим (за кем стоит он сам, нам знать уже не нужно). Также нам не нужно знать человека, который стоит за нами, ведь он сам должен контролировать свое место в очереди.
Очередь - классический пример односвязного списка. Но списки бывают и двусвязными. В этом случае каждый человек в очереди знает не только того, за кем он стоит, но также и того, перед кем стоит он сам. В этом случае, опрашивая каждого человека, можно передвигаться как от конца очереди к началу, так и от начала очереди к концу.
Именно такой алгоритм предлагает нам стандартный CList, доступный в Стандартной библиотеке. Попробуем создать очередь из уже хорошо знакомых нам классов, только на этот раз все они будут происходить из стандартного CObject, а не нашего CObjectCustom.
Схематично это можно изобразить следующим образом:
Рис. 3. Схема организации двусвязного списка
Итак, вот исходный код, который создает такую схему:
//+------------------------------------------------------------------+ //| TestList.mq5 | //| Copyright 2015, Vasiliy Sokolov. | //| https://www.mql5.com | //+------------------------------------------------------------------+ #property copyright "Copyright 2014, Vasiliy Sokolov." #property link "https://www.mql5.com" #property version "1.00" #include <Object.mqh> #include <Arrays\List.mqh> class CCar : public CObject{}; class CExpert : public CObject{}; class CWealth : public CObject{}; class CShip : public CObject{}; //+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { //--- CList list; list.Add(new CCar()); list.Add(new CExpert()); list.Add(new CWealth()); list.Add(new CShip()); printf(">>> enumerate from begin to end >>>"); EnumerateAll(list); printf("<<< enumerate from end to begin <<<"); ReverseEnumerateAll(list); }
Наши классы приобретают два указателя от CObject: один ссылается на предыдущий элемент, а другой на следующий. У элемента в самом начале списка указатель на предыдущий элемент равен NULL. У элемента в самом конце списка указатель на следующий элемент также будет равен NULL. Зная это, можно перебирать элементы один за другим, тем самым перебирая всю очередь.
Перебором все элементов списка занимаются функции EnumerateAll() и ReverseEnumerateAll().
Первая перебирает список от начала до конца, вторая - с конца до самого начала, вот исходный код этих функций:
//+------------------------------------------------------------------+ //| Перебирает список от начала к концу, выводя порядковый номер | //| каждого элемента в терминал. | //+------------------------------------------------------------------+ void EnumerateAll(CList& list) { CObject* node = list.GetFirstNode(); for(int i = 0; node != NULL; i++, node = node.Next()) printf("Element at " + (string)i); } //+------------------------------------------------------------------+ //| Перебирает список от конца к началу, выводя порядковый номер | //| каждого элемента в терминал. | //+------------------------------------------------------------------+ void ReverseEnumerateAll(CList& list) { CObject* node = list.GetLastNode(); for(int i = list.Total()-1; node != NULL; i--, node = node.Prev()) printf("Element at " + (string)i); }
Как работает этот код? На самом деле все просто. В функции EnumerateAll() в самом начале мы получаем ссылку на первый узел. Затем в цикле for мы печатаем порядковый узел этого узла и переходим к следующему узлу командой node = node.Next(), не забывая при этом проитерировать текущий индекс элемента на единицу (i++). Перебор продолжается до тех пор, пока текущий узел node не станет равен NULL, за это ответствен код во втором блоке for: node != NULL.
Аналогично работает реверсивная версия этой функции ReverseEnumerateAll() с той лишь разницей, что она вначале получает последний элемент списка CObject* node = list.GetLastNode(). В цикле for она получает не следующий, а предыдущий элемент списка node = node.Prev().
После запуска этого кода мы получим следующее сообщение:
2015.02.13 17:52:02.974 TestList (USDCHF,D1) enumerate complete.
2015.02.13 17:52:02.974 TestList (USDCHF,D1) Element at 0
2015.02.13 17:52:02.974 TestList (USDCHF,D1) Element at 1
2015.02.13 17:52:02.974 TestList (USDCHF,D1) Element at 2
2015.02.13 17:52:02.974 TestList (USDCHF,D1) Element at 3
2015.02.13 17:52:02.974 TestList (USDCHF,D1) <<< enumerate from end to begin <<<
2015.02.13 17:52:02.974 TestList (USDCHF,D1) Element at 3
2015.02.13 17:52:02.974 TestList (USDCHF,D1) Element at 2
2015.02.13 17:52:02.974 TestList (USDCHF,D1) Element at 1
2015.02.13 17:52:02.974 TestList (USDCHF,D1) Element at 0
2015.02.13 17:52:02.974 TestList (USDCHF,D1) >>> enumerate from begin to end >>>
Вставка новых элементов в список очень проста, для этого достаточно указатели предыдущего и следующего элементов изменить так, чтобы они ссылались на новый элемент, а новый элемент ссылался на предыдущий и следующие объекты.
На схеме это выглядит проще, чем на словах:
Рис. 4. Вставка нового элемента в двусвязный список
Основным слабым моментом списка является невозможность обратиться к каждому его элементу по индексу.
Например, чтобы обратиться к CExpert на рис. 4, вначале необходимо получить доступ к CCar, а уже от него перейти к CExpert. То же относиться к CWeather. Он находится ближе к концу списка, чем к его началу, потому доступ к нему легче получить с конца. Для этого сначала необходимо обратиться к CShip, а затем уже к CWeather.
Переход по указателям - более медленная операция, чем прямая индексация. Современные центральные процессоры сильно заоптимизированы для работы именно с массивами. Поэтому на практике иногда выбор массива более предпочтителен, даже если список теоретически должен работать быстрее.
Глава 2. Теория организации ассоциативного массива
2.1. Ассоциативные массивы в повседневной жизни
В нашей повседневной жизни мы регулярно сталкиваемся с ассоциативными массивами, однако их работа кажется нам настолько очевидной, что их мы воспринимаем как нечто само собой разумеющееся. Самым простым примером ассоциативного массива или словаря является обычная телефонная книга. В ней каждый номер телефона ассоциирован с именем конкретного человека. Имя человека в такой книге - уникальный ключ, а номер телефона - простое числовое значение. Каждому контакту в телефонной книге может принадлежать более чем один номер телефона. Например, у человека может быть домашний, мобильный и рабочий телефонный номер.
По большому счету, номеров может быть неограниченное количество, а вот сам контакт является уникальным. Если в нашей телефонной книге будет, например, два контакта с именем "Александр", то это будет путать нас. Время от времени мы будем набирать не тот номер. Чтобы этого не происходило, ключи (в данном случае имена) должны быть уникальны. Но при этом словарь должен уметь разрешать коллизии и быть устойчив к их появлению. Если в телефонной книге появится два одинаковых имени, это ее не разрушит. Точно также и наш алгоритм должен уметь обрабатывать такие ситуации.
В реальной жизни мы пользуемся несколькими типами словарей. Например, телефонная книга - это словарь, в котором уникальная строка (имя абонента) является ключом, а номер - значением. Словарь иностранных слов устроен несколько иначе. В нем ключом является слово на английском, а слово-перевод является его значением. В основе обоих этих ассоциативных массивов лежат одни и те же способы работы с данными, поэтому наш создаваемый словарь должен быть универсальным и позволять хранить и сопоставлять любые типы друг с другом.
Точно также и в программировании бывает очень удобно создавать свои собственные словари и "записные книжки".
2.2. Простейшие ассоциативные массивы на основе оператора switch-case или простого массива
Создать простейший ассоциативный массив очень просто, для этого достаточно воспользоваться стандартными средствами языка MQL5, например, оператором switch или массивом.
Разберем такой код подробней:
//+------------------------------------------------------------------+ //| Возвращает строковое представление периода в зависимости от | //| переданного таймфрейма. | //+------------------------------------------------------------------+ string PeriodToString(ENUM_TIMEFRAMES tf) { switch(tf) { case PERIOD_M1: return "M1"; case PERIOD_M5: return "M5"; case PERIOD_M15: return "M15"; case PERIOD_M30: return "M30"; case PERIOD_H1: return "H1"; case PERIOD_H4: return "H4"; case PERIOD_D1: return "D1"; case PERIOD_W1: return "W1"; case PERIOD_MN1: return "MN1"; } return "unknown"; }
Оператор switch-case в данном случае работает как словарь. На каждое значение ENUM_TIMEFRAMES приходится строковое значение, описывающее этот период. Благодаря тому, что оператор switch является коммутируемым переходом, доступ к нужному варианту case происходит мгновенно, другие варианты case не перебираются. Поэтому данных код обладает высокой производительностью.
Однако его недостаток в том, что во-первых, на практике необходимо вручную заполнять все значения, которые нужно вернуть при том или ином значении ENUM_TIMEFRAMES. Второй недостаток заключается в том, что switch работает только с целочисленными переменными. Написать обратную функцию, которая возвращала бы тип таймфрейма в зависимости от переданной строки, было бы уже сложнее. Третий недостаток данного подхода в том, что данный метод недостаточно гибкий. Требуется заранее указать все возможные варианты. Однако часто бывает необходимым заполнять значения в словаре динамически по мере поступления данных.
Второй "лобовой" способ хранения пар ключ-значения заключается в создании массива, где в качестве индекса используется ключ, а в качестве элемента массива - само значение.
Например, попробуем решить аналогичную задачу: вернуть строковое представление таймфрейма:
//+------------------------------------------------------------------+ //| Здесь хранятся строковые значения, которые соответствуют | //| таймфрейму. | //+------------------------------------------------------------------+ string tf_values[]; //+------------------------------------------------------------------+ //| Добавляет в массив ассоциированные значения. | //+------------------------------------------------------------------+ void InitTimeframes() { ArrayResize(tf_values, PERIOD_MN1+1); tf_values[PERIOD_M1] = "M1"; tf_values[PERIOD_M5] = "M5"; tf_values[PERIOD_M15] = "M15"; tf_values[PERIOD_M30] = "M30"; tf_values[PERIOD_H1] = "H1"; tf_values[PERIOD_H4] = "H4"; tf_values[PERIOD_D1] = "D1"; tf_values[PERIOD_W1] = "W1"; tf_values[PERIOD_MN1] = "MN1"; } //+------------------------------------------------------------------+ //| Возвращает строковое представление периода в зависимости от | //| переданного таймрфейма. | //+------------------------------------------------------------------+ void PeriodToStringArray(ENUM_TIMEFRAMES tf) { if(ArraySize(tf_values) < PERIOD_MN1+1) InitTimeframes(); return tf_values[tf]; }
Этот код иллюстрирует обращение по индексу, где в качестве индекса указано перечисление ENUM_TIMFRAMES. Прежде чем вернуть значение, функция проверяет, заполнен ли массив нужными элементами, и если не заполнен, делегирует заполнение специальной функции InitTimeframes(). Недостатки этого метода те же, что и при использовании оператора switch.
К тому же данная организация словаря требует инициализировать массив очень большими значениями. Так, значение модификатора PERIOD_MN1 равно 49153. Значит, требуется выделить 49153 ячейки для хранения всего девяти таймфреймов. Все остальные ячейки остаются незаполненными. Это далеко не компактный способ располагать данные, однако он может подойти в случаях, когда перечисление занимает небольшой и последовательный диапазон чисел.
2.3. Преобразование базовых типов в уникальный ключ
Так как алгоритмы, используемые в словаре, одни и те же независимо от конкретных типов ключа и значения, нам необходимо произвести унификацию данных, чтобы разные типы данных обрабатывались единым алгоритмом. Наш алгоритм словаря будет достаточно универсальным и позволит хранить значения, в качестве ключа которых можно будет указать любой базовый тип, например int, enum, double или даже string.
В действительности любой базовый тип данных в MQL5 может быть представлен как некое беззнаковое число ulong. Например тип данных short или ushort - эта "укороченная" версия ulong.
Подразумевая, что в типе ulong хранится значение ushort, можно всегда делать явное безопасное преобразование типов:
ulong ln = (ushort)103; // Сохраняем в типе ulong значение ushort (103) ushort us = (ushort)ln; // Получаем из типа ulong значение ushort (103)
Тоже относиться к типам char и int, а также к их беззнаковым аналогам, ведь в ulong мы можем хранить любой тип, размер которого меньше или равен ulong. Типы datetime, enum и color в своей основе имеют 32 разрядное целое число uint, а значит, и их мы можем безопасно преобразовать в ulong. Тип bool принимает всего два значения - 0, означающий false, и 1, которое означает true. Таким образом, значения типа bool также можно хранить в переменной типа ulong. Кстати, именно на этом свойстве основаны многие системные функции в MQL5.
Например, функция AccountInfoInteger() в реальности возвращает целочисленное число типа long, которое может быть и номером счета типа ulong и булевским значением разрешения на торговлю ACCOUNT_TRADE_ALLOWED.
Однако в MQL5 есть три базовых типа, которые стоят особняком от целочисленных типов. Их нельзя напрямую преобразовать в целочисленный тип ulong. К ним относятся типы, представляющие числа с плавающей запятой double и float, а также строки. Однако с помощью несложных действий и их можно преобразовать в целочисленные уникальные ключи-значения.
Каждое число с плавающей точкой можно представить как некое основание с произвольной степенью, где и основание и степень хранятся раздельно в виде целочисленного значения. Приблизительно такой способ хранения используется в значениях double и float. Тип float использует 32 разряда для хранения мантиссы и степени числа, тип double - 64.
Если мы попробуем напрямую конвертировать их в тип ulong, произойдет простое округление числа. В этом случае числа 3.0 и 3.14159 дадут одно и тоже ulong число: 3. Такой вариант нам не подходит, т.к. нам потребуется разные ключи для этих двух безусловно разных чисел. На помощь нам приходит одно нетривиальное свойство, которое можно использовать в Си-подобных языках. Оно называется преобразование структур. Если две разные структуры имеют один и тот же размер, то можно выполнить их преобразование, конвертировав одну структуру в другую.
Разберем этот пример на двух структурах, одна из которых хранит значение типа ulong, а вторая - значение типа double:
struct DoubleValue{ double value;} dValue; struct ULongValue { ulong value; } lValue; //+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { //--- dValue.value = 3.14159; lValue = (ULongValue)dValue; printf((string)lValue.value); dValue.value = 3.14160; lValue = (ULongValue)dValue; printf((string)lValue.value); }
Приведенный код побайтово копирует структуру DoubleValue в структуру ULongValue. Поскольку их размер одинаков и расположение переменных совпадает, double значение dValue.value побайтово копируется в ulong переменную lValue.value.
После этого значение этой переменной выводиться на печать. Если изменить значение dValue.value на 3.14160, значение lValue.value также изменится.
Вот результат, который будет выведен функцией printf():
2015.02.16 15:37:50.646 TestList (USDCHF,H1) 4614256673094690983
2015.02.16 15:37:50.646 TestList (USDCHF,H1) 4614256650576692846
Тип float - укороченная версия типа double. Следовательно, для конвертации типа float в тип ulong можно вначале безопасно расширить тип float до double:
float fl = 3.14159f; double dbl = fl;
После этого нужно конвертировать double в тип ulong через конвертацию структур.
2.4. Хэширование строк и использование хэша в качестве ключа
В приведенных выше примерах ключами являлись одинаковые типы данных, а именно строки. Однако это не всегда может быть так. Например, первые три цифры телефона означают оператора телефонной сети, к которому принадлежит номер. В этом случае ключом являются именно три этих последних цифры. С другой стороны, каждую строку можно представить в виде уникального числа, где каждый разряд означает номер буквы в алфавите. Таким образом можно конвертировать строку в уникальное число, а его использовать как целочисленный ключ к значению, которое ассоциировано с ним.
Такой способ хорош, однако он все равно недостаточно универсален. Если в качестве ключа будет очень длинная строка, содержащая сотни символов, число будет невообразимо большим. Уместить его в простой переменной любого типа будет невозможно. Для решения подобных проблем нам приходит на помощь хэширующие функции. Хэширующая функция - это специальный алгоритм, который принимает на вход любой тип данных (например, строку), и выдает некое уникальное число, которое эту строку характеризует.
Если входные данные изменятся хотя бы на один символ, число будет совершенно другим. Числа, возвращаемые такой функцией, имеют фиксированный диапазон. Например, хэширующая функция Adler32() принимает в качестве параметра произвольную строку, а возвращает число в диапазоне от 0 до 2^32 степени. Это достаточно простая функция, однако она вполне подойдет для наших задач.
Приведем ее исходный код на MQL5:
//+------------------------------------------------------------------+ //| Принимает строку и возвращает хэширующее 32-битное число, | //| характеризующее эту строку. | //+------------------------------------------------------------------+ uint Adler32(string line) { ulong s1 = 1; ulong s2 = 0; uint buflength=StringLen(line); uchar char_array[]; ArrayResize(char_array, buflength,0); StringToCharArray(line, char_array, 0, -1, CP_ACP); for (uint n=0; n<buflength; n++) { s1 = (s1 + char_array[n]) % 65521; s2 = (s2 + s1) % 65521; } return ((s2 << 16) + s1); }
Давайте посмотрим, какие числа она выдает в зависимости от переданной ей строки.
Для этого напишем простой скрипт, который вызывает эту функцию и передает ей разные строки:
//+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { //--- printf("Hello world - " + (string)Adler32("Hello world")); printf("Hello world! - " + (string)Adler32("Hello world!")); printf("Peace - " + (string)Adler32("Peace")); printf("MetaTrader - " + (string)Adler32("MetaTrader")); }
Вывод этого скрипта показал следующее:
2015.02.16 13:29:12.576 TestList (USDCHF,H1) MetaTrader - 352191466
2015.02.16 13:29:12.576 TestList (USDCHF,H1) Peace - 91685343
2015.02.16 13:29:12.576 TestList (USDCHF,H1) Hello world! - 487130206
2015.02.16 13:29:12.576 TestList (USDCHF,H1) Hello world - 413860925
Как видно, каждой строке соответствует уникальное число. Обратите внимание на строки "Hello world" и "Hello world!" - они практически идентичны, единственная разница в них, это восклицательный знак в конце второй строки.
Однако числа, которые были получены с помощью Adler32(), в том и другом случае были совсем разные.
Мы научились преобразовывать тип string в беззнаковое число uint, и теперь вместо ключа типа string можем хранить его целочисленный хэш. Если у двух строк будет один и тот же хеш, то, скорее всего, это одна и также строка. Таким образом, ключом к значению будет не сама строка, а целочисленный хэш, который будет генерироваться на ее основе.
2.5. Вычисление индекса по ключу. Массив списков
Итак, теперь мы знаем о том, как любой базовый тип MQL5 преобразовать в беззнаковый тип ulong. Именно он будет служить нам фактическим ключом, которому будет соответствовать наше значение. Однако иметь уникальный ключ типа ulong недостаточно. Конечно, зная уникальный ключ каждого объекта, можно было бы организовать какой-нибудь примитивный способ его хранения на основе оператора switch-case или массива произвольной длины.
Такие способы были описаны в разделе 2.2 текущей главы. Однако все они недостаточно гибки и эффективны. В случае с оператором switch-case не представляется возможным описать все варианты в этом операторе.
Ведь если объектов будет десятки тысяч, нам придется еще на этапе компиляции описывать оператор switch, состоящий из этих десятков тысяч ключей, что невозможно. Второй способ - хранение в массиве, где индексом элемента является его ключ. Это позволяет при необходимости динамически переразмечать массив, добавляя в него нужные элементы. Тем самым, можно постоянно обращаться к нему по индексу, где индекс элемента будет его ключом.
Давайте попробуем написать набросок такого решения:
//+------------------------------------------------------------------+ //| Массив, в котором будут храниться строки по ключу. | //+------------------------------------------------------------------+ string array[]; //+------------------------------------------------------------------+ //| Добавляет строку в ассоциативный массив. | //| RESULTS: | //| Возвращает true, если строку удалось добавить, и false в | //| противном случае. | //+------------------------------------------------------------------+ bool AddString(string str) { ulong key=Adler32(str); if(key>=ArraySize(array) && ArrayResize(array,key+1)<=key) return false; array[key]=str; return true; }
В реальности приведенный код порождает больше проблем, чем решает. Предположим, что хэширующая функция выдаст очень большой хэш. Так как в приведенном примере индекс массива равен его хэшу, придется переразмечать массив, делая его гигантского размера. Не факт, что это получиться сделать. Вы готовы хранить одну единственную строку в контейнере, размер которого в оперативной памяти будет несколько гигабайт?
Второй проблемой является то, что в случае возникновения коллизии предыдущее значение будет просто перезаписано новым. Ведь не исключена вероятность того, что для двух разных строк функция Adler32() вернет один и тот же хэш-ключ. Вы готовы потерять часть своих данных, чтобы можно было быстро обратиться к ним по ключу? Ответ на все эти вопросы очевиден - конечно, нет. Чтобы этого не происходило, необходимо модифицировать алгоритм-хранения и разработать специальный гибридный контейнер на основе массива списков.
Массив списков объединяет лучшие свойства массива и списка. Эти два класса уже представлены в Стандартной библиотеке. Напомним, что массив позволяет очень быстро обращаться к своему произвольному элементу, но очень медленно переразмечается. Список, напротив, позволяет очень быстро добавлять и удалять новые элементы, однако доступ к каждому элементу в нем - весьма медленная операция.
Массив списков можно представить на следующей схеме:
Рис. 5. Схема массива списков
Из представленной схемы выше видно, что массив списков - это массив, где каждым элементом является список. Давайте посмотрим, какие преимущества дает эта схема. Во-первых, мы можем очень быстро обратиться к любому из списков по его индексу. Во-вторых, если мы будем хранить каждый элемент наших данных в списке, мы также очень быстро сможем добавлять или удалять элементы из списка, не прибегая к переразметке массива. Индекс массива может быть пустым или равным NULL. Это означает, что элементы, соответствующие этому индексу, еще не добавлены.
Совмещение массива и списка дает еще одну нетривиальную возможность. Мы можем хранить по одному индексу два и более элементов. Чтобы понять, зачем это нужно, давайте представим, что в массиве с 3 элементами требуется хранить 10 чисел. Очевидно, что чисел больше, чем самих элементов в массиве. Мы решим эту проблему, организовав хранение в массиве списков. Представим, что для хранения того или иного числа нам понадобиться один из трех списков, прикрепленных к одному из трех индексов массива.
Чтобы выяснить индекс списка, нам необходимо произвести найти остаток от деления нашего числа на количество элементов в массиве:
индекс массива = число % количество элементов в массиве;
Например, для числа 2 индекс списка, в котором оно будет хранится, будет: 2 % 3 = 2. Значит, число 2 мы будем хранить в списке по индексу 2. Число 3 мы будем хранить по индексу 3%3 = 0. Число 7 мы будем хранить по индексу 7%3 = 1. После того как индекс списка определен, достаточно добавить число в конец этого списка.
Чтобы извлечь число из списка, необходимо произвести похожие действия. Предположим, мы хотим извлечь число 7 из нашего контейнера, для этого надо определить, в каком списке нам надо его искать: 7%3=1. После того как мы определили, что число 7 может находится в списке по индексу 1, нам необходимо перебрать весь список, и если один из его элементов будет равен 7, вернуть это значение.
Раз мы можем хранить несколько элементов по одному индексу, нам не нужно создавать гиганские массивы для хранения малого количества данных. Предположим, что с цифрами 0-10 в массиве с тремя элементами нам необходимо хранить число 232 547 879. Это число также будет иметь свой индекс списка, равный двум (232 547 879 % 3 = 2).
Если мы заменим числа на хэши, мы сможем вычислить индекс для любого элемента, который нам требуется разместить в словаре. Ведь хэш - это и есть число. Более того, благодаря возможности хранения нескольких элементов в одном списке, нам не требуется уникальность хэша. Элементы с двумя одинаковыми хэшами попадут в один и тот же список. Когда необходимо будет достать элемент по ключу, мы просто сравним эти элементы и достанем тот, который будет соответствовать ключу.
Это возможно, так как у двух элементов с одинаковыми хэшами будут два разных уникальных ключа. Уникальность ключей может контролироваться функцией добавления элемента в словарь. Она просто не добавит новый элемент в случае, если ключ, которому он соответствует, уже содержится в словаре. Это похоже на контроль того, чтобы одному телефонному номеру соответствовал только один абонент.
2.6. Переразметка массива, минимизация длины списков
Чем меньше наш массив списков и чем больше количество добавляемых элементов, тем более длинные цепочки списков будет образовывать наш алгоритм. Из первой главы мы узнали, что доступ к элементу такой цепочки - неэффективная операция. Чем наш список будет короче, тем больше наш контейнер будет напоминать массив, доступ к каждому элементу которого осуществляется по индексу. Нам необходимо стремиться к коротким спискам и длинным массивам. Идеальным случаем для десяти элементов будет массив, состоящий из десяти списков, каждый из которых будет иметь по одному элементу.
Самым нежелательным вариантом будет массив длиной в десять элементов, состоящий из одного списка. Поскольку все элементы в наш контейнер будут добавляться динамически в течении выполнения программы, мы не будем знать заранее, какое количество элементов будет добавлено, поэтому нам необходимо продумать механизм динамической переразметки массива, при этом сделать так, чтобы количество цепочек в списках стремилось к одному элементу. Очевидно, что для этого необходимо поддерживать размер массива равным общему количеству элементов. При постоянном добавлении элементов потребуется постоянно переразмечать массив.
Осложняет ситуацию то, что помимо переразметки массива необходимо будет делать переразметку всех списков, ведь индекс списка, к которому может принадлежать элемент, может измениться после переразметки. Например, если массив содержит три элемента, то число 5 будет храниться во втором индексе (5%3 = 2). Если элементов будет уже 6, то число 5 будет храниться в пятом индексе (5%6=5). Таким образом, переразметка словаря - очень медленная операция. Ее необходимо совершать как можно реже. С другой стороны, если ее не делать вовсе, цепочки с каждым новым элементом будут становится все более длинными, а эффективность доступа к каждому элементу будет снижаться.
Можно создать алгоритм, реализующий разумный компромисс между количеством переразметок массива и средней длинной цепочки. Он будет основан на том, что каждая последующая переразметка будет увеличивать текущий размер массива вдвое. Так при первоначальном размере словаря в два элемента, первая переразметка увеличит его размер до 4 (2^2), вторая - до 8 (2^3), третья до 16 (2^3), шестнадцатая переразметка выделит размер уже для 65 536 цепочек (2^16). Каждая переразметка будет вызываться в случае, когда количество добавленных элементов совпадет с очередной степенью двойки. Таким образом, общее количество требуемой фактической оперативной памяти не будет более чем вдвое превышать чистую память, требуемую для хранения всех элементов. С другой стороны, логарифмический закон поможет избежать частых переразметок массива.
Аналогично, по мере удаления элементов из списка мы можем ужимать размер массива, тем самым экономя размер выделенной оперативной памяти.
Глава 3. Разработка ассоциативного массива на практике
3.1. Класс CDictionary на основе шаблонов, методы AddObject, DeleteObjectByKey и контейнер KeyValuePair
Создаваемый нами ассоциативный массив должен быть достаточно универсальным и позволять работать с ключами любых типов. В то же время в качестве значения мы будем использовать объекты, основанные на стандартном CObject. Учитывая, что в классах можно разместить любые базовые переменные, наш словарь будет универсальным решениям. Конечно, мы могли бы создать сразу несколько классов словарей. Для каждого базового типа использовался бы свой тип класса.
Например, можно было бы создать такие классы:
CDictionaryLongObj // Для хранения пар <ulong, CObject*> CDictionaryCharObj // Для хранения пар <char, CObject*> CDictionaryUcharObj // Для хранения пар <uchar, CObject*> CDictionaryStringObj // Для хранения пар <string, CObject*> CDictionaryDoubleObj // Для хранения пар <double, CObject*> ...
Однако базовых типов в MQL5 слишком много. К тому же каждую ошибку в коде пришлось бы исправлять множество раз, т.к. основной код для всех типов один и тот же. Для того чтобы избежать дублирования, мы будем использовать в своей работе шаблоны. Наш класс будет один, однако он будет одновременно обрабатывать сразу несколько типов данных. Для этого основные методы класса будут шаблонными.
Для начала создадим наш первый шаблонный метод Add(). Этот метод будет добавлять элемент с произвольным ключом в наш словарь. Сам класс словаря мы назовем CDictionary. Помимо самого элемента, словарь будет содержать массив указателей на списки CList, в этих цепочках мы будем хранить сами элементы:
//+------------------------------------------------------------------+ //| Ассоциативный массив или словарь, хранящий элементы в виде | //| <ключ - значение>, где ключом может являться любой базовый тип, | //| а значением - объект типа CObject. | //+------------------------------------------------------------------+ class CDictionary { private: CList *m_array[]; // Массив списков. template<typename T> bool AddObject(T key,CObject *value); }; //+------------------------------------------------------------------+ //| Добавляет в словарь элемент типа CObject с ключом T key | //| INPUT PARAMETRS: | //| T key - любой базовый тип, например int, double или string. | //| value - класс, производный от CObject. | //| RETURNS: | //| true, если элемент был добавлен и false в противном случае. | //+------------------------------------------------------------------+ template<typename T> bool CDictionary::AddObject(T key,CObject *value) { if(ContainsKey(key)) return false; if(m_total==m_array_size){ printf("Resize" + m_total); Resize(); } if(CheckPointer(m_array[m_index])==POINTER_INVALID) { m_array[m_index]=new CList(); m_array[m_index].FreeMode(m_free_mode); } KeyValuePair *kv=new KeyValuePair(key, m_hash, value); if(m_array[m_index].Add(kv)!=-1) m_total++; if(CheckPointer(m_current_kvp)==POINTER_INVALID) { m_first_kvp=kv; m_current_kvp=kv; m_last_kvp=kv; } else { m_current_kvp.next_kvp=kv; kv.prev_kvp=m_current_kvp; m_current_kvp=kv; m_last_kvp=kv; } return true; }
Метод AddObject() работает следующим образом. Вначале он проверяет, есть ли в нашем словаре элемент с ключом, который требуется добавить. Эту проверку осуществляет метод ContainsKey(). Если ключ key уже содержится в словаре, новый элемент добавлен не будет, т.к. это вызовет неопределенность, ведь тогда одному и тому же ключу будут соответствовать два элемента.
Затем метод узнает размер массива, в котором храняться цепочки CList, и если размер массива равен количеству элементов, то пора сделать переразметку. Эта задача делегируется методу Resize().
Следующие шаги просты. Если по рассчитанному индексу еще не существует цепочки CList, то она создается. Сам индекс рассчитывается ранее методом ContainsKey(). Он записывает рассчитанный индекс в переменную m_index. Затем метод добавляет новый элемент в конец списка. Однако перед этим элемент упаковывается в специальный контейнер KeyValuePair. Она базируется на стандартном CObject и расширяет его дополнительными указателями и данными. Устройство класса контейнера мы приведем чуть ниже. Помимо дополнительных указателей, контейнер также хранит оригинальный ключ объекта и его хэш.
Метод AddObject() представляет из себя шаблонный метод:
template<typename T> bool CDictionary::AddObject(T key,CObject *value);
Данная запись означает, что тип аргумента key является подстановочным и его фактический тип определяется на этапе компиляции.
Так, например, метод AddObject() в своем коде можно вызвать следующим образом:
//+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { CObject* obj = new CObject(); dictionary.AddObject(124, obj); dictionary.AddObject("simple object", obj); dictionary.AddObject(PERIOD_D1, obj); }
Любой из этих вызовов будет прекрасно работать благодаря шаблонам.
Противоположным по смыслу методу AddObject() является метод DeleteObjectByKey(). Он, наоборот, удаляет объект по его ключу из словаря.
Например, если можно удалить объект с ключом "Car" если он существует:
if(dict.ContainsKey("Car")) dict.DeleteObjectByKey("Car");
Код во многом аналогичен коду метода AddObject(), поэтому мы не будем его здесь приводить.
Методы AddObject() и DeleteObjectByKey() работают с объектами не напрямую. Вместо этого они запаковывают каждый объект в специальный класс-контейнер KeyValuePair, основанный на стандартном классе CObject. Этот контейнер обладает дополнительными указателями, позволяющими связывать элементы друг с другом, а также содержит оригинальный ключ и хэш, рассчитанный для объекта. Также контейнер проверяет на равенство переданный ключ, позволяя тем самым избежать коллизий. Об этом механизме мы поговорим в следующем разделе, посвященном методу ContainsKey().
А сейчас мы просто приведем содержимое этого класса:
//+------------------------------------------------------------------+ //| Контейнер для хранения элементов CObject | //+------------------------------------------------------------------+ class KeyValuePair : public CObject { private: string m_string_key; // Хранит строковый ключ double m_double_key; // Хранит ключ с плавающей запятой ulong m_ulong_key; // Хранит беззнаковый целочисленный ключ ulong m_hash; public: CObject *object; KeyValuePair *next_kvp; KeyValuePair *prev_kvp; template<typename T> KeyValuePair(T key, ulong hash, CObject *obj); ~KeyValuePair(); template<typename T> bool EqualKey(T key); ulong GetHash(){return m_hash;} }; template<typename T> KeyValuePair::KeyValuePair(T key, ulong hash, CObject *obj) { m_hash = hash; string name=typename(key); if(name=="string") m_string_key = (string)key; else if(name=="double" || name=="float") m_double_key = (double)key; else m_ulong_key = (ulong)key; object=obj; } KeyValuePair::~KeyValuePair() { delete object; } template<typename T> bool KeyValuePair::EqualKey(T key) { string name=typename(key); if(name=="string") return key == m_string_key; if(name=="double" || name=="float") return m_double_key == (double)key; else return m_ulong_key == (ulong)key; }
3.2. Динамическая идентификация типов на основе typename, взятие хэша
Теперь, когда мы научились принимать в своих методах произвольные типы, нам необходимо будет определить их хэш. Для всех целочисленных типов хэш будет равен значению самого этого типа, расширенному до типа ulong.
Для того чтобы рассчитать хэш для типов double и float, необходимо использовать приведение через структуры, которое описывалось в разделе "Преобразование базовых типов в уникальный ключ". Для строк необходимо использовать хэширующую функцию. Так или иначе, каждый тип данных требует своего метода взятия хэша. Значит, все, что нам нужно - это определить переданный тип и в зависимости от его типа вызвать тот или иной метод взятия хэша. Для этих целей нам понадобиться специальная директива typename.
Метод, который определяет хэш на основе ключа, называется GetHashByKey().
Вот его содержимое:
//+------------------------------------------------------------------+ //| Рассчитывает хэш на основе переданного ключа. Ключом может быть | //| любой базовый MQL тип. | //+------------------------------------------------------------------+ template<typename T> ulong CDictionary::GetHashByKey(T key) { string name=typename(key); if(name=="string") return Adler32((string)key); if(name=="double" || name=="float") { dValue.value=(double)key; lValue=(ULongValue)dValue; ukey=lValue.value; } else ukey=(ulong)key; return ukey; }
Его логика проста. С помощью директивы typename метод получает строковое название переданного типа. Если в качестве ключа передается строка, typename вернет значение "string", если значение int - вернет "int". Также будет и для любого другого типа. Таким образом, все, что нам остается, это сравнить возвращаемое значение с нужными строковыми константами, и если оно совпадет с одной из этих констант, вызвать соответствующий обработчик.
Если ключ является типом string, то его хэш рассчитывает функция Adler32(). Если ключом является вещественные типы, то они преобразуются в хэш с помощью конвертирования структур. Все прочие типы просто явно преобразуются в тип ulong, который и становиться хэшем.
3.3. Метод ContainsKey(). Противодействие коллизиям хеша
Основной проблемой любой хеширующей функции является появления коллизий - ситуаций, когда разные ключи дают один и тот же хеш. Если такая ситуация возникнет, и их хэши совпадут, возникнет неоднозначность - оба объекта будут одинаковы с точки зрения логики словаря. Чтобы этого не происходило, необходимо проверять фактический тип ключа с запрашиваемым и возвращать положительное значение только в том случае, если фактические ключи совпадают. Именно таким образом работает метод ContainsKey(). Он возвращает true, если объект с запрашиваемым ключом существует и false в противном случае.
Наверное, это самый полезный и удобный метод всего словаря. Он позволяет узнать, существует ли объект с определенным ключом:
#include <Dictionary.mqh> CDictionary dict; //+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { if(dict.ContainsKey("Car")) printf("Car always exists."); else dict.AddObject("Car", new CCar()); }
Например, код выше проверяет наличие объекта типа CCar и добавляет CCar, если его там еще нет. Также этот метод позволяет контролировать уникальность ключа каждого нового добавляемого объекта.
Если ключ объекта уже используется, метод AddObject() просто не добавит новый объект в словарь.
template<typename T> bool CDictionary::AddObject(T key,CObject *value) { if(ContainsKey(key)) return false; ... }
Этот метод настолько универсальный, что активно используется как самими пользователями, так и другими методами класса.
Приведем его содержимое:
//+------------------------------------------------------------------+ //| Проверяет, содержит ли словарь ключ произвольного типа T. | //| RETURNS: | //| Возвращает true, если объект с таким ключом уже существует | //| и false в противном случае. | //+------------------------------------------------------------------+ template<typename T> bool CDictionary::ContainsKey(T key) { m_hash=GetHashByKey(key); m_index=GetIndexByHash(m_hash); if(CheckPointer(m_array[m_index])==POINTER_INVALID) return false; CList *list=m_array[m_index]; m_current_kvp=list.GetCurrentNode(); if(m_current_kvp == NULL)return false; if(m_current_kvp.EqualKey(key)) return true; m_current_kvp=list.GetFirstNode(); while(true) { if(m_current_kvp.EqualKey(key)) return true; m_current_kvp=list.GetNextNode(); if(m_current_kvp==NULL) return false; } return false; }
Сначала метод находит хеш объекта с помощью GetHashByKey(). Затем на основе хеша он получает индекс цепочки CList, в которой может располагаться объект с данным хэшем. Если такой цепочки еще нет, то и объекта с таким ключом точно не существует - в этом случае он досрочно завершит свою работу и вернет false (объекта с таким ключом нет). Если цепочка существует, начинается ее перебор.
Каждым элементом этой цепочки является объект типа KeyValuePair, которому предлагается сравнить фактический переданный ключ с ключом, который хранит сам элемент. Если ключи равны, метод возвращает true (объект с таким ключом уже существует). Код, делающий проверку на равенство ключей, приведен в листинге класса KeyValuePair.
3.4. Динамическое выделение и освобождение памяти
За динамическое выделение и освобождение памяти в нашем ассоциативном массиве отвечает метод Resize(). Этот метод вызывается каждый раз, когда количество элементов становиться равным размеру массива m_array. Также он вызывается при удалении элементов из списка. Этот метод переопределяет индексы хранения для всех элементов, поэтому работает крайне медленно.
Чтобы избежать частого вызова метода Resize(), количество выделяемой памяти каждый раз увеличивается вдвое от предыдущего значения. Иными словами, для того чтобы словарь мог вместить в себя 65 536 элементов, метод Resize() будет вызван всего 16 раз (2^16). После двадцатого вызова словарь будет вмещать в себя уже более миллиона элементов (1 048 576). За экспоненциальный рост требуемых элементов отвечает метод FindNextLevel().
Вот исходный код метода Resize():
//+------------------------------------------------------------------+ //| Переразмечает контейнер хранения данных | //+------------------------------------------------------------------+ void CDictionary::Resize(void) { int level=FindNextLevel(); int n=level; CList *temp_array[]; ArrayCopy(temp_array,m_array); ArrayFree(m_array); m_array_size=ArrayResize(m_array,n); int total=ArraySize(temp_array); KeyValuePair *kv=NULL; for(int i=0; i<total; i++) { if(temp_array[i]==NULL)continue; CList *list=temp_array[i]; int count=list.Total(); list.FreeMode(false); kv=list.GetFirstNode(); while(kv!=NULL) { int index=GetIndexByHash(kv.GetHash()); if(CheckPointer(m_array[index])==POINTER_INVALID) m_array[index]=new CList(); list.DetachCurrent(); m_array[index].Add(kv); kv=list.GetCurrentNode(); } delete list; } int size=ArraySize(temp_array); ArrayFree(temp_array); }
Этот метод работает как в большую, так и в меньшую сторону. Когда элементов гораздо меньше фактического размера массива, запускается код сжатия элементов в более компактный массив. И наоборот, когда размера текущего массива уже не хватает, массив переразмечается на большее количество элементов. Этот код требует больших вычислительных ресурсов.
Требуется переразметить массив, предварительно переместив из него все элементы во временную копию массива, затем требуется рассчитать новые индексы для каждого элемента и уже тогда разместить эти элементы на новых местах.
3.5. Последние штрихи - перебор объектов и удобный индексатор
Итак, наш класс CDictionary уже содержит основные методы для работы с ним. Наличие объекта с определенным ключом можно узнать при помощи метода ContainsKey(). Мы можем добавить объект в словарь с помощью метода AddObject(). Также мы можем удалить объект из словаря с помощью метода DeleteObjectByKey().
Теперь нам осталось сделать удобный перебор всех элементов контейнера. Как нам уже известно, все элементы в нем хранятся упорядоченно по ключу, однако было бы удобно делать перебор всех элементов в том порядке, в каком мы добавили их в ассоциативный массив. Для этого в классе-контейнере KeyValuePair содержаться два дополнительных указателя на предыдущий и последующий добавленный элемент типа KeyValuePair. Благодаря этим указателям можно делать перебор последовательно.
Например, если мы добавили в наш ассоциативный массив объекты в следующем порядке:
CNumber --> CShip --> CWeather --> CHuman --> CExpert --> CCar
то перебор этих элементов также будет последовательным, т.к. он будет осуществляться с помощью переходов по ссылкам на KeyValuePair, как это показано на рис. 6:
Рис. 6. Схема последовательного перебора массива
Для осуществления такого перебора используются пять методов.
Приведем их содержимое и краткую аннотацию:
//+------------------------------------------------------------------+ //| Возвращает текущий объект. Если объект не выбран, возвращает | //| NULL | //+------------------------------------------------------------------+ CObject *CDictionary::GetCurrentNode(void) { if(m_current_kvp==NULL) return NULL; return m_current_kvp.object; } //+------------------------------------------------------------------+ //| Возвращает предыдущий объект. После вызова метода текущий | //| объект становится предыдущим. Если объект не выбран, возвращает | //| NULL. | //+------------------------------------------------------------------+ CObject *CDictionary:: GetPrevNode(void) { if(m_current_kvp==NULL) return NULL; if(m_current_kvp.prev_kvp==NULL) return NULL; KeyValuePair *kvp=m_current_kvp.prev_kvp; m_current_kvp=kvp; return kvp.object; } //+------------------------------------------------------------------+ //| Возвращает следующий объект. После вызова метода текущий | //| объект становится следующим. Если объект не выбран, возвращает | //| NULL. | //+------------------------------------------------------------------+ CObject *CDictionary::GetNextNode(void) { if(m_current_kvp==NULL) return NULL; if(m_current_kvp.next_kvp==NULL) return NULL; KeyValuePair *kvp=m_current_kvp.next_kvp; m_current_kvp=kvp; return kvp.object; } //+------------------------------------------------------------------+ //| Возвращает первый узел в списке узлов. Если в словаре узлов нет, | //| возвращает NULL. | //+------------------------------------------------------------------+ CObject *CDictionary::GetFirstNode(void) { if(m_first_kvp==NULL) return NULL; m_current_kvp=m_first_kvp; return m_first_kvp.object; } //+------------------------------------------------------------------+ //| Возвращает последний узел в списке узлов. Если в словаре узлов | //| нет, возвращает NULL. | //+------------------------------------------------------------------+ CObject *CDictionary::GetLastNode(void) { if(m_last_kvp==NULL) return NULL; m_current_kvp=m_last_kvp; return m_last_kvp.object; }
Благодаря этим простым итераторам можно последовательно осуществлять перебор добавленных элементов:
class CStringValue : public CObject { public: string Value; CStringValue(); CStringValue(string value){Value = value;} }; CDictionary dict; //+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { dict.AddObject("CNumber", new CStringValue("CNumber")); dict.AddObject("CShip", new CStringValue("CShip")); dict.AddObject("CWeather", new CStringValue("CWeather")); dict.AddObject("CHuman", new CStringValue("CHuman")); dict.AddObject("CExpert", new CStringValue("CExpert")); dict.AddObject("CCar", new CStringValue("CCar")); CStringValue* currString = dict.GetFirstNode(); for(int i = 1; currString != NULL; i++) { printf((string)i + ":\t" + currString.Value); currString = dict.GetNextNode(); } }
Данный код выведет строковые значения объектов в том порядке, в котором они были добавлены в словарь:
2015.02.24 14:08:29.537 TestDict (USDCHF,H1) 6: CCar
2015.02.24 14:08:29.537 TestDict (USDCHF,H1) 5: CExpert
2015.02.24 14:08:29.537 TestDict (USDCHF,H1) 4: CHuman
2015.02.24 14:08:29.537 TestDict (USDCHF,H1) 3: CWeather
2015.02.24 14:08:29.537 TestDict (USDCHF,H1) 2: CShip
2015.02.24 14:08:29.537 TestDict (USDCHF,H1) 1: CNumber
Чтобы вывести все элементы от конца к началу, достаточно заменить две строчки кода в функции OnStart():
CStringValue* currString = dict.GetLastNode(); for(int i = 1; currString != NULL; i++) { printf((string)i + ":\t" + currString.Value); currString = dict.GetPrevNode(); }
Соответственно, выводимые значения инвертируются:
2015.02.24 14:11:01.021 TestDict (USDCHF,H1) 6: CNumber
2015.02.24 14:11:01.021 TestDict (USDCHF,H1) 5: CShip
2015.02.24 14:11:01.021 TestDict (USDCHF,H1) 4: CWeather
2015.02.24 14:11:01.021 TestDict (USDCHF,H1) 3: CHuman
2015.02.24 14:11:01.021 TestDict (USDCHF,H1) 2: CExpert
2015.02.24 14:11:01.021 TestDict (USDCHF,H1) 1: CCar
Глава 4. Исследования производительности
4.1. Пишем тесты и измеряем производительность
Измерение производительности - важный элемент в проектировании класса, особенно если этот класс является классом для хранения данных. Ведь в этом случае он может использоваться самыми разными программами. Их алгоритмы могут быть критичны к скорости и требовать высокой производительности. Вот почему так важно уметь измерять производительность и искать "слабые места" подобных алгоритмов.
Для начала мы напишем простой тест, измеряющий скорость добавления и извлечения элементов из словаря. Этот тест мы напишем в виде обычного скрипта.
Его исходный код прикреплен ниже:
//+------------------------------------------------------------------+ //| TestSpeed.mq5 | //| Copyright 2015, Vasiliy Sokolov. | //| https://www.mql5.com | //+------------------------------------------------------------------+ #property copyright "Copyright 2015, Vasiliy Sokolov." #property link "https://www.mql5.com" #property version "1.00" #include <Dictionary.mqh> #define BEGIN 50000 #define STEP 50000 #define END 1000000 //+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { //--- CDictionary dict(END+1); for(int j=BEGIN; j<=END; j+=STEP) { uint tiks_begin=GetTickCount(); for(int i=0; i<j; i++) dict.AddObject(i,new CObject()); uint tiks_add=GetTickCount()-tiks_begin; tiks_begin=GetTickCount(); CObject *value=NULL; for(int i= 0; i<j; i++) value = dict.GetObjectByKey(i); uint tiks_get=GetTickCount()-tiks_begin; printf((string)j+" elements. Add: "+(string)tiks_add+"; Get: "+(string)tiks_get); dict.Clear(); } }
Этот код последовательно добавляет элементы в словарь, а затем обращается к ним, измеряя их скорость. Затем каждый элемент удаляется с помощью метода DeleteObjectByKey(). Скорость измеряется с помощью системной функции GetTickCount().
С помощью этого скрипта был составлен график, описывающий временные зависимости этих трех основных методов:
Рис. 7. Точечный график зависимости между количеством элементов и временем работы методов в миллисекундах
Как видно, основное время уходит на размещение и удаление элементов в словаре. Тем не менее, ожидалось, что удаление элементов будет происходить гораздо быстрее. Мы постараемся улучшить производительность этого метода, используя профилировщик кода. Об этой методике будет написано в следующем разделе.
Обратите внимание на график метода ContainsKey() - он линейный. Это значит, что на доступ к произвольному элементу требуется примерно одинаковое количество времени, независимо от количества самих элементов в массиве. Это именно то свойство, которым должен обладать настоящий ассоциативный массив.
Для иллюстрации данного свойства изобразим график зависимости между среднем временем доступа к одному элементу и количеством элементов в массиве:
Рис. 8. Среднее время доступа к одному элементу с помощью метода ContainsKey()
4.2. Профилирование кода. Скорость против автоматического управления памятью
Профилирование кода - специальная техника, позволяющая измерять временные затраты всех функций. Для профилирования достаточно запустить любую MQL5-программу, нажав на специальный значок 
в редакторе MetaEditor.
Точно также поступим и мы, отправив наш скрипт на профилирование. После некоторого времени наш скрипт выполниться, а мы получим временной профиль всех методов, которые были выполнены в процессе работы скрипта. На скриншоте ниже видно, что основное время ушло на выполнение 3 методов: AddObject() (40% всего времени), GetObjectByKey() (7% всего времени) и DeleteObjectByKey() (53% всего времени):
Рис. 9. Профилирование кода в функции OnStart()
В свою очередь более 60% вызова DeleteObjectByKey() ушло на вызов метода Compress().
Сам этот метод практически пустой, основное время в нем уходит на вызов метода Resize().
Вот его содержимое:
CDictionary::Compress(void) { double koeff = m_array_size/(double)(m_total+1); if(koeff < 2.0 || m_total <= 4)return; Resize(); }
Проблема ясна. При удалении элементов время от времени запускается медленный метод Resize(), который снижает размер массива, динамически высвобождая память.
Если мы хотим, чтобы удаление элементов происходило быстрее, необходимо отключить этот метод. Например, можно ввести в класс специальный метод AutoFreeMemory(), устанавливающий флаг компрессии. По умолчанию он будет установлен, в этом случае компрессия будет происходить автоматически. В случае, если нам нужна будет дополнительная скорость, компрессию будем делать вручную в подходящий момент, для чего метод Compress() сделаем публичным.
С выключенным флагом компрессии удаление всех элементов происходит в три раза быстрее:
Рис. 10. Время удаления элементов с ручным контролем занимаемой памяти (сравнение)
Метод Resize() вызывается не только в случае сжатия данных, но и в случаях, когда количество элементов уже становиться слишком большим и уже требуется массив большего размера. В этом случае избежать вызова метода Resize() не удастся. Его нужно вызвать обязательно, чтобы в будущем не создавать длинных и медленных цепочек CList. Однако мы можем заранее указать требуемую емкость нашего словаря.
Например, количество добавляемых элементов часто известно заранее. Зная количество элементов, словарь заранее создаст массив нужного размера, и лишних переразметок в процессе заполнения массива не потребуется.
Для этого добавим еще один конструктор, принимающий на вход количество требуемых элементов:
//+------------------------------------------------------------------+ //| Создает словарь с заранее определенной емкостью capacity | //+------------------------------------------------------------------+ CDictionary::CDictionary(int capacity) { m_auto_free = true; Init(capacity); }
Основную работу выполняет приватный метод Init():
//+------------------------------------------------------------------+ //| Выполняет инициализацию словаря | //+------------------------------------------------------------------+ void CDictionary::Init(int capacity) { m_free_mode=true; int n=FindNextSimpleNumber(capacity); m_array_size=ArrayResize(m_array,n); m_index = 0; m_hash = 0; m_total=0; }
Наши доработки готовы. Теперь настало время измерить производительность метода AddObject() с первоначально установленным размером массива, для чего изменим первые две строки в функции OnStart() нашего скрипта:
void OnStart() { //--- CDictionary dict(END+1); dict.AutoFreeMemory(false); ... }
END в данном случае очень большое число, равное 1 000 000 элементов.
С нововведениями наш метод AddObject() стал работать гораздо быстрее:
Рис. 11. Время добавления элементов с предустановленным размером массива
В реальных задачах, решаемых в программировании, всегда приходится выбирать между объемом занимаемой памяти и скоростью выполнения. Если память освобождать, это занимает существенное время. Однако в этом случае доступной памяти будет больше. Если память не освобождать, то время центрального процессора не будет тратиться на дополнительные сложные вычислительные задачи, но свободной памяти будет меньше. Объектно-ориентированное программирование с помощью классов-контейнеров позволяет гибко распределять ресурсы между памятью и временем процессора, выбирая для каждой конкретной задачи свою политику выполнения.
В целом производительность процессоров масштабируется гораздо хуже, чем объем памяти, поэтому в большинстве случаев надо отдавать предпочтение скорости выполнения, чем объему занимаемой памяти. К тому же на пользовательском уровне управлять памятью можно гораздо эффективней, чем в автоматическом режиме, т.к. как правило, конечное состояние задачи известно.
Например, в нашем скрипте нам еще до момента его выполнения известно, что общее количество элементов к концу всего перебора будет равно нулю, т.к. метод DeleteObjectByKey() удалит их всех к моменту окончания задачи. Поэтому сжимать массив автоматически не требуется вообще. Достаточно лишь очистить его в самом конце, вызвав соответствующий метод Compress().
Теперь, когда у нас есть хорошие линейные метрики добавления и удаления элементов из массива, проанализируем среднее время добавления и удаления элемента в зависимости от общего количества элементов:
Рис. 12. Среднее время добавления и удаления одного элемента
Видно, что среднее время добавления одного элемента в целом стационарно и не зависит от общего количества элементов в массиве. Среднее время удаления одного элемента немного дрейфует вверх, что нежелательно. Однако мы не можем точно сказать, имеем ли мы дело с результатами в пределах погрешности или это закономерная тенденция.
4.3. Производительность CDictionary по сравнению со стандартным CArrayObj
Настала пора для самого интересного теста - мы сравним созданный нами CDictionary со стандартным классом массива CArrayObj. Класс CArrayObj не содержит механизмов для ручного распределения памяти вроде указания предположительного размера на этапе создания, поэтому мы честно отключим в CDictionary ручное управление памятью и наш механизм AutoFreeMemory() будет включен.
Из первой главы мы знаем сильные и слабые места каждого из классов. В CDictionary можно очень быстро добавить элемент в произвольное место, а также очень быстро извлечь его из словаря. Зато в CArrayObj можно очень быстро сделать полный перебор элементов. В CDictionary перебор будет медленнее, т.к. он будет происходить за счет перехода по указателю, а это более медленная операция, чем прямая индексация.
Итак, приступим. Для начала создадим новую версию нашего теста:
//+------------------------------------------------------------------+ //| TestSpeed.mq5 | //| Copyright 2015, Vasiliy Sokolov. | //| https://www.mql5.com | //+------------------------------------------------------------------+ #property copyright "Copyright 2015, Vasiliy Sokolov." #property link "https://www.mql5.com" #property version "1.00" #include <Dictionary.mqh> #include <Arrays\ArrayObj.mqh> #define TEST_ARRAY #define BEGIN 50000 #define STEP 50000 #define END 1000000 //+------------------------------------------------------------------+ //| Script program start function | //+------------------------------------------------------------------+ void OnStart() { //--- CDictionary dict(END+1); dict.AutoFreeMemory(false); CArrayObj objects; for(int j=BEGIN; j<=END; j+=STEP) { //---------- ADD --------------// uint tiks_begin=GetTickCount(); for(int i=0; i<j; i++) { #ifndef TEST_ARRAY dict.AddObject(i,new CObject()); #else objects.Add(new CObject()); #endif } uint tiks_add=GetTickCount()-tiks_begin; //---------- GET --------------// tiks_begin=GetTickCount(); CObject *value=NULL; for(int i= 0; i<j; i++) { #ifndef TEST_ARRAY value = dict.GetObjectByKey(i); #else ulong hash = rand()*rand()*rand()*rand(); value = objects.At((int)(hash%objects.Total())); #endif } uint tiks_get=GetTickCount()-tiks_begin; //---------- FOR --------------// tiks_begin = GetTickCount(); #ifndef TEST_ARRAY for(CObject* node = dict.GetFirstElement(); node != NULL; node = dict.GetNextNode()); #else int total = objects.Total(); CObject* node = NULL; for(int i = 0; i < total; i++) node = objects.At(i); #endif uint tiks_for = GetTickCount() - tiks_begin; //---------- DEL --------------// tiks_begin = GetTickCount(); for(int i= 0; i<j; i++) { #ifndef TEST_ARRAY dict.DeleteObjectByKey(i); #else objects.Delete(objects.Total()-1); #endif } uint tiks_del = GetTickCount() - tiks_begin; //---------- SUMMARY --------------// printf((string)j+" elements. Add: "+(string)tiks_add+"; Get: "+(string)tiks_get + "; Del: "+(string)tiks_del + "; for: " + (string)tiks_for); #ifndef TEST_ARRAY dict.Clear(); #else objects.Clear(); #endif } }
Он использует макрос TEST_ARRAY. Если он определен, тест выполняет операции над CArrayObj, если нет - над CDictionary. Первый тест на добавление новых элементов выигрывает CDictionary.
Его модель перераспределения памяти в данном конкретном случае оказалась лучше:
Рис. 13. Время, затрачиваемое на добавление новых элементов в CArrayObj и CDictionary (сравнение)
Важно отметить, что причиной более медленной работы стала конкретная используемая модель перераспределения памяти в CArrayObj.
Она описывается всего одной строкой исходного кода:
new_size=m_data_max+m_step_resize*(1+(size-Available())/m_step_resize); Это линейный алгоритм выделения памяти. По умолчанию он вызывается при заполнении каждых 16 элементов. В CDictionary используется экспоненциальный алгоритм: каждое последующее перераспределение памяти выделяет вдвое больше памяти, чем предыдущий вызов. Этот график великолепно иллюстрирует дилемму между производительностью и используемой памятью. Метод Reserve() класса CArrayObj более экономный и требует меньше памяти, но работает медленнее. Метод Resize() класса CDictionary работает быстрее, но требует больше памяти, половину из которой может не использовать вовсе.
Выполним последний тест. Рассчитаем время полного перебора контейнеров CArrayObj и CDictionary. CArrayObj использует прямую индексацию, а CDictionary - переход по ссылке. В CArrayObj можно произвольно обратиться по индексу к любому элементу, а в CDictionary обращение к элементу по его индексу затруднено. Последовательный перебор практически ничем не уступает прямой индексации:
Рис. 14. Время, затрачиваемое на полный перебор CArrayObj и CDictionary
Разработчики языка MQL5 хорошо постарались и оптимизировали переходы по ссылкам. Такие переходы практически не уступают в скорости прямой индексации, что хорошо видно на графике.
Важно понимать, что перебор элементов занимает настолько малое время, что практически находится на грани разрешающей возможности функции GetTickCount(). Промежутки времени менее 15 миллисекунд с ее помощью измерить проблематично.
4.4. Общие рекомендации при использовании CArrayObj, CList и CDictionary
Создадим таблицу, в которой опишем основные задачи, встречающиеся в программировании, и свойства контейнеров, которые необходимо знать для решения этих задач.
Зеленым цветом помечены те свойства, которые дадут хорошую производительность при решении задачи, красным - свойства, которые не позволят решить эти задачи эффективно.
| Задача | CArrayObj | CList | CDictionary |
|---|---|---|---|
| Последовательное добавление новых элементов в конец контейнера. | Контейнеру необходимо будет выделить новую память для элемента. Переносить существующие элементы на новые индексы не потребуется. Эта операция CArrayObj будет выполнена очень быстро. | Контейнер запоминает первый, текущий и последний элемент. Благодаря этому присоединение нового элемента к концу списка (последнему запомненному элементу) будет очень быстрой операцией. | У словаря нет понятия "конца" или "начала". Присоединение нового элемента работает в нем очень быстро и не зависит от количества элементов коллекции. |
| Доступ к произвольному элементу по его индексу. | Благодаря прямой индексации доступ осуществляется очень быстро, за O(1). | Доступ к каждому элементу осуществляется через перебор всех предыдущих элементов. Эта операция занимает время O(n). | Доступ к каждому элементу осуществляется через перебор всех предыдущих элементов. Эта операция занимает время O(n). |
| Доступ к произвольному элементу по его ключу. | Недоступно | Недоступно | Расчет хэша и индекса по ключу - эффективная и быстрая операция. Для строковых ключей большое значение имеет эффективность хэширующей функции. Эта операция выполняется за O(1). |
| Добавление/удаление новых элементов по произвольному индексу. | CArrayObj потребуется не только выделить память для нового элемента, но и переместить все элементы, чей индекс превышает индекс вставляемого элемента на новое место. Поэтому в CArrayObj это медленная операция. | Добавление или удаление самого элемента в CList очень быстрая операция, однако доступ к необходимому индексу выполняется за O(n). Эта операция будет выполняться медленно. | Доступ в CDictionary к элементу по индексу осуществляется на основе списка CList и занимает много времени. Однако само удаление и вставка элемента - быстрая операция. |
| Добавление/удаление новых элементов по произвольному ключу. | Недоступно | Недоступно | Благодаря тому, что каждый новый элемент вставляется в CList, добавление и удаление новых элементов происходит очень быстро, т.к. не требуется переразмечать массив на каждой вставке/удалении. |
| Использование и управление памятью. | Требуется динамическая переразметка массива. Это ресурсоемкая операция, требующая либо много времени, либо много памяти. | Управление памятью не используется. Каждый элемент занимает ровно столько памяти, сколько требуется. | Требуется динамическая переразметка массива. Это ресурсоемкая операция, требующая либо много времени, либо много памяти. |
| Перебор коллекций. Операции, которые необходимо выполнить над каждым элементом вектора. | Благодаря прямой индексации элементов осуществляется очень быстро. Однако в некоторых случаях перебор важно выполнять в обратном порядке (например, при последовательном удалении последнего элемента). | Т.к. перебор всей колекции необходим однократно, прямой переход по связанным ссылкам является быстрой операцией. | Т.к. перебор всей колекции необходим однократно, прямой переход по связанным ссылкам является быстрой операцией. |
Глава 5. Документация к классу CDictionary
5.1. Основные методы для добавления, удаления и доступа к элементам
5.1.1. Метод AddObject()
Добавляет новый элемент типа CObject с ключом T Key. В качестве ключа может использоваться любой базовый тип.
template<typename T> bool AddObject(T key,CObject *value);
Параметры
- [in] key – уникальный ключ, являющийся одним из базовых типов (string, ulong, char, enum и т.д.).
- [in] value - объект, базовым классом которого является CObject.
Возвращаемое значение
Возвращает true, если объект был добавлен в контейнер, и false в противном случае. Если ключ добавляемого объекта уже содержится в контейнере, метод вернет отрицательное значение и объект не будет в него добавлен.
5.1.2. Метод ContainsKey()
Проверяет, существует ли в контейнере объект, чей ключ равен T Key. В качестве ключа может использоваться любой базовый тип.
template<typename T> bool ContainsKey(T key);
Параметры
- [in] key – уникальный ключ, являющийся одним из базовых типов (string, ulong, char, enum и т.д.).
Возвращает true, если объект с проверяемым ключом находиться в контейнере. Возвращает false в противном случае.
5.1.3. Метод DeleteObjectByKey()
Удаляет объект по заданному ключу T Key. В качестве ключа может использоваться любой базовый тип.
template<typename T> bool DeleteObjectByKey(T key);
Параметры
- [in] key – уникальный ключ, являющийся одним из базовых типов (string, ulong, char, enum и т.д.).
Возвращаемое значение
Возвращает true, если объект с заданным ключом был удален. Если объекта с заданным ключом не существует, или его не удалось удалить, возвращает false.
5.1.4. Метод GetObjectByKey()
Возвращает объект по заданному ключу T Key. В качестве ключа может использоваться любой базовый тип.
template<typename T> CObject* GetObjectByKey(T key);
Параметры
- [in] key – уникальный ключ, являющийся одним из базовых типов (string, ulong, char, enum и т.д.).
Возвращаемое значение
Возвращает объект, соответствующий заданному ключу. Если объекта с заданным ключом не существует, возвращает NULL.
5.2. Методы управления памятью
5.2.1. Конструктор CDictionary()
Базовый конструктор создает объект CDictionary с первоначальным размером базового массива, равного 3 элементам.
Увеличение и сжатие массива происходит автоматически по мере заполнения словаря или удаления из него элементов.
CDictionary();
5.2.2. Конструктор CDictionary(int capacity)
Конструктор создает объект CDictionary с первоначальным размером базового массива равным 'capacity' элементам.
Увеличение и сжатие массива происходит автоматически по мере заполнения словаря или удаления из него элементов.
CDictionary(int capacity);
Параметры
- [in] capacity – количество первоначальных элементов.
Примечание
Установление предельного размера массива сразу после его инициализации помогает избежать вызовов внутреннего метода Resize(), и тем самым увеличивает производительность при вставке новых элементов.
Однако следует учесть, что при удалении элементов и включенном флаге автоматического управления памятью (AutoMemoryFree(true)) произойдет автоматическое сжатие контейнера несмотря на установку capacity. Чтобы преждевременного сжатия не происходило, выполняйте первую операцию удаления объектов после полного заполнения контейнеров, либо, если это невозможно, отключайте автоматическое управление памятью (AutoMemoryFree(false)).
5.2.3. Метод FreeMode(bool mode)
Устанавливает режим удаления объектов, находящихся в контейнере.
Если режим удаления включен, то после удаления объекта из контейнера он также подвергается процедуре delete. Вызывается его деструктор, и он больше становится недоступен. Если режим удаления выключен, для объекта его деструктор не вызывается, и он продолжает быть доступным из других мест программы.
void FreeMode(bool free_mode);
Параметры
- [in] free_mode – флаг режима удаления объектов.
5.2.4. Метод FreeMode()
Возвращает флаг удаления объектов, находящихся в контейнере (см. FreeMode(bool mode)).
bool FreeMode(void);
Возвращаемое значение
Возвращает true, если объект удаляется оператором delete после его удаления из контейнера, в противном случае false.
5.2.5. Метод AutoFreeMemory(bool autoFree)
Устанавливает флаг автоматического управления памятью. По умолчанию автоматическое управление памятью включено. В этом случае компрессия массива (переразметка с большего размера на меньший) происходит автоматически. Если ее отключить, компрессия не происходит. Это существенно может ускорить выполнение программы, т.к. вызов ресурсоемкого метода Resize() не потребуется. Однако в этом случае необходимо самостоятельно следить за размером массива и производить его сжатие вручную с помощью вызова метода Compress().
void AutoFreeMemory(bool auto_free);
Параметры
- [in] auto_free – флаг режима управления памятью.
Возвращаемое значение
Возвращает true, если требуется включить управление памятью и вызывать метод Compress() автоматически, в противном случае false.
5.2.6. Метод AutoFreeMemory()
Возвращает флаг, указывающий используется ли автоматический режим управления памятью (см. метод FreeMode(bool free_mode)).
bool AutoFreeMemory(void);
Возвращаемое значение
Возвращает true, если используется режим управления памятью, в противном случае false.
5.2.7. Метод Compress()
Сжимает словарь и переразмечает элементы. Сжатие происходит только в том случае, если это возможно.
Этот метод следует вызывать только в том случае, если отключен режим автоматического управления памятью.
void Compress(void);
5.2.8. Метод Clear()
Удаляет все элементы, находящиеся в словаре. Если флаг управления памятью включен, для каждого удаляемого элемента также вызывается его деструктор.
void Clear(void);
5.3. Методы для перебора элементов в словаре
Все элементы в словаре связаны между собой. Каждый новый добавляемый элемент связывается с предыдущим. Таким образом возможен последовательный перебор всех элементов в словаре. В этом случае осуществляется переход по связанному списку. Методы из этого раздела помогают осуществить перебор, делая итерацию словаря удобной.
В качестве перебора словаря можно использовать следующую конструкцию:
for(CObject* node = dict.GetFirstNode(); node != NULL; node = dict.GetNextNode()) { // Здесь node - текущий элемент словаря. }
5.3.1. Метод GetFirstNode()
Возвращает самый первый элемент, который был добавлен в словарь.
CObject* GetFirstNode(void); Возвращаемое значение
Возвращает указатель на объект типа CObject, который был добавлен в словарь самым первым.
5.3.2. Метод GetLastNode()
Возвращает последний элемент, который был добавлен в словарь.
CObject* GetLastNode(void); Возвращаемое значение
Возвращает указатель на объект типа CObject, который был добавлен в словарь последним.
5.3.3. Метод GetCurrentNode()
Возвращает текущий выбранный элемент. Элемент предварительно должен быть выбран одним из методов для перебора элементов в словаре или методом доступа к элементу словаря (ContainsKey(), GetObjectByKey()).
CObject* GetLastNode(void); Возвращаемое значение
Возвращает указатель на объект типа CObject, который был добавлен в словарь последним.
5.3.4. Метод GetNextNode()
Возвращает следующий после текущего элемент. Если текущий элемент последний или не выбран, возвращает NULL.
CObject* GetLastNode(void); Возвращаемое значение
Возвращает указатель на объект типа CObject, следующий за текущим. Если текущий элемент последний или не выбран, возвращает NULL.
5.3.5. Метод GetPrevNode()
Возвращает элемент, предшествующий текущему элементу. Если текущий элемент является самым первым или не выбран, возвращает NULL.
CObject* GetPrevNode(void); Возвращаемое значение
Возвращает указатель на объект типа CObject, предшествующий текущему элементу. Если текущий элемент является самым первым или не выбран, возвращает NULL.
Заключение
Мы рассмотрели основные свойства распространенных контейнеров данных. Каждый контейнер данных необходимо использовать в тех случаях, где его возможности позволяют наиболее эффективно решать поставленную задачу.
Обычные массивы лучше всего использовать в случаях, где достаточно иметь последовательный доступ к элементу. Словари или ассоциативные массивы лучше всего использовать там, где удобно использовать доступ к элементу по его уникальному ключу. Списки лучше всего использовать в случаях частых перестановок элементов: удаление, вставок, добавления новых элементов.
Словарь позволяет просто и элегантно решать интересные алгоритмические задачи. Там, где другие контейнеры данных требуют дополнительных функций по их обработке, словарь позволяет организовать доступ к существующим элементам максимально эффективно. Например, на основе словаря можно построить событийную модель, где каждое событие типа OnChartEvent() будет напрямую доставляться классу, который управляет тем или иным графическим элементом. Для этого в словаре достаточно проассоциировать каждый такой экземпляр класса с именем объекта, которым он управляет.
Благодаря тому, что словарь - универсальный алгоритм, его области применения могут быть самыми разнообразными. Прочитав эту статью, становится понятным, что в основе его работы лежат достаточно простые и в тоже время надежные алгоритмы, делающие работу с ним удобной и эффективной.
Торговые идеи на основе направления и скорости движения цен
Изучаем класс CCanvas. Реализация прозрачности графических объектов
Создание интерактивного приложения для отображения RSS-каналов в MetaTrader 5
Рецепты MQL5 - ОСО-ордера
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования
Хороший вопрос. Сейчас проверил удаление Вашим способом - оно не работает корректно. Буду разбираться.
Спасибо за отклик!
оно и не должно работать корректно в общем случае.
правильный способ множественного удаления из ассоциативного массива - собрать массив удаляемых ключей, затем удалить по ключу.
Да вот в том-то и дело, что даже такой способ вдруг вызвал странный баг. Там явно ошибка. Буду разбираться в чем дело.
Пока могу посоветовать создать новый словарь, и в него добавлять значения которые не нужно удалять. Затем старый очистить. Это 100% сработает.
Значит так:
1. Обновляем версию Dictionary на ту что прикреплена к этому посту.
2. Запускаем тестовый скрипт по удалению четных элементов.
Удаление нужно делать в два прохода:
По поводу метода DeleteCurrentObject():
Данный метод нужно использовать только совместно с функцией ContainsKey(). Единственная причина по которой он доступен как public это то, что именно в этом кейсе вызов метода позволяет сэкономить время на повторном позиционировании указателя. Т.е. типичный и единственный случай его использования это 1. Проверили есть ли ключ, 2. если есть - удалили его быстро этим методом.
Это понятно, но опять же лишние телодвижения.
Технически возможно однопроходное удаление как Вы ожидаете. Но сложновато будет. Поэтому пока нет, только в два прохода. С точки зрения словаря как распределенной структуры данных, двухпроходное удаление является более канонически правильным решением. Это только на уровне пользователя кажется что удаление идет последовательно, на самом деле все иначе устроено. В плане перфоманса однопроходное удаление не принесет каких-либо бенефитов. В плане удобства - да, это может быть более удобным.
Технически возможно однопроходное удаление как Вы ожидаете. Но сложновато будет. Поэтому пока нет, только в два прохода. С точки зрения словаря как распределенной структуры данных, двухпроходное удаление является более канонически правильным решением. Это только на уровне пользователя кажется что удаление идет последовательно, на самом деле все иначе устроено. В плане перфоманса однопроходное удаление не принесет каких-либо бенефитов. В плане удобства - да, это может быть более удобным.
Спасибо.