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

新评论
 
阿列克谢-奥列什金。

一个很好的理论例子!在实践中，有没有人操作过成千上万的交易？

p.s. 我不是要证明它是垃圾，没有人需要它。我正在努力理解对真实交易的价值。我不是一个一般的理论家，而是一个纯粹的实践者。

这不是关于1000个交易或只有10个交易。关键是，我们写的是短代码，对10个或1000000..... 交易同样有效。
 

简要介绍一下目前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. 按hash_code % (ArraySize(m_buckets))将刚刚添加到m_entries[]的元素的索引值放入m_buckets[]（这是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）。



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

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

Sergey Dzyublik, 2017.12.09 01:12

熟悉了CHashMap 的实现
 说实话，我很喜欢它。


有几个可能的改进建议。

1）在我看来，实现中包含了不太正确的容量选择--包括初始大小3和重建哈希表时的后续容量。
是的，应该选择一个素数来实现分布的均匀性，这是正确的。
然而，CPrimeGenerator的实现并不符合预期，包含了质数的遗漏。
这样一个 "生成器 "的目的很明确--提供一个增量系数为1.2的自动生成素数。
然而，这个系数不是太小了吗？在C++中，对于向量来说，系数通常是1.5-2.0，这取决于库（因为它强烈地影响着操作的平均复杂性）。
出路可能是一个常数系数，然后通过对素数列表的二进制搜索，将数字四舍五入 到素数。
而3的初始规模太小了，我们不是生活在上个世纪。

2) 目前哈希表只有在容量100%满时才会被重建（调整大小）（所有m_entries[]都被填满）。
正因为如此，对于分布不是很均匀的钥匙，可能会有很多碰撞。
作为一种选择，考虑引入一个填充因子，通过必要的限制来减少100%，以执行哈希表重建。


 
阿列克谢-奥列什金。

在实践中，有没有人对成千上万的交易进行过操作？

是的，数百万次的历史电话一传十十传百，很多人都在练习。

 
Vasiliy Sokolov:

关于堡垒的每一个第一。

这很清楚。

通过hft算法发送订单 和拿起它们进行分析是不同的事情。发送时不需要这些哈希值，分析时也不需要，因为它们是以不同方式分析的。

所以，没有冒犯的意思。你还需要理论。

 
阿列克谢-奥列什金。

这很清楚。

通过hft算法发送订单和稍后拿起它们进行分析是不同的事情。你不需要这些哈希值来发送，你也不需要它们来分析，因为这不是正在分析的东西。

所以，没有冒犯的意思。我们也需要理论。


我不使用洗碗机，我使用海绵。
完全没有冒犯的意思。洗碗机很蹩脚，它们有什么用。

 
阿列克谢-奥列什金。

这很清楚。

通过hft算法发送订单和以后提出来分析是不同的事情。你不需要这些哈希值来提交它们，你也不需要它们来分析，因为我们事后会分析其他东西。

所以，没有冒犯的意思。我们也需要理论。

什么恩怨情仇？继续写你的拐杖。

 
谢尔盖-迪尤布利 克。

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

谢谢，我将在解析源代码时使用它。

 
瓦西里-索科洛夫。

什么恩怨情仇？继续写你的拐杖。

问题是，我没有使用这里提供的主题，我想了解我的想法是否正确。我对普通的关联数组很满意，但我总是希望能做得更好。
 
fxsaber:

谢谢，我将在解析来源时使用它。


在添加新的键值对时，省略了对容器中键是否存在的检查，先执行。
但这并不重要。

 
面对一个错误信息，由于没有这个
//+------------------------------------------------------------------+
//| Gets the element at the specified index.                         |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::TryGetValue(const int index,T &value) const

请在整个 "通用 "中修复这样的东西。

1...101112131415161718192021222324...38
新评论