汎用クラスライブラリ - バグ、説明、質問、使用上の特徴、提案 - ページ 35

新しいコメント
 
Renat Fatkhullin:

ほとんど不可能で、もし遭遇してもアクセスは超有効です。

どんなレベルの効率でも衝突はよくない。返信ありがとうございました。肝に銘じておきます。

 
fxsaber:

どんなレベルの効率でも衝突はよくない。ご返信ありがとうございました。肝に銘じておきます。

ハッシュマップは定義上、コリジョンフリーではありません。

 
fxsaber #:

コリジョンに関する質問です。このような場合、ぶつかる可能性はあるのでしょうか？

27,000枚のレコードが生産された場合。

特にコレクションが大きく（リサイズ）なると、常にコリジョンが発生します。ハッシュはさらにギャング番号に切り捨てられ、その数は常に限られている（理想的には1つに等しい）ので。

結論

1.マップに重要なのは、ハッシュ関数の暗号的な安定性ではなく、そのスピードです。ハッシュ関数は、ただ良いランダム性を提供する必要があり、それだけである。

2.リサイズは絶対に避けた方が良い。ハッシュ関数の衝突ではなく、リサイズが主な描画の原因となっているのです。可能な限り、常にあらかじめ設定した数のアイテムでコレクションを初期化する。正確な数値が分からなくても、おおよその数値を伝えておくと、アルゴリズムの大きな助けになります。

3.衝突は規則的な圧縮のメカニズムである。衝突によって、idが159, 4'569'209, 29'459'876の3つのレコードは、最後の2つの値が両方ともインデックス2のギャングに該当しても、30 000 000長ではなく、3長さの配列に格納することが可能です。

 
Vasiliy Sokolov #:

2.リサイズは絶対に避けた方が良い。ハッシュ関数の衝突ではなく、リサイズが主な欠点です。可能な限り、あらかじめ設定した数のアイテムでコレクションを初期化する。正 確な数値が分からなくても、おおよその数値を伝えることで、アルゴリズムの大きな助けになります。

例を挙げて示してください。

今のところこれしか使ってません。

//+------------------------------------------------------------------+
//| Adds the specified key and value to the map.                     |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::Add(TKey key,TValue value);
//+------------------------------------------------------------------+
//| Gets the value associated with the specified key.                |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::TryGetValue(TKey key,TValue &value);
 
fxsaber #:

例を示してください。

今のところこれしか使ってません。

CHashMap コレクションを作成するときは、capacity パラメータを受け入れるコンストラクタのいずれかを使用します。リサイズ時のパフォーマンスについては、CDicionaryについての記事を参照してください。このアルゴリズムについては、完全なウォークスルーがあります。

 

CHashMapに非常に珍しい挙動を発見しました。

// Демонстрация невозможности доступа по ключу после первого добавления.

#include <Generic\HashMap.mqh>

void OnStart()
{
  // Отсортированный массив неповторяющихся цен.
  const double Array[] =
{1.70682, 1.70691, 1.70700, 1.70709, 1.70710, 1.70717, 1.70721, 1.70742, 1.70749, 1.70752, 1.70757, 1.70766, 1.70768, 1.70769, 1.70771, 1.70773, 1.70774, 1.70777,
 1.70782, 1.70785, 1.70786, 1.70797, 1.70804, 1.70808, 1.70813, 1.70850, 1.70868, 1.70879, 1.70881, 1.70883, 1.70895, 1.70905, 1.70918, 1.70921, 1.70936, 1.70962,
 1.70966, 1.71022, 1.71027, 1.71047, 1.71056, 1.71080, 1.71081, 1.71093, 1.71096, 1.71109, 1.71112, 1.71119, 1.71120, 1.71127, 1.71128, 1.71135, 1.71136, 1.71138,
 1.71145, 1.71147, 1.71148, 1.71150, 1.71155, 1.71159, 1.71162, 1.71164, 1.71168, 1.71172, 1.71203, 1.71204, 1.71210, 1.71269, 1.71289, 1.71293, 1.71299, 1.71334,
 1.71337, 1.71343, 1.71357, 1.71358, 1.71367, 1.71371, 1.71374, 1.71380, 1.71402, 1.71410, 1.71414, 1.71425, 1.71426, 1.71427, 1.71429, 1.71430, 1.71446, 1.71474,
 1.71477, 1.71518, 1.71521, 1.71558, 1.71587, 1.71588, 1.71617, 1.71620, 1.71624, 1.71626, 1.71629, 1.71635, 1.71644, 1.71654, 1.71655, 1.71658, 1.71661, 1.71664,
 1.71689, 1.71700, 1.71712, 1.71718, 1.71727, 1.71752, 1.71769, 1.71775, 1.71780, 1.71782, 1.71786, 1.71792, 1.71795, 1.71797, 1.71798, 1.71801, 1.71815, 1.71827,
 1.71832, 1.71835, 1.71841, 1.71869, 1.71895, 1.71908, 1.71951, 1.71984, 1.71992, 1.72008, 1.72086, 1.72132, 1.72147, 1.72204, 1.72208, 1.72212, 1.72215, 1.72227,
 1.72230, 1.72233, 1.72234, 1.72336, 1.72374, 1.72378, 1.72381, 1.72405, 1.72454, 1.72464, 1.72477, 1.72488, 1.72541, 1.72553, 1.72562, 1.72588, 1.72625, 1.72651,
 1.72653, 1.72671, 1.72679, 1.72685, 1.72720, 1.72783, 1.72849, 1.72852, 1.72854, 1.72925, 1.72927, 1.72938, 1.72953, 1.72956, 1.72960, 1.72970, 1.72975, 1.72979,
 1.72996, 1.73014, 1.73028, 1.73034, 1.73050, 1.73056, 1.73084, 1.73085, 1.73119, 1.73137, 1.73176, 1.73278, 1.73328, 1.73337, 1.73344, 1.73345, 1.73362, 1.73377,
 1.73385, 1.73399, 1.73401, 1.73405, 1.73425, 1.73432, 1.73445, 1.73446, 1.73447, 1.73451, 1.73458, 1.73468, 1.73491, 1.73512, 1.73515, 1.73516, 1.73537, 1.73545,
 1.73553, 1.73580, 1.73581, 1.73598, 1.73611, 1.73630, 1.73635, 1.73643, 1.73658, 1.73678, 1.73694, 1.73695, 1.73698, 1.73712, 1.73713, 1.73721, 1.73746, 1.73748,
 1.73750, 1.73751, 1.73781, 1.73782, 1.73789, 1.73821, 1.73843, 1.73845, 1.73854, 1.73857, 1.73858, 1.73861, 1.73874, 1.73892, 1.74003, 1.74060, 1.74062};

  CHashMap<double, int> Index; // Будем по double-ключу хранить int-значения.
  
  for (int i = ArraySize(Array) - 1; i >= 0; i--)
    Index.Add(NormalizeDouble(Array[i], 5), 0); // Каждую цену массива используем в качестве ключа.
    
  // Все это было подготовкой, чтобы продемонстрировать поведение ниже.
  
  const double Price = 1.75141; // Берем новую цену.
  
  if (Index.Add(Price, 0)) // Если получилось добавить ее в качестве ключа.
  {
    int Value = 0;

    Print(Index.TryGetValue(Price, Value)); // (false) Проверяем, получается ли посмотреть данные по этому ключу.
    
    if (Index.Add(Price, 0)) // Пробуем повторно добавить в качестве ключа
      Print(Index.TryGetValue(Price, Value)); // (true) Проверяем, получается ли посмотреть данные по этому ключу.
  }
}


false
true

鍵が追加されたはずなのに、何も読み取れないようです。しかし、再びキーを追加すると、すぐに読めるようになります

これはBAGなのか？


例題の価格1.75141を 別のものに置き換えると、正しく動作します。


デバッグをしない 巨大なコードからこの挙動を検出し、このような簡潔な例を作るのは地獄のような難しさでした。

 
Vasiliy Sokolov #:

可能な限り、常に決められた数の要素でコレクションを初期化する。正確な数値が分からなくても、おおよその数値を伝えておくと、アルゴリズムの大きな助けになります。

上の例では、コンストラクタで容量を設定してみました。ある容量の値から、この例は正しく動作し始めます。

でも、これは偶然だと思うんです。

 
fxsaber #:

CHashMapに非常に珍しい挙動を発見しました。


鍵が追加されたはずなのに、何も読み取れないようです。しかし、再びキーを追加すると、すぐに読めるようになりました

これはBAGなのか？


例題の価格1.75141を 別のものに置き換えると、正しく動作します。


デバッグをしない 巨大なコードからこの挙動を検出し、このような簡潔な例を作るのは地獄のような難しさでした。

修正され、本日のリリースに含まれます。
 
MetaQuotes #:
修正され、本日のリリースに含まれます。

ありがとうございました。編集を拝見しました。


 
fxsaber #:

上の例では、コンストラクタで容量を設定しようとしました。ある容量の値から、この例は正しく動作し始めます。

でも、これは偶然だと思うんです。

そう、不具合に不具合を重ねているのです。ジェネリックの使用を強くお勧めします。

1...2829303132333435363738
新しいコメント