通用类库 - 错误、说明、问题、使用功能和建议 - 页 23

新评论
  
//+------------------------------------------------------------------+
//|                                              CompareFunction.mqh |
//|                   Copyright 2016-2017, MetaQuotes Software Corp. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic\Interfaces\IComparable.mqh>
//+------------------------------------------------------------------+
//| Compares two objects and returns a value indicating whether one  |
//| is less than, equal to, or greater than the other.               |
//+------------------------------------------------------------------+
int Compare(const bool x,const bool y)
  {
   if(x>y)
      return(1);
   else if(x<y)
      return(-1);
   else
      return(0);
  }


该函数是全局声明的。由于这个原因，与用户对他们的比较存在冲突。

'Compare' - function already defined and has body

为了减少命名冲突，作者能否将所有全局辅助性的Generic函数变成public-static-methods？

 

fxsaber:

为了减少命名冲突，作者能否将所有全局辅助性的Generic函数变成public-static-methods？

关于交易、自动交易系统和策略测试的论坛

编译器错误：'operator=' - 结构有对象，不能复制

fxsaber 2018.09.10 11:00 2018.09.10 10:00:13 RU
阿列克谢-纳沃伊科夫。
这只是暂时的。如果你想包含某人的库，你会发现作者和你一样写得很 "原始"，使用相同的类和函数的名字。

我将用巨额资金钉住他们。

巨集呢？
 
A100:
巨集呢？

我不是在说我自己。

 

我已经读了所有的讨论页，但还是不明白如何使用它？

谁能给我一些例子？

 
Vladimir Pastushak:

我已经读了所有的讨论页，但还是不明白如何使用它？

谁能给我一些例子？

忘了它吧。你不能像现在这样使用它。使用标准的CObject+CDictionary 来代替。对于大多数任务来说，这已经足够了。

 
Vasiliy Sokolov:


级别描述
巧夺天工图一个键值集。允许你根据项目的钥匙有效地插入、检索和搜索。该键必须是唯一的。例如，CHashMap可以立即找到一个具有指定号码的订单，其中号码被用作一个键。

关于按键检索一个值的问题。在库的代码中，这个方法看起来是这样的

//+------------------------------------------------------------------+
//| Find index of entry with specified key.                          |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
int CHashMap::FindEntry(TKey key)
  {
   if(m_capacity!=NULL)
     {
      //--- get hash code from key
      int hash_code=m_comparer.HashCode(key)&0x7FFFFFFF;
      //--- search pair with specified key
      for(int i=m_buckets[hash_code%m_capacity]; i>=0; i=m_entries[i].next)
         if(m_entries[i].hash_code==hash_code && m_comparer.Equals(m_entries[i].key,key))
            return(i);
     }
   return(-1);
  }

ME导航工具（ALT+G和CTRL+-）按来源拒绝在这个库中工作。因此，要追溯其逻辑是非常困难的。特别是，我还没有弄清楚高亮循环中的初始值。但有一种理解是，如果有一个速度，这个值应该远远小于钥匙的数量。


请澄清这个想法，在这个函数中实现的速度是多少？过度杀伤力明显存在。但显然，由于某种原因，它很短。


SZ 我一步一步地浏览了我的调试器。所有清楚的例子 TKey = int: m_bucket[Array[i]] = i。只有当Array[i] == Array[j] (i != j)的碰撞不清楚。

 
fxsaber:

这个问题是关于通过键来获取值。在库的代码中，这个方法看起来像这样
请澄清一下这个想法，是什么让这个功能变得快速？过冲的情况明显存在。但显然，由于某种原因，它很短。

有一次，我正在回顾和描述CHashMap 的工作原理
，你需要搜索一下条目，可能在这个主题中。

 

关于交易、自动交易系统和交易策略测试的论坛

通用类库 - 错误、描述、问题、使用的特殊性和建议

Sergey Dzyublik, 2017.12.11 13:41

简要介绍一下当前CHashMap 的实现。

template<typename TKey,typename TValue>
class CHashMap: public IMap<TKey,TValue>
  {
protected:
   int               m_buckets[];                        
   Entry<TKey,TValue>m_entries[];
   int               m_count;
   int               m_free_list;
   int               m_free_count;
   IEqualityComparer<TKey>*m_comparer;
   bool              m_delete_comparer;

     .................................

     .................................

  }

首先，我们来看看什么是Entry<TKey,TValue>。
从本质上讲，它是CLinkedList中的一个Node，它包含。

- 放在容器中的键和值
- 缓存的键的哈希值 - hash_code
- next - 指向下一个Entry<TKey,TValue> 的 "指针"，目的是通过单连接的列表进行碰撞解决。


m_entries[] - "单元格 "数组，用于放置添加的键和值、哈希代码、下一步。阵列的大小与容量相对应。
m_count - 指定m_entries中第一个未使用的单元格的索引。初始值为0，增长到容量，接下来是重建所有阵列，增加容量和所有阵列的大小。
m_buckets[] - m_entries[]的索引阵列。默认值为-1。阵列大小与容量相对应。


没有碰撞，为CHashMap 容器添加唯一值。

  1. 按键计算哈希值，得到哈希代码
  2. 按索引m_count将key、value、hash_code放入m_entries[]。(next = -1，因为该例子没有碰撞)
  3. 在m_buckets[]中按hash_code % (ArraySize(m_buckets))把刚刚添加的元素的索引值放在m_entries[]中（这是m_count）。
  4. 增加m_count +1

在没有碰撞的情况下，通过CHashMap 容器中的键获取值。

  1. 从钥匙计算哈希值，得到哈希代码
  2. 从m_buckets[]中，通过hash_code % (ArraySize(m_buckets))得到的值是数组m_entries[]的索引。
  3. 使用获得的索引m_buckets[hash_code % (ArraySize(m_buckets))]，从数组m_entries[]获得我们的值。

碰撞解决。

对于不同的键，可能发生hash_code_key_1 % (ArraySize(m_buckets)) 等于hash_code_key_2 % (ArraySize(m_buckets)) 这被称为碰撞。
所有添加到m_entries[]的有碰撞的元素都通过与next的单连接列表进行链接（见Entry<TKey,TValue> 结构）。
而m_buckets[]总是指向这个碰撞列表中第一个头部元素的索引。
我们得到的不是一个有碰撞的大名单，而是许多小名单。


碰撞，在CHashMap 容器中通过键获取值。

  1. 在钥匙上，我们计算哈希值，得到哈希码。
  2. 使用索引hash_code % (ArraySize(m_buckets))，从m_entries[]数组中获取值。
  3. 我们可以看到，Next的值不等于-1，这表明有一个碰撞
  4. 走过由m_entries[]的元素组成的单条目列表，比较所寻求的值和保存的键是否相等


从CHashMap 容器中删除一个值。

- 当删除m_entries[]中的一个单元格时，不做任何删除处理；该单元格被标记为空闲，hash_code = -1。
- 自由单元形成自己的自由单元列表（使用与Entry<TKey,TValue>相同的下一个），m_free_list
- 自由单元首先用于向容器添加新值。
-m_free_count 用于控制当前自由细胞的数量。


重建哈希表（增加容量过程） :

- 只有当容量达到100%时才会重建。
- 下一个容量大小从列表中取出。

const static int  CPrimeGenerator::s_primes[]=
  {
   3,7,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,
   1103,1327,1597,1931,2333,2801,3371,4049,4861,5839,7013,8419,10103,12143,14591,
   17519,21023,25229,30293,36353,43627,52361,62851,75431,90523,108631,130363,156437,
   187751,225307,270371,324449,389357,467237,560689,672827,807403,968897,1162687,1395263,
   1674319,2009191,2411033,2893249,3471899,4166287,4999559,5999471,7199369
  };

- m_entries[] 和 m_buckets[] 数组被递增。
- m_buckets[]被清除并完全重新填充，基于来自m_entries[]的数据（键的缓存哈希值-hash_code）。


描述的行为来自2017.12.11
 目前，可能已经添加/改变了一些细节/系数。

 
Sergey Dzyublik:

我曾一度拆解并描述了CHashMap 的工作原理
，你需要寻找条目，可能在这个主题中。

我发现它在

关于交易、自动交易系统和策略测试的论坛

通用类库 - 错误、描述、问题、使用的特殊性和建议

Sergey Dzyublik, 2017.12.07 14:21


在这个例子中，哈希值是学生的生日。
我们有一个有365个架子的柜子，里面有学生的日记。
我们把每本日记放在与学生的生日相对应的架子上。

我们需要学生彼得罗夫的日记，我们知道他的出生时间。
现在通过O(1)中的出生日期，我们可以很容易地找到彼得罗夫的日记，以及任何其他学生的日记。
例外情况是两个学生有相同的生日--这被称为撞车。

解决碰撞问题是利用额外的信息来找出我们需要的两个或多个期刊中的哪一个。
通过列表进行碰撞解决，就是简单地将碰撞中的所有条目一个一个地找出来，找到一个匹配。撕下每本日记，看看是谁的。
一个子标题是组织一个参与碰撞的项目的哈希表，但以不同的标准。例如，按学生出生的时间。


如果你对这个话题感兴趣--我建议在youtube上学习MailRu关于算法和数据结构 的课程。

关于交易、自动交易系统和交易策略测试的论坛

通用类库 - 错误、描述、问题、使用的特殊性和建议

Sergey Dzyublik, 2017.12.08 14:40

关于这个话题的基础知识是为懒惰的人准备的。
https://www.slideshare.net/mkurnosov/6-32402313

在现实中，它要复杂得多，并在相关文献或良好的 "算法和数据结构 "课程中讨论。


谢谢，调试有帮助。有小名单的碰撞。捋了捋这条线，吓了一跳。事实证明，我一直在讨论这个问题......

 
Sergey Dzyublik:
从2017.12.11 开始描述的行为

截至目前，可能已经增加/改变了一些细节/系数。

非常感谢您!对你的描述有很大帮助。

1...161718192021222324252627282930...38
新评论