汎用クラスライブラリ - バグ、説明、問題、使用例、提案

Vasiliy Sokolov  

2017年12月6日現在、MetaTrader 5の 標準配信セットには、データの保存と抽出のための効率的なアルゴリズムを実装した、いわゆるGenericクラスが 含まれています。このブランチは、これらのクラスについて説明し、それらを使った作業の例や、作業を改善するための提案のために作成されています。

ジェネリックとは? Genericは、カスタムデータ型を 格納することができる特別なテンプレートクラスです。型判別はコンパイル時に行われるため、高い性能を発揮する。

なぜジェネリックなのか? プログラミングの初心者は、通常、配列という1種類のコレクションにしか馴染みがない。しかし、配列で作業することが有効でない作業も多くあります。100万個のユニークな識別子からなる配列があるとします。例えば、1000個の注文があるとします。この1000件の注文の中に、番号Nの注文が1件あるかどうかを確認するにはどうすればよいですか?汎用クラスの一つを使えば、この作業はほぼ即座に、検索する要素の数に依存しない一定の時間で達成することができる。他にも、プログラマが考案したアルゴリズムよりも、一般的なコレクションから正しいアルゴリズムを選択した方が高速になる問題もある。

一般的なアルゴリズム。 以下は、一般的なクラスと、その機能の簡単な説明の表です。

クラスクラス説明
CArrayList .アレイ。サイズ自動再分割機能付き。アウトオブバウンズ制御を必要としないアレイを利用できるようにします。
CHashMapキー・バリュー・セット。キーに基づいた要素の挿入、取り出し、検索を効率的に行えるようにする。キーは一意でなければならない。例えば、CHashMapは、番号をキーとして、指定した番号の注文を瞬時に探し出すことができます。
CHashSetユニークな要素のセットです。CHashMapと同じことができますが、キーは必要ありません。このコレクションに格納された要素は、複製してはならない。また、アイテムの検索、取得、追加を瞬時に行うことができます。
CLinkedListリンクリストのこと。アイテムの出し入れが簡単にできます。ただし、アイテムの数によっては、探すのに直線的な時間がかかる。
キューキューヒープです。FIFO型のキューを整理する。
CStackスタックLIFO型のキューを整理
CRedBlackTreeRedBlackTreeです。要素の挿入、取り出し、検索を高速(対数時間)に行うことができます。CHashMapやCHashSetとは異なり、more than, less than, betweenなどの 追加のリレーショナルアルゴリズムを効率的に実装することができる。
CSortedMapキーでソートされたセット。キーバリューを格納する。この場合、キーはソートされています。
CSortedSet値でソートされたセット。順序付けられた値の集合を格納する。

これらのクラスの実装機能については、後ほど見ていくことにします。

fxsaber  
ワシリー・ソコロフ

例えば1000件の注文など、100万件の一意な識別子の配列があるとします。1000件の注文の中に、番号Nの注文が1件あるかどうかを確認するにはどうしたらよいでしょうか。汎用クラスの一つを使えば、この作業はほぼ瞬時に、検索する要素の 数に依存しない一定の時間で達成される。

全く詳しくない。しかし、強調された部分は非論理的に聞こえます。

Vasiliy Sokolov  

残念ながら、ライブラリは発売されたばかりで、まだ生ものです。すでにその中の最初のエラーを発見しています(マーカーでエラーを強調します)。

CSortedSet でエラーが発生しました。

//+------------------------------------------------------------------+
//| Class CSortedSet<T>.                                             |
//| Usage: Represents a collection of objects that is maintained in  |
//|        sorted order.                                             |
//+------------------------------------------------------------------+
template<typename T>
class CSortedSet: public ISet<T>
  {
   ...
   bool              TryGetMin(T &min)    { return(m_tree.TryGetMin(min)); }
   bool              TryGetMax(T &max)    { return(m_tree.TryGetMin(max)); }
   ...
  }

TryGetMaxメソッドは、TryGetMinメソッドと同様に、最大要素の代わりに最小要素を返します。

Vasiliy Sokolov  
fxsaber

...しかし、強調された部分は非論理的に聞こえます。

それはなぜでしょうか?

fxsaber  
ワシリー・ソコロフ

それはなぜでしょうか?

ハッシュを作り、昇順に並べる。しかし、いずれにせよ捜索は行われるでしょう。

TheXpert  
fxsaber

全く詳しくない。しかし、強調された部分は非論理的に聞こえます。

平均時間 O(1) 最悪 O(n) であり、性能はハッシュに大きく依存する。
Vasiliy Sokolov  
fxsaber

ハッシュを作る ...

用語を定義しておこう。瞬間的なものはない。どんな操作にも時間がかかる。瞬間的と 言ったのは、初心者のプログラマーにもわかるように単純化しているんです。厳密には、複雑さにはいくつかのクラスが ありますが、これから扱う主なものは以下の通りです。

  • 一定の複雑さcO(1)。
  • 対数:cO(log n)です。
  • リニア:cO (n)。
  • 非線形ランタイムを必要とするアルゴリズム。

ハッシュ値の計算など、技術的な操作の際に発生する定数のようなもので、あえてc 記号を導入しました。しかし、この場合、定数cの 最適化の議論は、このスレッドの主題から外れています。ここでは、一般的なクラスとその実際の適用にのみ興味があります。

Vasiliy Sokolov  
fxsaber

ハッシュを作り、昇順に並べる。しかし、いずれにせよ検索は行われるでしょう。

コンビナート です。
平均時間 O(1) 最悪 O(n) で、性能はハッシュに大きく依存する。

+

p.s. 説明のために、CHashMapを正しく扱わないと、これと同じ性能がO(n)に落ちてしまう例を示します。

Ivan Gurov  

名前をもっとシンプルに、論理的にしたほうがいい。例えば、CArrayListは Arrayなのか、mql5におけるListなのか、両方の実装なのか。

そのため、疑問や混乱が生じるのです。IMHOは、C#やJavaではなく、stlを使うべきだと考えています。あるいは、前のCを削除して、ArrayListだけにしてください。


普通の名前を作れば。

- 読みやすさが何倍にもなります。

- あなただけのmql5スタイルができあがります。

- 初心者の方でもすぐに操作できるようになります(stlが標準装備されているため)

Vladimir Karputov  
ワシリー・ソコロフ

...

例えば、何千もの案件の中から検索するような例を挙げていただければと思います。
理由: