汎用クラスライブラリ - バグ、説明、質問、使用上の特徴、提案 - ページ 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 はハッシュバリアントより高速です。CArrayListの中身を覗いてみると、こんなものがありました。

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

今は騙されたと思っています。CArrayListは通常の配列のラッパーであることが判明した。Prev/Nextポインタを持つ普通のリストかと思いきや、こんな感じです。

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は、通常の配列のラッパーであることが判明しました。Prev/Nextポインタを持つ普通のリストかと思いきや、こんな感じです。


トレーディング、自動売買システム、ストラテジーテストに関するフォーラム

アルゴリズム、解法、性能比較

セルゲイ・デジブリク さん 2017.12.10 20:52


データ構造を 全く知らない人に、どんなDBMSだ、何を言うんだ。
ArrayList（C++のvector）の概念がなければ、ここで何を語ればいいのか......。


それよりも、あなたの不注意が問題です...。
利用可能なすべてのリストを読む -https://www.mql5.com/ru/docs/standardlibrary/generic

CArrayList は、C++ の std::vector の類似品です。
CLinkedListは、C++のstd::listの類似品である可能性が高い

 
fxsaber

これを実行する

で、これを得た。

CArrayList はハッシュバリアントより高速です。CArrayListの中身を覗いてみると、こんなものがありました。

今は騙されたと思っています。CArrayListは通常の配列のラッパーであることが判明した。Prev/Nextポインタを持つ普通のリストかと思いきや、こんな感じでした。

歴史的に見ると、Listはシートではなく、配列なのです。だから、大丈夫です。genericでリストを取得すると、おそらくLinkedListとかいう名前になると思います。

 
fxsaber

インターフェースではなく、配列という具体的な実装に不満がある。

まあこのコンテナは配列（つまりC++のvectorのアナログ）であり、ネイティブのmql配列は非常に優れているので、arraylistはむしろ後付けで、もう少し便利に使えるようになります。
 

トレーディング、自動売買システム、トレーディング戦略のテストに関するフォーラム

汎用クラスライブラリ - バグ、説明、質問、使用上の特殊性、提案

セルゲイ・デジブリク さん 2017.12.09 01:12


改善可能な提案もいくつかあります。

1) 私の率直な意見ですが、この実装は、ハッシュテーブルを再構築する際に、初期サイズ3およびそれ以降の容量の選択がかなり正しくないと思います。
そうですね、分布の均一化のために素数を選ぶというのは正しいです。
しかし、CPrimeGeneratorの実装は期待に沿うものではなく、素数の抜けがある。
このような「ジェネレータ」の目的は明確で、素数の自動生成で1.2桁の増加率を提供することである。
しかし、これでは係数が小さすぎるのでは？C++でベクトルを扱う場合、この係数はライブラリにもよりますが、通常1.5〜2.0です（演算の平均的な複雑さに強く影響するため）。
この場合、定数係数の後、素数リストの2進法検索で素数に丸めるという 方法が考えられます。
それに初期サイズが3というのは小さすぎる、前世紀に生きているわけではないのだから。

2) 現在、ハッシュテーブルの再構築（Resize）は、容量が100%になったとき（m_entries[]がすべて埋まったとき）にのみ行われています。
このため、あまり均等に配置されていない鍵では、かなりの量の衝突が発生する可能性があります。
オプションとして、ハッシュテーブルの再構築に必要な上限で100%を削減するフィルファクターの導入を検討する。

1) CHashMapの新しいボリュームを計算するためにCPrimeGenerator::ExpandPrimeメソッドが使用されるボリューム成長係数（容量）が1.2に等しくない。

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) fill factor パラメータを追加することで、場合によっては衝突を回避するのに非常に役立ちます。ほとんどの場合、実装されるでしょう。

ローマン、あなたはそこを勘違いしているようですね。今では、最も必要なメソッドさえ含まれていないクラスもあります。使ってみたことはありますか？例えば、CRedBlackTreeは、赤黒木の古典的な実装である。かなりクールなアルゴリズムだが、反復の可能性がない。どういうことですか？他にも必要なものはたくさんあるのですが、なぜか誰もわざわざ実装してくれません。GetHashCodeの件、酷いですね。申し訳ないが、MQのレベルではない！？

 
ワシリー・ソコロフ

ローマン、私はあなたがそこで正しいことを行っているとは思わない。現在、いくつかのジェネリッククラスは、最も必要なメソッドさえ含んでいません。全く使ってみていないのですか？例えば、CRedBlackTreeは、赤黒木の古典的な実装です。かなりクールなアルゴリズムだが、反復の可能性がない。どういうことですか？他にも必要なものはたくさんあるのですが、なぜか誰もわざわざ実装してくれません。GetHashCodeの件、酷いですね。申し訳ないが、これはMQのレベルではない！？

Genricライブラリのすべてのテンプレートコレクションにイテレータが必要なことは十分承知していますが、ネストしたクラスを作成したり、インターフェースからの多重継承が可能でなければ、まともに実装することはできません。

GetHashCodeについて、もう少し具体的なコメントが欲しい。

 
ロマン・コノペルコ

...

GetHashCodeについては、もう少し具体的な指摘が欲しいところです。

問題点

当然ながら、カスタムMQL5環境では、GetHashCodeは正しく実装できません。これは、すべてのオブジェクトにアクセスできるわけではないからです。また、この実装は double int のようなプリミティブなメンバでは問題ありませんが、複雑なオブジェクト（クラス、構造体、さらには列挙体）では名前によってハッシュが計算されます。もし、何千もの CObject や 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

この機能は、システム機能のセクションに配置される可能性があります。他に解決策はないのか

s.e. インターフェイス、多重継承、その他のC++のレガシーなものについては、もう少し後で他の提案をします。
1...111213141516171819202122232425...38
新しいコメント