外汇EA编写教程:mql5 secret:使用关联数组或字典快速访问数据

内容有效性

  • 简介
  • 第一章。数据组织理论
    • 1.1。数据组织算法。找到最佳的数据存储容器
    • 1.2。直接访问阵列和数据
    • 1.3。以CobjectCustom简单类为例介绍节点的概念
    • 1.4。以CarrayCustom类为例,介绍了节点指针数组。
    • 1.5。检查类型
    • 1.6。双向链表clist类的示例
  • 第二章相关阵列的组织理论
    • 2.1。日常生活中的关联数组
    • 2.2。基于开关盒算子的主关联数组或简单数组
    • 2.3。将基本类型转换为唯一键
    • 2.4。哈希字符串并将哈希数组用作键
    • 2.5。根据键确定索引列表的数组
  • 第三章关联数组的发展实例
    • 3.1。cdictionary类模板、addObject()和deleteObjectByKey()方法以及keyValuePair容器
    • 3.2。基于类型名运行类型确定:哈希采样
    • 3.3。containsKey()方法。对哈希冲突的响应
    • 3.4。动态分配和内存释放
    • 3.5。最终解决方案:搜索对象和一个简单的索引器
  • 第四章性能测试与评价
    • 4.1。写测试和性能评估
    • 4.2。代码分析的自动内存管理速度
    • 4.3。传统carrayobj与cdictionary的性能比较
    • 4.4。使用carrayobj、clist和cdi时的建议
  • 第五章限制类文件
    • 5.1。添加、删除和访问元素的方法
      • 5.1.1AddObject()方法
      • 5.1.2containsKey()方法
      • 5.1.3.DeleteObjectByKey()方法
      • 5.1.4.GetObjectByKey()方法
    • 5.2。内存管理方法
      • 5.2.1cDictionary()方法
      • 5.2.2.cDictionary(int capacity)方法
      • 5.2.3.自由模式()方法
      • 5.2.4.自由模式(布尔模式)方法
      • 5.2.5.自动释放内存(bool auto)方法
      • 5.2.6。自动释放内存()方法
      • 5.2.7.压缩()方法
      • 5.2.8。清除()方法
    • 5.3。字典搜索方法
      • 5.3.1.GetFirstNode()方法
      • 5.3.2.GetLastNode()方法
      • 5.3.3。getcurrentNode()方法
      • 5.3.4.GetNextNode()方法
      • 5.3.5.GetPrevNode()方法
  • 结论

简介

本文介绍了一个用于存储信息的方便类,称为关联的所有物或字典。此类允许通过键访问信息。

关联数组是一个正则数组。但它用唯一键替换索引,例如枚举时间框架枚举值或某些文本。关键不是关键。只要钥匙是独一无二的。这种数据存储算法可以大大简化许多编程任务。

例如,可以打印错误消息的函数可以实现如下:

//+------------------------------------------------------------------+
//| 在终端中显示错误描述                                                |
//| 如果错误代码未知则显示“未知错误”                                     |
//+------------------------------------------------------------------+
void PrintError(int error)
 {
   Dictionary dict;
   CStringNode* node = dict.GetObjectByKey(error);
   if(node != NULL)
      printf(node.Value());
   else
      printf("Unknown error");
 }

稍后我们将检查此代码。

在介绍关联数组的内部逻辑之前,让我们先看看数据存储的两种主要方式:数组和列表。我们的字典将基于这两种数据类型,因此我们需要深入了解它们的特性。第一个重点是数据类型。Chapter 2 introduces associative arrays and their methods.

第一章数据组织理论

1.1。数据组织算法。找到最佳的数据存储容器

搜索存储和信息表示是现代计算机的主要功能。人机交互通常包括信息搜索或信息创建和信息存储。信息不是一个抽象的概念。在实践中,它具有特定的意义。例如,货币的报价历史记录是任何交易者订购或准备订购的信息来源。编程语言文档或某些程序的源代码可以用作程序员的信息源。

一些图形文件,例如数码相机拍摄的照片,可以用作与编程或交易无关的人的信息来源。显然,这些类型的信息有其自身的特点。因此,信息的存储、表示和处理算法将有所不同。

例如,很容易将图形文件表示为二维矩阵(二维数组),每个元素或元组存储一小段图像颜色信息-像素。报价数据有其他特点。这本质上是一系列采用OHLCV格式的数据流。最好将此数据流表示为数组或有序结构,编程语言中的特定数据类型可以由多个数据类型组成。文档和源代码通常用纯文本表示。此数据类型可以定义并存储为有序字符串类型,其中每个字符串都是任意字符序列。

容器类型根据数据类型存储数据。使用面向对象的编程方法,很容易定义一个容器(如类)来存储这些数据,并有一个特定的算法(方法)来处理它们。类似的数据存储容器(类)有几种类型。它们基于不同的数据结构。然而,一些数据结构算法允许合并不同的数据存储模式。所以我们利用了所有存储类型的组合。

选择存储、处理和接收数据的容器取决于它们的方法和属性。重要的是要认识到没有具有相同效率的数据容器。有优点也有缺点。

例如,您可以非常快速地访问任何数组元素。但是,在随机数组中的某个位置执行插入操作非常耗时,在这种情况下需要对数组进行重构。相反,将元素插入到单向列表中是非常有效和快速的,但是访问一个随机元素可能需要更多的时间。如果您希望频繁插入新元素,但不经常访问它们,那么作为数据存储容器的单向链接列表是正确的选择。如果需要频繁访问随机元素,请选择数组作为数据存储类。

为了了解哪种类型的数据存储更为有利,您应该熟悉所有容器的组成。本文重点介绍关联数组和字典,这是一个基于数组和链接列表组合的特殊数据存储容器。但我想提醒您,根据特定的编程语言、可接受的编程规则和功能,字典可以以不同的方式实现。

例如,C语言中字典的实现不同于C++中的字典。本文没有介绍C++中词典的实现。本文介绍的关联数组是用MQL5编程语言编写的,并考虑了它的特点和实际的编程特点。尽管它们的实现是不同的,但字典的一般属性和操作方法是相似的。本文中描述的版本完全演示了这些属性和方法。

我们将逐步创建字典算法并讨论数据存储算法的特性。在本文的最后,我们将得到一个完整的算法,并彻底了解它的工作原理。

不同数据类型的处理效率不能完全相同。让我们考虑一个简单的例子:一个纸笔记本。它可以看作是我们日常生活中使用的容器/类。所有记录都存储在默认列表中(按字母顺序)。如果你知道订户的名字,你可以打开笔记本找到他或她的电话号码。

1.2。直接访问阵列和数据

数组是存储信息最简单、最有效的方法。在编程中,数组是类似元素的集合,一个接一个地分布在内存中。由于这个特性,我们可以计算数组中每个元素的地址。

事实上,如果所有元素都具有相同的类型,那么它们将具有相同的大小。因为数组元素是连续存储的,所以如果我们知道元素的大小,就可以计算任意元素的地址并直接访问它。计算地址的一般公式取决于数据类型和索引。

例如,我们可以使用以下公式计算UChar类型数组的第五个元素的地址:

任意元素的地址=第一个元素的地址+(数组中任意元素的索引*数组元素类型的大小)

第一个数组元素的地址对应于数组中索引为0的元素的地址。通过类比,第五个元素的索引是4。假设元素的类型是uchar。这是许多编程语言的基本数据类型。例如,它以C类型语言显示。MQL5也不例外。每种UChar类型占用一个字节或八个位的内存。

例如,根据前面提到的公式,数组中第五个元素的地址如下:

第五个元素的地址=第一个元素的地址+(4*1字节);

换句话说,第五个元素的地址比第一个元素的地址高四个字节。在程序的执行阶段,可以通过地址直接访问元素。这种地址算法可以很快地访问数组中的每个元素。但这种数据结构也有弱点。

不能在数组中存储不同类型的元素。这种限制也是直接寻址的结果。不同的数据类型有不同的大小,也就是说,不可能通过上述公式计算数组中特定元素的地址。但是,如果数组不存储元素,而是存储指针,那么这种限制也可以得到巧妙的服务。

最简单的方法是将指针视为链接(如Windows中的快捷方式)。指针指向内存中的特定对象,但指针本身不是对象。在MQL5中,指针只能指向一个类。在面向对象的编程语言中,类是一种特殊的数据类型,它可以包含任何数据聚合和方法,并且可以由用户创建以实现高效的程序构造。

每个类都是用户定义的特定数据类型。指向不同类的指针不能放置在数组中。但是无论指向哪个类,指针的大小都是相同的,因为它只包含操作系统中对象的地址,并且所有对象的地址大小都是相同的。

1.3。以CobjectCustom简单类为例介绍节点的概念

现在我们有足够的知识来设计第一个通用指针。其思想是创建一个指针的通用数组,每个指针指向一个特定的类型。实际的数据类型可能不同,但由于它们都由同一指针指向,因此这些类型可以存储在容器/数组中。创建第一个指针版本。

此指针将表示为最简单的类型,我们称之为cobjectcustom:

class CObjectCustom
{
};

没有什么比CobjectCustom类更简单的了,因为它既没有数据也没有方法。但现在已经足够了。

现在我们使用继承,这是面向对象编程的主要思想。继承提供了一种在对象之间建立标识关系的特殊方法。例如,我们可以告诉编译器任何类都是cobjectcustom的子类。

例如,human、ea和cWeather都是cobject自定义类的表示类。也许这些概念在现实生活中很难联系起来:天气与人类无关,ea与天气无关。但是没有理由不创建链接,让我们在程序的世界中建立,如果它们帮助我们的算法。

让我们用同样的方式创建更多的类:ccar、cnumber、cbar、cquotes、cmetaQuotes和cship。与前面的类一样,这些类实际上是不相关的,但它们都是cobjectcustom的子类。

让我们创建一个类库对象。文件中这些类的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
  {
  };
//+------------------------------------------------------------------+
//| 描述EA的类。                                                       |
//+------------------------------------------------------------------+
class CExpert : public CObjectCustom
  {
  };
//+------------------------------------------------------------------+
//| 描述汽车的类。                                                     |                                                              
//+------------------------------------------------------------------+
class CCar : public CObjectCustom
  {
  };
//+------------------------------------------------------------------+
//| 描述数字的类。                                                     |
//+------------------------------------------------------------------+
class CNumber : public CObjectCustom
  {
  };
//+------------------------------------------------------------------+
//| 描述价格K线的类。                                                  |                                          
//+------------------------------------------------------------------+
class CBar : public CObjectCustom
  {
  };
//+------------------------------------------------------------------+
//| 描述报价的类。                                                     |                               
//+------------------------------------------------------------------+
class CQuotes : public CObjectCustom
  {
  };
//+------------------------------------------------------------------+
//| 描述MetaQuotes公司的类。                                           |
//+------------------------------------------------------------------+
class CMetaQuotes : public CObjectCustom
  {
  };
//+------------------------------------------------------------------+
//| 描述船的类。                                                       |                               
//+------------------------------------------------------------------+
class CShip : public CObjectCustom
  {
  };

现在是时候将这些类分组到一个数组中了。

1.4。以CarrayCustom类为例,介绍了节点指针数组。

要组合类,我们需要一个特殊的数组。

最简单的是:

CObjectCustom array[];

此字符串创建一个动态数组来存储CObjectCustom类型的元素。因为我们先前定义的所有类都继承自CobjectCustom,所以我们可以将这些类存储在数组中。例如,我们可以在这里存储人员、汽车和船舶类。但要实现这一点,声明cobjectcustom数组是不够的。

通常,当我们声明一个数组时,当数组初始化时,它的所有元素都会自动填充。因此,当我们声明一个数组时,它的所有元素都被cobjectcustom类占用。

要确认这一点,我们可以稍微修改objectcustom类:

//+------------------------------------------------------------------+
//| 基类 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"
//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   CObjectCustom array[3];
  }

在onStart()函数中,我们初始化一个包含三个cobjectcustom元素的数组。

编译器用相应的对象填充数组。您可以读取日志以检查:

2015.02.12:12:26:32.964测试(USDCHF,H1)对象2-CObjectCustom
2015.02.12:26:32.964测试(USDCHF,H1)对象1-CObjectCustom
2015.02.12:26:32.964测试(USDCHF,H1)对象0-CObjectCustom

这意味着数组是由编译器填充的,我们不能在这里分配任何其他元素,如cweather或cexpert。

此代码不会通过以下方式编译:

#include "ObjectsCustom.mqh"
//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
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"
//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   CObjectCustom* array[3];
   CWeather* weather = new CWeather();
   array[0] = weather;
  }

现在代码不会报告错误并顺利编译。发生了什么事?首先,我们使用cobjectcustom的指针数组来初始化,而不是初始化cobjectcustom数组。

这样,编译器不会在初始化时创建新的cobjectcustom对象,而是将其设置为空指针。第二,我们使用指向C对象的指针,而不是对象本身。使用关键字new,我们创建cWeather对象并用指针“weather”指向它,然后将指针“weather”(而不是对象本身)放入数组中。

以相同的方式将剩余的对象放入数组。

代码如下:

#include "ObjectsCustom.mqh"
//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
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();
  }

这段代码可以工作,但是这样做是有风险的,因为我们直接对数组的索引进行操作。

如果我们计算数组大小错误或写错误的索引,程序将有严重的错误。但是这个代码适合于演示。

让我们展示这些元素:

图1。用指针数组存储数据的方案

由“new”操作符创建的元素存储在随机存储器中的特定位置,称为堆。这些元素杂乱无章,清晰可见。

我们的arrayobj指针有一个严格的索引方法,可以通过索引快速访问任何元素。但是访问这些元素是不够的,因为指针数组不知道它指向什么对象。CobjectCustom可以指向Cweather、CBAR或CMetaQuotes,因为它们是CobjectCustom类型。因此,为了获得元素类型,必须精确地指向实际的对象类型。

例如,实现如下:

#include "ObjectsCustom.mqh"
//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   CObjectCustom* arrayObj[8];
   arrayObj[0] = new CHuman();
   CObjectCustom * obj = arrayObj[0];
   CHuman* human = obj;
  }

在这段代码中,我们创建chuman对象,并将其作为cobjectcustom类型存储在arrayobj数组中。然后我们解析cobjectcustom并将其转换为chuman。因为我们指定了类型,所以本例中的代码不会报告错误。在实际编程中,很难跟踪每个对象的类型,因为可能有数百种类型,并且对象的数量可能是数百万。

这就是为什么我们在objectcustom类的末尾添加了一个额外的type()方法,该方法返回实际对象类型的修饰符。A modifier is a specific number that describes the type of object we are allowed to point to. 例如,我们可以使用预处理命令定义修饰符。如果我们知道由修饰符决定的对象类型,我们总是可以安全地将其转换为实际类型。所以下一步是创建安全类型。

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类的代码,并将变量更改为由数字表示的对象类型。将其设置为私有变量,以便其他对象无法更改它。

此外,我们将添加一个特殊的构造函数,以便类可以从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使用。这是为了防止打印错误。如果类不调用受保护对象自定义的构造函数,则类型“object”将是其默认类型。

所以是时候学习如何从arrayobj中提取类型并对其进行处理了。为此,我们将分别为chuman和weather类补充常用的run()和temp()方法。从arrayobj中提取类后,我们将其转换为所需的类型,并开始处理它。

如果CObjectCustom数组中存储的类型未知,我们将忽略并写入“未知类型”:

#include "ObjectsCustom.mqh"
//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
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测试(USDCHF,H1)未知类型。
2015.02.13:15:11:24.703试验(USDCHF,h1)32.0
2015.02.13:15:11:24.703试验(USDCHF,h1)人运行…

看来我们已经得到了我们想要的结果。现在,我们可以将任何类型存储在cobject自定义类型数组中,根据索引快速访问这些对象,并将它们转换为我们实际需要的类型。但是我们仍然缺少很多东西:对象在程序结束时被正确地销毁,堆中的对象被使用delete操作符删除。

此外,如果阵列已满,则需要一种安全的阵列大小重建方法。但我们不必从头再来。MetaTrader5标准类库已经包含了实现所有这些功能的工具。

这些类基于基于对象的通用容器/类。和我们的类一样,它有一个type()方法,返回类的实际类型,还有两个更重要的cobject类型指针:m_Prev和m_Next。他们的角色将在下一节中描述,在这里我们将通过CObject容器和列表类的示例讨论另一种存储数据的方法,称为双向链接列表。

1.6。双向链表clist类的示例

包含仁义类型元素的数组有一个主要缺点:如果要插入一个新元素,特别是在数组的中间,这将花费大量的时间。元素按顺序排列,您必须重新分配数组的大小以添加数组元素以进行插入,然后重新组织数组以使索引与新值匹配。

假设我们有一个由七个元素组成的数组,并且希望在第四个位置插入一个新元素。一般的插入算法如下:

图 2. 调整数组大小并插入新元素

图2。调整数组大小并插入新元素

有一个数据存储方案,可以快速有效地插入和删除元素。此方案称为单链接或双链接列表。此列表是常规队列。当我们排队时,我们只需要知道前一个人是谁(我们不需要知道他或她在前面)。我们不需要知道谁在我们后面。他或她必须控制自己在队列中的位置。

队列是单向链接列表的典型示例。然而,列表也可以是双向的。在这种情况下,每个人不仅知道前一个人是谁,而且也知道他或她在后面。因此,如果您正在寻找任何人,您可以从队列的任意一侧开始。

标准库中的clist类可以准确地实现该算法。让我们从已知类创建队列。但这次它们将从cobject类而不是cobjectcustom派生。

以下为指示:

图 3. 双向链表

图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{};
//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
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类型的指针:一个指向前一个元素,另一个指向后一个元素。列表中第一个元素的前向指针为空。指向列表中最后一个元素的向后指针也为空。所以我们可以一个接一个地遍历,直到队列的所有元素都被遍历为止。

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。下一个()移动到下一个节点。不要忘记将元素的当前索引号添加到1(i++)。如果知道当前节点为空,则停止遍历。在for代码中的第二段用于确认:节点!= NULL。

ReverseEnumerateAll()函数的不同之处在于,它首先获取列表中的最后一个元素cobject*node=list。获取最后一个节点()。前一个元素node=node,而不是获取for循环中的下一个列表。PREV()。

执行代码时,我们收到以下信息:

2015.02.13 17:17:52:52:02.13 17:52:52.02.1317:52:02.974测试列表(USDCHF,D1)枚举完成。
2015.02.13 2015.02.13 17:17:17:17:17:52:52:52:52:52:52:52:02.974测试列表(USCHF,d1)元素在0
2015.02.13.13 17:52:02.974测试列表(USCHF,d1)元素在
2015.2015.02.13 2015.02.13 13:17:17:17:17:17:13:17:17:17:17:17:17:17:17:17:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52:52 17:52:02.97 4测试列表(usdchf,d1)&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;枚举从头到尾&lt;&lt;&lt;&lt;&lt;&lt;
2015.02.52:52.13 17:52.02.974测试列表(usdchf,d1)元素在3
2015.02.02.13 17:52:52.974测试列表(usdchf,d1)元素在2
2015.02.02.02.13在2
13.13 13:12.13:02.13 17:52:02.974测试列表(USDCHF,D1)元素位于0
2015.02.13 17:52:02.974测试列表(USDCHF,D1)&gt;&gt;&gt;&gt;从头到尾枚举&gt;&gt;&gt;&gt;&gt;

您可以轻松地将新元素插入到列表中。只需更改前一个或后一个元素的指针,并将其指向新元素,新元素将指向前一个和后一个元素。

方法非常简单:

图 4. 在双向链表中插入元素

图4。将新元素插入双向列表

链表最大的缺点是它们不能根据索引访问元素。

例如,如果您想在图4中引用cexpert,则必须先访问ccar,然后访问cexpert。对C来说也是一样。它在列表的末尾,因此从末尾访问更容易。要做到这一点,您必须在线访问cship,然后访问cweather。

移动指针比直接索引访问操作慢。现代的CPU操作已经得到了优化,特别是对阵列。这就是为什么在实践中优先使用数组的原因,尽管列表运行得更快。

第二章相关阵列的组织理论

2.1。日常生活中的关联数组

在日常生活中,我们每天都面对关联数组。但它们是如此普遍,我们认为它们是理所当然的。关联数组或字典的最简单示例是电话簿。本书中的每个电话号码都与一个人的姓名相关联。电话簿中的姓名是一个唯一的键,电话号码是一个简单的号码。电话号码簿中的每个人都可能有几个号码。例如,一个人可能有家庭电话、手机和公司电话号码。

一般来说,可能有无限的数字,但人们的名字是独一无二的。例如,电话簿中的两个Alexanders可能会让你困惑。有时我们可能拨错号码。这就是为什么键(在本例中是名称)必须是唯一的原因。字典还需要知道如何解决冲突并避免冲突。两个相同的名字不会把电话簿弄坏。我们的算法需要知道如何处理这种情况。

我们在日常生活中使用几种类型的字典。例如,电话簿是一本字典,每一行(名称)是一个键,电话号码是一个数字。外国词典有另一种结构。英语单词是一把钥匙,它的翻译是一种价值。这两种类型的关联数组都基于相同的数据处理方法,这就是为什么我们的字典必须能够有多种用途,并且允许存储和比较任何类型。

在编程中,创建自己的字典和记事本并不复杂。

2.2。基于开关盒算子的主关联数组或简单数组

您可以轻松地创建一个简单的关联数组。在MQL5中使用标准工具库,例如开关运算符或数组。

让我们看看下面的代码:

//+------------------------------------------------------------------+
//|  根据传入的时间框架值                                               |
//|  返回时间框架的字符串表示                                            |
//+------------------------------------------------------------------+
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运算符的操作方式类似于字典。每个枚举时间框架都有一个字符串值来描述时间框架。由于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];
}

此代码通过索引描述数组元素的应用,其中枚举帧是索引。在返回值之前,函数检查数组是否分配了所需的元素。如果不是,请使用特殊函数来分配-initTimeframes()。它与开关操作员有相同的缺点。

此外,这种字典结构需要大量的数字来初始化数组。期间mn1的值是49153。也就是说,我们需要49153个单元来存储9个时间帧。其他单位未分配。这种数据分配方法远不是一种紧凑的方案,但是当枚举值的数目很小且连续时,它更为合适。

2.3。将基本类型转换为唯一键

由于字典的算法是相似的,而不考虑键的类型和值,因此我们需要执行数据对齐,以便通过一个算法处理不同的数据类型。我们的字典算法是通用的,任何基本类型都可以用作键,如int、enum、double甚至string。

实际上,MQL5中的任何基本类型都可以用ulong数字表示。例如,short或ushort是ulong的“短”版本。

当ulong类型存储ushort类型的值时,您始终可以安全、准确地键入:

ulong ln  = (ushort)103; // 将ushort类型值保存在ulong类型中(103)
ushort us = (ushort)ln;  // 从ulong类型中获取ushort类型值(103)

char和int类型也是如此,它们的无符号类型ulong可以存储小于或等于ulong类型的任何值。日期时间、枚举和颜色类型基于32位数字,这意味着它们可以安全地转换为ulong类型。bool类型只有两个值:0代表假,1代表真。因此,bool类型值也可以存储在ulong类型变量中。此外,许多MQL5系统功能都基于此功能。

例如,accountinfointeger()函数返回long类型的整数值,可以是ulong类型的帐户,也可以是允许进行交易的account_trade_的布尔值。

但是,mql5有三种不同于整数的基本类型。它们可以直接转换为ulong类型。有浮点类型,如double和float,以及字符串。但是一些简单的操作可以将它们转换为唯一的整数键/值。

每个浮点数都可以用科学的计数方法表示,基数和乘数分别存储为整数值。此存储方法用于双精度值和浮点值。float类型使用32位存储尾部和电源,double类型使用64位。

如果我们试图将其直接转换为ulong类型,则值将被简单地四舍五入。在这种情况下,3.0和3.14159将返回相同的值-3。这不适合我们,因为我们需要两个不同值的不同键。C语言中不常用的特性可以解决这个问题。这就是所谓的结构转换。如果两个不同的结构大小相同(将一个结构转换为另一个结构),则可以相互转换。

让我们来看两个结构的例子,一个存储ulong类型的值,另一个存储double类型的值:

struct DoubleValue{ double value;} dValue;
struct ULongValue { ulong value; } lValue;

//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
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结构。因为它们具有相同的大小和变化顺序,所以dvalue的双类型值。值以字节为单位复制到左值的ulong类型值。价值。

然后输出变量值。如果我们改变dvalue的值。值为3.14160,左值的值。值也会改变。

这是printf()函数输出的结果:

2015.02.16 15:37:50.646测试列表(USDCHF,h1)461425667394983
2015.02.16 15:37:50.646测试列表(USDCHF,h1)461425650576692846

浮点类型是double类型的缩短版本。相应地,在将float类型转换为ulong类型之前,可以安全地将float类型扩展为double类型:

float fl = 3.14159f;
double dbl = fl;

在此基础上,通过结构变换,将双精度变换为乌龙型。

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);
}

返回的值取决于要转换的字符串。

为了实现这个目标,我们编写了一个简单的脚本来调用这个函数并转换不同的字符串:

//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
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:13:29:29:12.576测试列表(USDCHF,h1)元交易员-35219191466
2015.02.16 13:13 13:23:29:29:12.576测试列表(USDCHF,h1)和平-91685343
2015.02.16:13:29:12.576测试列表(USDCHF,h1)和平-91685343
2015.02.16:13:29:12.576测试列表(USDCHF,h1)你好!-48713020世界!-48713020206 A6060606 A606063
2015.02.02.02.02世界-413860925

我们看到每个字符串都有一个与之对应的特殊数字。注意字符串“hello world”和“hello world!”-它们几乎是一样的。唯一的区别是第二个字符串以感叹号结尾。

但由adler32()返回的数字是完全不同的。

既然我们知道了如何将字符串类型转换为无符号uint值,那么就可以保存它的整型散列值而不是字符串类型键。如果两个字符串具有相同的哈希代码,那么这两个字符串是相同的。因此,值的键不是字符串,而是基于字符串的整数哈希代码。

2.5。根据键确定索引列表的数组

现在我们知道了如何将mql5基类型转换为ulong类型。实际上,我们的值对应于这种类型。但乌龙型的钥匙是不够的。当然,如果我们知道每个对象的唯一键,我们可以基于switch case操作符创建一些私有存储方法或任意长度的字符串。

上一章的第2.2节描述了这种方法。但它们的可扩展性不足且效率低下。对于开关情况,似乎不可能列出该运算符的所有变量。

如果有成千上万的对象,我们必须在switch操作符中使用数万个键作为枚举值,这在第一阶段是不可能的。第二种方法是使用数组,数组的键也是它们的索引。允许动态添加元素和重新分配数组大小。所以我们可以通过它的索引频繁地访问它,索引是它的元素的关键。

让我们为这个解决方案构建一个框架:

//+------------------------------------------------------------------+
//|  通过key存储字符串的数组                                            |
//+------------------------------------------------------------------+
string array[];
//+------------------------------------------------------------------+
//| 向关联数组中添加字符串。                                            |                                                                     
//| 结果:                                                            |
//|    返回 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;
  }

但实际上,这个代码不能解决这个问题。假设一个哈希函数输出一个大的哈希代码。在给出的示例中,数组索引等于其哈希代码,我们必须重置非常大的数组大小。但这可能意味着失败。是否要将字符串存储在几个g大小的内存空间中?

第二个问题是,如果存在冲突,前面的值将被一个新值替换。简而言之,adler32()函数可以将相同的哈希代码返回到两个不同的字符串。是否只使用密钥快速访问丢失的数据?这些问题的答案是显而易见的-不,你不会的。为了避免这种情况,我们必须修改存储算法,并开发一个基于链表数组的特殊混合存储容器。

链接列表数组结合了数组和列表的最佳特性。这两个类在标准类库中进行了描述。请注意,数组可以很快地访问未定义的元素,但要缓慢地重新组织数组。但是链接列表可以快速执行添加和删除元素,但是访问每个列表中的元素的速度很慢。

链接列表的数组可以以下形式表示:

图. 5. 链表数组

图5。链接列表数组

如上图所示,列表数组是一个数组,其中每个元素都是一个列表。让我们看看有什么好处。首先,我们可以通过索引快速访问任何列表。此外,如果我们在列表中存储数据元素,我们将能够在不调整数组大小的情况下及时添加和删除列表中的元素。数组索引可以为空或为空,这意味着尚未添加与该索引对应的元素。

组合数组和列表给我们提供了一个难得的机会。我们可以在一个索引中存储多个元素。为了便于理解,我们假设只需要在三个元素的数组中存储10个数字。您可以看到存储的数字比数组元素多。我们将通过在数组中存储列表来解决这个问题。假设我们需要将三个列表中的一个连接到三个数组索引中的一个来存储一个或另一个数字。

为了确定列表索引,我们需要找到数组中元素数的除数余数。

数组索引=数组元素数百分比;

例如,数字2的列表索引为:2%3=2。这也意味着2将存储在索引为2的列表中。3将存储在索引为3%3=0的列表中。7将存储在索引7%3=1的列表中。在确定了列表索引之后,我们只需要在列表的末尾添加数字。

从列表中解析数据的方法类似。假设我们现在分析数字7。所以我们需要找出它在哪里:7%3=1。当我们知道数字7存储在索引为1的列表中后,我们将检索整个列表并返回元素的值等于7。

如果我们可以使用索引来存储多个元素,就不需要创建巨大的存储空间来存储少量的数据。假设数字232547879需要存储在一个包含三个元素的数组中。The list index of this number is (232,547,879%) 3 = 2.

如果我们用散列码替换数字,我们可以找到任何需要放在字典中的元素的索引。因为散列码是一个数字。此外,由于多个元素可以存储在一个列表中,哈希代码不必是唯一的。具有相同哈希代码的元素将存储在列表中。如果需要逐键分析元素,我们将比较这些元素并逐键分析相应的元素。

具有相同哈希代码的两个元素可能具有两个不同的键。可以通过向字典中的函数添加元素来控制键的唯一性。如果字典中已经存在对应的键,则不会添加新元素。这就像控制一个用户只有一个对应的电话号码。

2.6。数组大小重构以最小化列表长度。

列表数组的长度越小,添加的元素越多,算法形成的列表链就越长。如第1章所述,访问此类列表中的元素效率很低。列表越短,容器越像可以通过索引访问的数组。我们需要短列表和长数组。有十个元素的完美数组是一个有十个列表的数组,每个列表只有一个元素。

最坏的情况是一个只有一个10个元素列表的数组。因为所有元素都是在程序运行时动态添加到容器中的,所以我们无法预测将添加多少元素。这就是我们需要动态分配数组长度的原因。此外,列表中的元素数量往往是一个。为了实现这一目标,很明显这需要数组长度等于元素数。连续添加元素需要不断调整数组大小。

这种情况也很复杂,因为我们必须在调整数组大小的同时调整所有列表的长度,因为元素所属的列表索引可能会更改。例如,如果数组有三个元素,则数字5将存储在第二个索引中(5%3=2)。如果一个元素被保留,数字5将存储在第五个索引中(5%6=5)。因此,字典大小调整是一个缓慢的操作。它应该尽可能少。另一方面,如果我们不这样做,列表将随着新元素的数量而增加,对每个元素的访问将变得越来越低效。

我们可以创建一个算法来合理地平衡数组的长度和链表的平均长度。它将基于这样一个事实:数组大小的每次调整将是当前数组长度的两倍。因此,如果字典最初只有两个元素,则第一次调整后字典的大小将为4(2^2)、2^8(2^3)和3^16(2^3)。第十六次调整为65 536(2^16)。如果新元素的数目正好等于当前数字的二次幂,请调整数组大小。因此,实际所需的总内存不会超过存储所有元素所需内存的两倍。另一方面,该算法有助于避免阵列尺寸的频繁调整。

类似地,列表中的元素可以减小数组的大小并节省内存空间。

第三章关联数组的发展实例

3.1。cdictionary类模板、addObject和deleteObjectByKey方法以及keyValuePair容器

我们的关联数组必须是多功能的,并且支持所有类型的键。同时,我们将使用基于标准CObject类的对象作为变量。因为我们可以在类中放入任何基本类型变量,所以我们的字典将提供一站式解决方案。当然,我们需要能够创建多个字典类。可以为每个基类型使用单独的类。

例如,我们可以创建以下类:

CDictionaryLongObj    // 存储 <ulong, CObject*>
CDictionaryCharObj    // 存储 <char, CObject*>
CDictionaryUcharObj   // 存储 <uchar, CObject*>
CDictionaryStringObj  // 存储 <string, CObject*>
CDictionaryDoubleObj  // 存储 <double, CObject*>
...

但是在MQL5中有太多的基本类型。此外,我们还必须多次纠正每个代码错误,因为所有类型都有一个核心代码。我们将使用模板来避免重复。我们将只有一个类,但它可以同时处理多个数据类型。这就是类的主要方法是模板的原因。

首先,让我们创建第一个模板方法,添加()。此方法将任何键的元素添加到字典中。Dictionary类的名称为CDictionary。除了元素本身之外,字典还将包含指向clist列表的指针数组。我们将元素存储在这些链接列表中:

//+------------------------------------------------------------------+
//|  一个关联数组或者字典存储元素形如                                     |
//| <key - value>,key可能被任何基本类型所表示                           |
//|  值可能被CObject类型对象表示。                                      |
//+------------------------------------------------------------------+
class CDictionary
  {
private:
   CList            *m_array[];       // 列表数组。
   template<typename T>
   bool              AddObject(T key,CObject *value);
  };
//+------------------------------------------------------------------+
//| 添加一个带 T 的CObject类型元素key到字典中                            |
//| 输入参数:                                                         |
//|   T key - 任何基本类型,例如 int,double或者string。                 |
//|   value - 从CObject类派生而来的类。                                 |  
//| 返回:                                                            |
//|   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()方法执行此检测。If the key already exists in the dictionary, the new element will not be added, because if two elements correspond to one key, uncertainty will arise.

然后,此方法获取存储clist列表的数组的大小。如果数组大小等于元素数,则需要重新分配数组大小。此操作在resize()方法中实现。

下一步很简单。如果基于已确定索引的clist链接列表还不存在,则需要创建它。索引以前是由containsKey()方法确定的。将索引存储在变量m_index中。然后在列表的末尾添加一个新元素。以前,这个元素存储在一个特殊的容器keyValuePair中。它基于标准的CObject并对其进行扩展,添加指针和数据。稍后将讨论容器类的组织。除了其他指针之外,容器还包含对象的原始键及其哈希代码。

addObject()方法是模板方法:

template<typename T>
bool CDictionary::AddObject(T key,CObject *value);

这意味着密钥类型是可替换的,其实际类型在编译时确定。

例如,可以使用以下代码激活addObject()方法:

//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
void OnStart()
  {
   CObject* obj = new CObject();
   dictionary.AddObject(124,  obj);
   dictionary.AddObject("simple object",  obj);
   dictionary.AddObject(PERIOD_D1,  obj);
  }

由于模板的作用,这些操作将被完美地执行。

还有deleteObjectByKey()方法,它与adObject()方法相反。此方法通过元素的键从字典中删除一个对象。

例如,您可以删除键为“car”的对象(如果存在)。

if(dict.ContainsKey("Car"))
      dict.DeleteObjectByKey("Car");

代码与adObject()方法的代码非常相似,因此我们将不再讨论它。

AddObject()和DeleteObjectByKey()方法不直接操作对象。相反,它们将每个对象打包到一个基于标准cobject类keyValuePair的容器中。容器具有可以关联元素的指针,并具有对象的初始键和哈希代码。此容器还测试传入密钥以避免冲突。我们将在下一章讨论containsKey()方法来处理冲突。

现在让我们看看这个类的代码:

//+------------------------------------------------------------------+
//| 存储CObject元素的容器                                              | 
//+------------------------------------------------------------------+
class KeyValuePair : public CObject
  {
private:
   string m_string_key;    // 存储字符串类型的key
   double m_double_key;    // 存储浮点数类型的key
   ulong  m_ulong_key;     // 存储无符号整型的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。根据类型名和哈希采样在运行时确定变量类型。

现在,如果我们想要得到未定义的方法,我们需要确定它们的哈希代码。对于所有整数类型,哈希代码等于将值扩展到ulong类型之后的值。

要计算双类型和浮点类型的哈希代码,我们需要使用结构,如“将基本类型转换为唯一键”一节中所述。哈希函数应用于字符串类型。无论如何,任何数据类型都需要它自己的哈希采样方法。所以我们需要做的是确定转换类型并使用与此类型对应的哈希采样方法。为了实现这个目标,我们需要一个特殊的类型名。

按键确定哈希代码的方法称为GetHashByKey()。

它包含:

//+------------------------------------------------------------------+
//| 基于key计算hash码                                                 |                                                                     
//| key可能被表征为任何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;
  }

它的逻辑很简单。使用类型名称方法获取传输类型的字符串名称。如果字符串作为键传输,则类型名返回“string”值,如果整数值返回“int”。这同样适用于其他类型。因此,我们需要做的是将返回值与字符串常量进行比较,并在值与其中一个常量匹配时激活相应的函数句柄。

如果键是字符串类型,则其哈希代码由adler32()函数计算。如果键由实际类型表示,则它们将转换为结构转换的哈希代码。所有其他类型都准确地转换为ulong类型的哈希代码。

3.3。containsKey()方法。对哈希冲突的响应

任何哈希函数的主要问题都是存在冲突——也就是说,当不同的键对应于相同的哈希代码时。如果哈希代码发生冲突,就会出现混淆(字典逻辑中的两个对象相同)。为了避免这种情况,我们需要检查实际的和请求的键类型,并且只在实际的键冲突时返回一个正值。这就是containsKey()的工作原理。如果对象请求的键已存在,则返回true,或者返回false。

也许这是整个词典中最有用和最方便的方法。它确定对象的键是否已存在:

#include <Dictionary.mqh>
CDictionary dict;
//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
void OnStart()
  {
   if(dict.ContainsKey("Car"))
      printf("Car always exists.");
   else
      dict.AddObject("Car", new CCar());
  }

例如,上面的代码检查是否存在CCAR类型的对象,如果它们不存在,则添加它们。此方法还检测添加的每个新对象的键是否唯一。

如果对象的键已经存在,addObject()方法将不会将新对象添加到字典中。

template<typename T>
bool CDictionary::AddObject(T key,CObject *value)
  {
   if(ContainsKey(key))
      return false;
   ...
  }

这是用户和其他类大量使用的常用方法。

如下:

//+------------------------------------------------------------------+
//| 检查字典中是否存在T类型的key                                        |
//| 返回:                                                           |
//|    如果已经存在返回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类型的对象表示,该对象用于比较实际转换的键和存储在元素中的键。如果键相同,则函数返回“真”(已存在该键的对象)。keyValuePair类中提供了用于确定键是否相等的代码。

3.4。动态分配和内存释放

在我们的关联数组中,resize()方法用于动态分配和回收内存。每当元素数等于m_数组的大小时,就会调用此方法。当从列表中删除元素时,也会调用它。此方法重写所有存储元素的索引,因此运行非常缓慢。

为了避免频繁调用Resize()方法,每个内存分配都是原始大小的两倍。换句话说,如果我们的字典要存储65536个元素,那么resize()方法将被调用16次(2^16)。在20次调用之后,字典可能包含100多万个元素(1048576)。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-&gt;cShip-&gt;cWeather-&gt;Chuman-&gt;cExpert-&gt;CCAR

因为这些元素的枚举也将通过对keyValuePair的引用按顺序执行,如图6所示:

图. 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;
//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
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 2015.02.24 14:08:29.537测试dict(USCHF,h1)6:CCAR
2015.02.24 14:08:29.537测试dict(USCHF,h1)5:CExpert
2015.02.24 14:08:29.537测试dict(USCHF,h1)4:Chuman
2015.02.23 2015.02.24 14:08:29.537测试dict(USCHF,h1)3:CWEather
2015.02.24 14:08:29.537测试dict(USCHF,h1)29.537测试dict(USCHF,h1)6:29.537测试dict(USCHIP
.537测试dict(USCH033 2015.02.24 14:08:29.537测试dict(USDCHF,h1)1:号码

将onStart()函数中的两行代码更改为反向输出所有元素:

CStringValue* currString = dict.GetLastNode();
for(int i = 1; currString != NULL; i++)
 {
  printf((string)i + ":/t" + currString.Value);
  currString = dict.GetPrevNode();
 }

相应地,输出内容反转:

2015.02.24 2015.02.24 14:11:01.021测试dict(USCHF,h1)6:CN编号
2015.02.24 2015.02.24 14:11:01.021测试dict(USCHF,h1)5:CSHIP
2015.02.24 14:24 14:24 14:11:11:01.021测试dict(USCHF,h1)4:CWEATHER
2015.02.23 2015.02.24 14:01.021测试dict(USCHF,h1)3:楚曼
2015.02.2015.23 2015.2015.02.24 14:11:01.033 2015.2015.02.03:CN编号
2015.2015.02.2015.02.2015.02.23 2015.
2015.02.24 14:11:01.021测试指令(USDCHF,H1)1:CCAR

第四章。测试和评估性能

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
//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
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程序。

我们将以同样的方式分析脚本。经过一段时间后,我们的脚本运行,我们得到了脚本中所有方法的运行时分析。屏幕截图显示了三种最耗时的方法:AddObject()占40%的时间,GetObjectByKey()占7%,DeleteObjectByKey()占53%。

0

数字。9。onStart()功能代码分析

compress()方法消耗了DelteObjectByKey()函数所用时间的60%以上。

但是这个方法几乎是空的,时间主要花在调整大小()方法上。

它包含:

CDictionary::Compress(void)
{
   double koeff = m_array_size/(double)(m_total+1);
   if(koeff < 2.0 || m_total <= 4)return;
   Resize();
}

问题很明显。当我们删除所有元素时,偶尔会加载resize()方法。此方法动态地减小阵列大小以释放存储空间。

如果要加快删除元素的速度,请禁用此方法。例如,可以使用autofreemory()方法在类中设置一个缩减的标识符。将其设置为默认值,在这种情况下,压缩将自动执行。但是如果我们需要获得额外的速度,我们必须在正确的时间手动执行压缩。我们将compress()方法设置为公共方法来实现这一目标。

如果禁用压缩,则删除元素的速度将快三倍:

1

数字。10。元素删除时间比较

Resize()方法不仅在压缩数据时调用,而且在元素太多并且需要较大的数组时调用。在这种情况下,我们不能避免调用Resize()方法。为了创建一个不冗长的未来列表,必须调用它。但我们可以预先确定字典所需空间的大小。

例如,要添加的元素的数量通常提前知道。知道元素的数量后,可以预先创建与字典大小相匹配的数组,因此不需要在填充阶段调整数组的大小。

为了实现这一点,我们将添加一个额外的构造函数来接收所需的元素。

//+------------------------------------------------------------------+
//| 创建一个容量预先定义好的字典                                         |
//+------------------------------------------------------------------+
CDictionary::CDictionary(int capacity)
  {
   m_auto_free = true;
   Init(capacity);
  }

private 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表示1000000个元素。

这些改进显著提高了addObject()方法的性能:

2

数字。11。在默认数组大小之后添加元素所需的时间

解决这个问题成为了一个真正的问题,我们很震惊地发现必须在内存使用和性能速度之间做出选择。释放内存需要很多时间。但在这种情况下,我们会得到更多的记忆。如果我们不干预,CPU将不会在复杂的计算问题上花费额外的时间,但同时可用内存将减少。使用容器的面向对象编程,并为每个问题选择特定的执行策略,可以在CPU缓存和CPU时间之间灵活地分配资源。

简而言之,CPU性能比内存占用更重要。这就是为什么在大多数情况下,我们更喜欢加快执行速度而不是内存占用。In addition, memory control on the user side is more efficient than automatic control, because we often don’t know the state of the heaviest task.

例如,如果我们事先知道脚本中的所有元素在结尾处都将为空,则deleteObjectByKey()方法将在任务结束时删除它们。这就是我们不需要自动缩小数组大小的原因。最后一次调用compress()方法就足够了。

既然我们有了从数组中添加和删除元素的良好线性度量,我们就可以分析添加和删除元素的平均时间。

3

数字。12。添加和删除元素的平均时间

您可以看到,添加元素的平均时间非常稳定,与数组中元素的数量无关。删除元素的平均时间增长缓慢,这不是我们想要的。但我们不确定这是误差范围内的结果还是常规趋势。

4.3。传统carrayobj与cdictionary的性能比较

现在让我们做一个我们最感兴趣的测试:C标准carrayobj类的字典。carrayobj没有类似于创建阶段累积分配空间提示的手动内存分配机制,这就是为什么我们将禁用cdictionary中的手动内存分配并启用autofreemory()机制的原因。

第一章介绍了每一类的优缺点。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

//+------------------------------------------------------------------+
//| 脚本程序start函数                                                  |
//+------------------------------------------------------------------+
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_数组宏。如果定义了它,则在carrayobj或cdictionary上执行测试。第一个添加新元素的测试字典获胜。

在这种特殊情况下,它的内存分配更好:

4

图13。在carrayobj和cdi action ary中添加新元素的时间开销比较

应该强调的是,执行速度慢是由于carrayobj特殊的内存分配机制造成的。

源代码中只有一行描述了此操作:

new_size=m_data_max+m_step_resize*(1+(size-Available())/m_step_resize);

这是一种用于内存分配的线性算法。在填充16个元素后调用。cdictionary使用指数算法:每个内存分配的大小是前一个内存分配的两倍。此图完美地说明了性能和内存使用之间的困境。carrayobj类的reserve()方法效率更高,需要的内存更少,但运行速度较慢。cdictionary类的resize()方法执行速度更快,但需要更多的内存,可能使用的内存不足一半。

让我们做最后一个测试。我们将计算carrayobj和cdi容器完全枚举所需的时间。carrayobj使用直接索引,cdictionary使用引用。carrayobj可以按索引访问任何元素,但不允许在cdictionary中按索引引用任何元素。按直接索引顺序枚举非常有效:

5

图14。carrayobj及字典全计数时间

MQL5语言开发人员在优化引用方面做得很好。如图所示,与直接索引相比,它们的执行速度非常有竞争力。

重要的是要认识到元素枚举花费的时间非常少,以至于gettickCount()函数可以区分边缘。很难检测到小于15毫秒的时间间隔。

4.4。使用carrayobj、clist和cdi时的建议

我们将创建一个表,描述编程过程中遇到的主要任务以及解决这些问题必须知道的容器的特性。

良好的性能特征显示为绿色,反之亦然,显示为红色。

目标 卡拉Objo 克里斯特 辞典
在容器的末尾按顺序添加新元素。 容器必须为新元素分配新空间。不需要将现有元素移动到新索引。Carrayobj可以很快做到这一点。 容器记住第一个当前元素和最后一个元素。因此,新元素将很快添加到列表中(最后一个元素)。 字典中没有“结束”或“开始”这样的概念。不管元素的数量如何,新元素的添加速度都非常快。
通过其索引访问任何元素。 由于直接索引,访问速度非常快,时间复杂度为O(1)。 通过枚举所有以前的元素来访问每个元素。时间复杂度o(n)。 通过枚举所有以前的元素来访问每个元素。时间复杂度o(n)。
通过键访问任何元素。 不可用的 不可用的 它是一种高效、快速的按键确定散列码和索引的方法。对于字符串密钥,哈希代码生成函数的效率非常重要。此操作的时间复杂度为O(1)。
通过未定义的索引添加/删除新元素。 carrayobj不仅为新元素分配内存,还删除索引大于插入元素的所有元素。这就是为什么carrayobj执行缓慢的原因。 元素在clist中添加或删除的速度非常快,但访问其索引的时间复杂度为o(n)。这个操作很慢。 在cdictionary中,通过索引访问元素是基于clist列表的,这很耗时。但是添加和删除元素的速度非常快。
新元素由未定义的键添加/删除。 不可用的 不可用的 每个新元素都被插入到clist中,数组在每次添加和删除操作之后不需要重新组织,因此元素的添加和删除执行得非常快。
CPU占用和内存管理。 这需要动态数组。这是一个资源密集型的操作,需要花费大量时间或占用大量内存。 不使用内存管理。每个元素占用一定的内存空间。 这需要动态数组。这是一个资源密集型的操作,需要花费大量时间或占用大量内存。
元素枚举。向量中每个元素必须执行的操作。 由于直接索引访问,执行速度非常快。但是,在某些情况下,需要进行反向枚举(例如,连续删除最后一个元素)。 因为我们只需要枚举所有元素一次,直接引用执行非常快。 因为我们只需要枚举所有元素一次,直接引用执行非常快。

nbsp;

第五章。C限制类文档

5.1。添加、删除和访问元素的方法

5.1.1AddObject()方法

用T键添加一个新的对象类型元素。任何基本类型都可以用作键。

template<typename T>
bool AddObject(T key,CObject *value);

参数

  • [in]键-基本类型(string、ulong、char、enum等)表示的唯一键。
  • [in]value-cobject对象是基本类型。

返回值

如果对象已添加到容器中,则返回true,否则返回false。如果已添加对象的键已存在,则函数返回负数,不添加该对象。

5.1.2containsKey()方法

检查容器中是否存在键为T键的对象。任何基本类型都可以用作键。

template<typename T>
bool ContainsKey(T key);

参数

  • [in]键-基本类型(string、ulong、char、enum等)表示的唯一键。

返回值

如果容器中已存在具有检测到的键的对象,则返回true。Otherwise, return false.

5.1.3.DeleteObjectByKey()方法

根据默认的T键删除对象。任何基本类型都可以用作键。

template<typename T>
bool DeleteObjectByKey(T key);

参数

  • [in]键-基本类型(string、ulong、char、enum等)表示的唯一键。

返回值

如果删除默认键对应的对象,则返回true。如果对象不存在或删除失败,则返回false。

5.1.4.GetObjectByKey()方法

返回由T键表示的对象。任何基本类型都可以用作键。

template<typename T>
CObject* GetObjectByKey(T key);

参数

  • [in]键-基本类型(string、ulong、char、enum等)表示的唯一键。

返回值

返回与默认键对应的对象。解理对象不存在并返回空值。

5.2。内存管理方法

5.2.1cdictionary()构造函数

构造函数创建一个基数组的初始大小等于3的CDictionary对象。

数组根据字典元素的填充和删除来增加或减少空间。

CDictionary();

5.2.2.cDictionary(int容量)构造函数

构造函数创建初始大小等于“capacity”的cdictionary对象。

数组根据字典元素的填充和删除来增加或减少空间。

CDictionary(int capacity);

参数

  • [in]容量-初始元素的数量。

小心

初始化后立即限制数组的大小有助于避免调用Resize()方法,并提高插入新元素的效率。

但是,需要注意的是,如果使用automemory free(true)删除元素,那么容器将自动收缩空间,而不管容量设置和值如何。为避免过早收缩,请在容器完全填充后执行第一个对象删除操作,或者在无法执行时禁用自动内存释放(错误)。

5.2.3.自由模式(布尔模式)方法

设置删除容器中已有对象的方式。

如果启用了删除模式,则删除对象时容器仍保持“删除”模式。析构函数被激活,对象变得不可用。如果删除模式被禁用,对象析构函数将不会被激活,并且仍然可以在程序的其他地方使用。

void FreeMode(bool free_mode);

参数

  • [在]自由模式-对象删除模式指示器

5.2.4.自由模式()方法

返回容器中已删除元素的指示器(请参见FreeMode(bool模式))。

bool FreeMode(void);

返回值

如果对象被删除运算符成功删除,则返回true。否则,返回false。

5.2.5.自动释放内存(bool autofree)方法

设置自动内存管理度量。默认情况下启用自动内存管理启动。在这种情况下,数组会自动减小(减小大小)。如果禁用,则阵列不会缩小。它将显著加快程序的执行,因为没有调用Resize()方法,因为它消耗了大量的资源。但在这种情况下,您必须注意数组的大小,并使用compress()方法手动减少数组空间。

void AutoFreeMemory(bool auto_free);

参数

  • [in]自动内存管理模型指示器

返回值

如果要启用内存管理并自动调用compress()方法,请返回true。否则,返回false。

5.2.6。自动释放内存()方法

返回内存管理模式是否为自动模式的指示器(请参阅free mode(bool free_模式)方法)。

bool AutoFreeMemory(void);

返回值

如果启用内存管理模式,则返回true。否则,返回false。

5.2.7.压缩()方法

减小字典大小并重新组织元素。只有在可能的情况下才会压缩数组。

只有在禁用自动内存管理模式时才能调用此方法。

void Compress(void);

5.2.8。清除()方法

删除自动化中的所有元素。如果启用内存管理度量,则在删除每个元素时调用析构函数。

void Clear(void);

5.3。字典搜索方法

字典中的所有元素都是无关的。每个新元素都与前一个元素相关联。因此,可以按顺序搜索字典中的所有元素。在这种情况下,元素引用是通过链接列表执行的。本节中的方法很容易找到,并且使字典迭代更加方便。

在搜索字典时,可以使用以下构造函数:

for(CObject* node = dict.GetFirstNode(); node != NULL; node = dict.GetNextNode())
  {
   // 节点代表字典的当前元素。
  }

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()方法

返回紧接当前元素之后的下一个元素。如果当前元素是最后一个或未选择,则返回空值。

CObject* GetLastNode(void);

返回值

返回指向当前元素的下一个CObject类型对象的指针。如果当前元素是最后一个或未选择,则返回空值。

5.3.5.GetPrevNode()方法

返回当前元素的前一个元素。如果当前元素是第一个或未选择,则返回空值。

CObject* GetPrevNode(void);

返回值

返回指向当前元素之前的cobject类型对象的指针。如果当前元素是第一个或未选择,则返回空值。

总结

我们已经考虑了大量数据容器的主要特性。每个数据容器都应该在最有效地解决问题的情况下使用。

传统阵列应该用于顺序访问元素足以解决问题的场景。当需要通过唯一键访问元素时,字典和关联数组更高效。如果经常需要元素替换操作:删除、插入和添加,则最好使用列表。

字典能简明扼要地解决棘手的算法问题。字典可以以最有效的方式访问现有元素,而其他数据容器则需要额外的处理能力。例如,基于字典,您可以创建一个事件模型,其中每个onchartevent()类型的事件都传递给管理图形元素的类。为了实现这个目标,每个类的一个实例与该类管理的对象的名称相关联。

因为字典是一种通用的算法,所以它可以在很多地方使用。说明了字典算法的操作简单、功能强大,使其应用方便、有效。

本文由MetaQuotes Software Corp.翻译自俄语原文
,网址为https://www.mql5.com/ru/articles/1334。

附加文件下载zip字典。MQH(37.78 kb)

 

 


MyFxtop迈投(www.myfxtop.com)-靠谱的外汇跟单社区,免费跟随高手做交易!

 

免责声明:本文系转载自网络,如有侵犯,请联系我们立即删除,另:本文仅代表作者个人观点,与迈投财经(www.myfxtop.cn)无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。

著作权归作者所有。
商业转载请联系作者获得授权,非商业转载请注明出处。

風險提示

MyFxtops邁投所列信息僅供參考,不構成投資建議,也不代表任何形式的推薦或者誘導行為。MyFxtops邁投非外匯經紀商,不接觸妳的任何資金。 MYFXTOPS不保證客戶盈利,不承擔任何責任。從事外彙和差價合約等金融產品的槓桿交易具有高風險,損失有可能超過本金,請量力而行,入市前需充分了解潛在的風險。過去的交易成績並不代表以後的交易成績。依據各地區法律法規,MyFxtops邁投不向中國大陸、美國、加拿大、朝鮮居民提供服務。

邁投公眾號

聯繫我們

客服QQ:981617007
Email: service@myfxtop.com

MyFxtops 邁投