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

新评论
 

运行这个

#include <Generic\ArrayList.mqh>
#include <Generic\HashMap.mqh>

CHashMap<int, int> MagicsByDeals;

#define  AMOUNT 1000000

template <typename T>
int Test( T &Object )
{
  int Res = 0;
  
  for(int i = 0; i < AMOUNT; i++)
  {
    int Tmp = 0;
    
    if (Object.TryGetValue(i, Tmp))    
      Res += Tmp;
  }
  
  return(Res);
}

#define  BENCH(A)                                                              \
{                                                                             \
  const ulong StartTime = GetMicrosecondCount();                              \
  A;                                                                          \
  Print("Time[" + #A + "] = " + (string)(GetMicrosecondCount() - StartTime)); \
} 

void OnStart()
{   
  CArrayList<int> CollectionList;
  CHashMap<int, int> CollectionHash;
  
  for(int i = 0; i < AMOUNT; i++)
  {      
    CollectionHash.Add(i, i);
    CollectionList.Add(i);
  }
  
  BENCH(Print(Test(CollectionList)));
  BENCH(Print(Test(CollectionHash)));
}


并得到了这个。

1783293664
Time[Print(Test(CollectionList))] = 24819
1783293664
Time[Print(Test(CollectionHash))] = 91270


CArrayList 比hash变体更快。进入CArrayList的内脏，有这样的内容

template<typename T>
class CArrayList: public IList<T>
  {
protected:
   T                 m_items[];
   int               m_size;

我现在觉得被骗了。CArrayList原来是一个通常的数组的包装器。我以为这是一个带有上一个/下一个指针的普通列表，但它看起来是这样的

template<typename T>
bool CArrayList::TryGetValue(const int index,T &value)
  {
//--- check index
   if((uint)index<(uint)m_size)
     {
      //--- get value by index
      value=m_items[index];
      return(true);
     }
   return(false);
  }
 
fxsaber:
除了结构算法本身，还有一个问题是根据任务的具体情况选择合适的容器。
 
组合器。
除了使用结构本身的算法外，还有一个问题是根据任务的具体情况选择合适的容器。

因此，不同的实现方式的接口可能是相同的。有些失望，不是来自接口，而是来自具体的实现--数组。与哈士奇相比，它就是天堂和大地。

 
fxsaber:

我现在觉得被骗了。CArrayList原来是一个普通数组的包装器。我以为这是一个带有上一个/下一个指针的普通列表，但它是这样的


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

算法、解决方法、性能比较

Sergey Dzyublik, 2017.12.10 20:52


什么样的DBMS，你对一个对数据结构 一无所知的人说什么。
如果没有ArrayList（来自C++的向量）的概念，我们在这里能谈什么.....。


这里更多的是你的不注意...
阅读所有可用列表 -https://www.mql5.com/ru/docs/standardlibrary/generic

CArrayList是C++中std::vector的一个类似物。
CLinkedList很可能是C++中std::list的一个类似物。

 
fxsaber:

运行这个

并得到了这个。

CArrayList比hash变体更快。进入CArrayList的内脏，有这样的内容

我现在觉得被骗了。CArrayList原来是一个通常的数组的包装器。我以为这是一个带有上一个/下一个指针的普通列表，但它看起来是这样的

从历史上看，List根本就不是一个表--它是一个数组。所以，这一切都很好。如果你在泛型中得到一个列表，它可能会被称为LinkedList或类似的东西。

 
fxsaber:

有些沮丧，不是因为接口，而是因为具体的实现--数组。

好吧......。这个容器是一个数组（即C++中向量的类似物），而本地的mql数组非常好，所以arraylist更像是一个事后的想法，使用起来更方便一些。
 

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

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

Sergey Dzyublik, 2017.12.09 01:12


有几条可能的改进建议。

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

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

1) 体积增长因子（容量）不等于1.2，CPrimeGenerator::ExpandPrime方法被用来计算CHashMap中的新体积。

int CPrimeGenerator::ExpandPrime(const int old_size)
  {
   int new_size=2*old_size;
   if((uint)new_size>INT_MAX && INT_MAX>old_size)
      return INT_MAX;
   else
      return GetPrime(new_size);
  }

在这个方法中，旧的集合大小被乘以2，然后对于所得的值，我们从最上面的质数中找到最近的，并将其作为新的体积返回。

关于能力的初始值--我同意，它是非常小的。

但另一方面，总有一些构造函数，你可以明确地指定初始容量。

class CHashMap: public IMap<TKey,TValue>
  {
public:
                     CHashMap(const int capacity);
                     CHashMap(const int capacity,IEqualityComparer<TKey>*comparer);
  }

因此，我认为在这里改变什么没有什么意义。

2）增加一个填充因子参数，确实有助于避免某些情况下的碰撞。最有可能被实施。

 
罗曼-科诺佩尔科。

1) 容量系数不等于1.2，为了计算CHashMap中的新体积，使用CPrimeGenerator::ExpandPrime方法。

在这个方法中，旧的集合大小被乘以2，然后对于所得的值，我们从最上面的质数中找到最近的，并将其作为新的体积返回。

关于能力的初始值--我同意，它是非常小的。

但另一方面，总有一些构造函数，你可以明确地指定初始容量。

这就是为什么我不认为有任何理由要在这里改变一些东西。

2）添加填充因子参数将真正有助于避免某些情况下的碰撞。最有可能的是，它将被实施。

罗曼，我认为你在那里得到了错误的想法。现在有些类甚至不包含最必要的方法。你曾经尝试过使用它们吗？以CRedBlackTree为例，它是红黑树的经典实现。很酷的算法，但没有迭代的可能。你这话是什么意思？还有许多其他你可能需要的东西，但由于某些原因，没有人愿意去实施。GetHashCode的东西太可怕了。对不起，但这还没有达到MQ的水平!

 
瓦西里-索科洛夫。

罗曼，我不认为你在那里做了正确的事情。现在有些泛型类甚至不包含最必要的方法。你到底有没有尝试过使用它们？以CRedBlackTree为例，它是红黑树的经典实现。很酷的算法，但没有迭代的可能。你这话是什么意思？还有许多其他你可能需要的东西，但由于某些原因，没有人愿意去实施。GetHashCode的东西太可怕了。对不起，但这不是MQ的水平!

我很清楚Genric库的所有模板集合都需要迭代器，但如果没有创建嵌套类和从接口多重继承的可能性，你就无法正确实现它们。

我希望听到关于GetHashCode的更多具体评论。

 
罗曼-科诺佩尔科。

...

至于GetHashCode，我想听听更具体的意见。

问题

显然，GetHashCode不能在自定义的MQL5环境中正确实现。这是因为不是所有的对象都能被访问。而且，虽然这个实现对于像double int这样的原始成员来说效果很好，但对于复杂的对象（类、结构甚至枚举）来说，哈希是按名称计算的。如果我们有成千上万的CObjects甚至ENUM_something_that，那么CHashMap和CHashSet将退化为LinkedList。

#include <Generic\HashSet.mqh>
//+------------------------------------------------------------------+
//| Безобидное перечисление, но может быть класс или структура       |
//+------------------------------------------------------------------+
enum ENUM_NUMBER
{
   NUMBER_FIRTS,  // First
   NUMBER_SECOND, // Second
   NUMBER_THIRD   // Third
};
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
{
   CHashSet<ENUM_NUMBER> set_enum;
   for(int i = 0; i < 3; i++)
      set_enum.Add((ENUM_NUMBER)i);
   //-- Поздравляю, мы выродились в LinkedList.... 
   for(int i = 0; i < 3; i++)
   {
      //-- Здесь дикий оверхед по производительности, который тчательно скрывается...
      string is = set_enum.Contains((ENUM_NUMBER)i) ? " присутствует " : " отсутствует ";
      //...
   }
}

我们无法避免这一点，因为我们在用户层面所拥有的只是对象的名称。

//+------------------------------------------------------------------+
//| Returns a hashcode for custom object.                            |
//+------------------------------------------------------------------+
template<typename T>
int GetHashCode(T value)
  {
//--- try to convert to equality comparable object  
   IEqualityComparable<T>*equtable=dynamic_cast<IEqualityComparable<T>*>(value);// <-- Здесь будет получено название класса, структуры или перечисление
   if(equtable)
     {
      //--- calculate hash by specied method   
      return equtable.HashCode();
     }
   else
     {
      //--- calculate hash from name of object
      return GetHashCode(typename(value));
     }
  }

因此，所有复杂类型的 对象的哈希值是相互相等的，这里的搜索代码涉及到一个完整的数组枚举。

//+------------------------------------------------------------------+
//| Determines whether a set contains the specified element.         |
//+------------------------------------------------------------------+
template<typename T>
bool CHashSet::Contains(T item)
  {
//--- check buckets
   if(ArraySize(m_buckets)!=0)
     {
      //--- get hash code for item      
      int hash_code=m_comparer.HashCode(item);
      //--- search item in the slots       
      for(int i=m_buckets[hash_code%ArraySize(m_buckets)]-1; i>=0; i=m_slots[i].next)
         if(m_slots[i].hash_code==hash_code && m_comparer.Equals(m_slots[i].value,item))
            return(true);
     }
   return(false);
  }

事实上，这一点非常关键，以至于它违背了在根部使用所有通用语的意义。 重点是，在大多数情况下，你需要关联或存储复杂的对象：枚举、结构或类。如果你只需要操作简单的类型，你可以用更简单的东西来做。


解决方案

很明显，MQL5是一种类型安全的自定义编程语言，在内部虚拟机中运行。类似Net的东西。这意味着对对象的必要访问仍然存在，但在更多的系统层面。因此。也许可以编写GetHashCode系统函数 与下一个原型。

int GetHashCode(void sample);

它应该如何运作？首先，它应该是杂食性的，而且速度快。它应该给出一个均匀的分布。比如说。

int hash = GetHashCode(3);
// hash = 3

hash = GetHashCode(3.14159);
// hash = 2039485

enum EType{E1, E2, E3};
hash = GetHashCode(E2);
// hash = 2

class C1{};
C1* class1 = new C1();
hash = GetHashCode(class1);
//hash = 39203847

struct S1{};
S1 struct1;
hash = GetHashCode(struct1);
//hash = 83928342

这个功能可以位于系统功能部分。我没有看到任何其他解决办法。

也就是说，我将在稍后提出关于接口、多重继承和其他C++遗留问题的其他建议。
1...111213141516171819202122232425...38
新评论