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

[fxsaber]

セルゲイ・デジュブリク

ハッシュは、辞書のサイズと予想される要素数が許す限り、平均O(1)である。
あとは、コリジョンハンドリングの 実装次第で、リストを通してもいいし、もっとサブハシを使ってもいいかもしれない......。

私の専門用語の無知が、その中に入っていく過程を妨げています。事例を待ちたいと思います。ワラントやティックなど、簡潔で要点を押さえたものを希望します。

[Vladimir Karputov]

fxsaber

私の専門用語の無知が、その中に入っていく過程を妨げています。事例を待ちたいと思います。ワラントやティックなど、簡潔で要点を押さえたものを希望します。

令状は論外です。お得感に興味がある。

[Sergey Dzyublik]

fxsaber

wikiで読みました。直感的な理屈を全く理解していないようなケース。

365日が辞書の大きさの限界です
クラスの生徒数がコレクションの予想数
誕生日の一致は衝突

[fxsaber]

セルゲイ・デジュブリク

365日というのは、辞書のサイズに制限があるんです。
クラスの生徒数がコレクションの予想数
誕生日の一致は衝突

ありがとうございます。その用語の定義はより明確です。この「パラドックス」がスレッドの話題とどう関係するのかが理解できないのですが？

[Sergey Dzyublik]

セルゲイ・デジュブリク

365日が辞書の大きさの限界です
クラスの生徒数が予想される数 コレクションのアイテム数
誕生日の一致は衝突

この例では、ハッシュは生徒の誕生日である。
365段の棚を持つ食器棚には、生徒の日記が保管されています。
日記は誕生日に合わせて棚に並べています。

弟子ペトロフの日記が必要で、彼がいつ生まれたかもわかっている。
さて、O(1)の生年月日から、ペトロフの日記も、他の生徒の日記も、簡単に見つけることができる。
ただし、2人の生徒が同じ誕生日の場合は例外で、これをコリジョン（衝突）と呼びます。

衝突を解決することは、余分な情報を使って、2つ以上の雑誌のうちどれが必要かを見つけることである。
リストによるコリジョン解消は、コリジョンの全エントリーを1つずつ調べて一致するものを見つけるだけです。日記を一枚一枚はがして、誰のものかを確認する。
小見出しは、衝突に関係する項目のハッシュテーブルを、別の基準で整理したものです。例えば、生徒が生まれた時間によって。

もし興味があれば、MailRuのアルゴリズムとデータ構造についての youtube講座をお勧めします。

[fxsaber]

セルゲイ・デジュブリク

この例では、ハッシュは生徒の誕生日である。
365段の棚がある食器棚には、生徒の日記を収納しています。
誕生日に合わせた棚に、それぞれの手帳を並べています。

ペトロフの日記が必要で、彼がいつ生まれたかもわかっている。
さて、O(1)の生年月日から、ペトロフだけでなく、もう一人の学生の日記も簡単に見つけることができる。
ただし、2人の生徒が同じ誕生日の場合は例外で、これをコリジョン（衝突）と呼びます。

衝突を解決することは、余分な情報を使って、2つ以上の雑誌のうちどれが必要かを見つけることである。
リストによるコリジョン解消は、コリジョンの全エントリーを1つずつ調べて一致するものを見つけるだけです。日記を一枚一枚はがして、誰のものかを確認する。
小見出しは、衝突に関係する項目のハッシュテーブルを、別の基準で整理したものです。例えば、生徒が生まれた時間単位で。

もし興味があれば、MailRuのアルゴリズムとデータ構造についての youtube講座をお勧めします。

もともとそういうイメージだったんです。ただ、ハイライトの方は理解できない。Hashはインデックスではないので、ポインタの配列のオフセットで見つけることができます。すべて同じように、リストで検索する必要があります。そして、これは適切なソートによる2値探索です。

[Sergey Dzyublik]

fxsaber

最初からこのようにイメージしていました。ただ、ハイライトの方は理解できない。Hashはインデックスではないので、ポインタの配列のオフセットで見つけることができます。リストで検索する必要がありますが。そして、これは適切なソートによる2値探索です。

ハイライトは口頭での誤字です))と既に修正済み。
ハッシュはインデックスである。辞書のサイズに付与される。

各棚の高さは同じで、棚番号によって、どの高さで探せばいいのかがよくわかります。O(1)

[Vasiliy Sokolov]

連想配列についてできるだけシンプルに#1

Genericで紹介されている多くのアルゴリズムは、何らかの形で連想配列や辞書をベースにしています。また、最もよく使われる2つのアルゴリズムのうちの1つです。プログラミングの作業の9割は配列と辞書でカバーされている、というのは正解に近いと思います。実践に移る前に、辞書の働きをできるだけわかりやすく、意図的に細部を簡略化して説明しよう。

ここでは、非常に簡単な例として、通常の単語リストで辞書を紹介する。例えば、アルファベットで始まる単語がいくつかあるとします。

string words[] = {"apple", "cat", "fog", "dog", "walk", "zero"};

英語のアルファベットは26文字です。サイズ26要素の文字列の配列を作成してみましょう。

string dictionary[26];

ここで、単語をその最初の文字に対応するインデックスに格納することに同意すれば、簡単な辞書ができあがる。ゼロからインデックスを作成します。単語「apple」は、文字「a」がアルファベットの最初の文字であるため、インデックス0に格納され、「cat」はインデックス1、「dog」はインデックス3、「fog」はインデックス4、「walk」はインデックス24、「0」は最後のインデックス25に格納されることになります。

なお、インデックス5～23は使用しません。これはメモリの無駄遣いですが、例えば「walk」という単語が存在すればインデックス24に位置することが分かっているので、即座にアクセスすることができます。

最初の空の辞書を書いてみましょう。

//+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link      "http://www.mql5.com"
#property version   "1.00"
string words[26];

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   return words[index] != NULL;
}
bool Add(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   if(words[index] == NULL)
   {
      words[index] = word;
      return true;
   }
   return false;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   Add("apple");
   if(Contains("apple"))
      printf("Словарь содержит слово apple");
   else
      printf("Словарь не содержит слово apple");
  }
//+------------------------------------------------------------------+

そこに「りんご」という言葉を加えて検索すれば、この言葉にアクセスするための検索操作は瞬時に完了する。なぜなら、この言葉を見つけるためのインデックスをあらかじめ知っているからです。他のインデックスバリアントはありえないので、全リストを見る必要はない。これは、おおよそすべての辞書の基本である。

次の例では、同じ文字から始まる単語を格納できるように改良します。

[Vasiliy Sokolov]

連想配列についてできるだけシンプルに #2

同じアルファベットで始まる単語が異なることがある。前の辞書に「apple」と入れて、そこに「application」を入れようとすると、うまくいきません。インデックス0はワードアップルで占められる。この場合、ハッシュ関数の衝突と言うことになります。今回のハッシュ関数は非常にシンプルで、単語の最初の文字の番号を返すので、この関数の衝突は非常に頻繁に起こるでしょう。同じ文字で始まる異なる単語を格納するために、要素を配列ではなく、配列の配列に格納する足し算を行います。この場合、インデックス0には、"apple "と "application "という2つの単語からなる別の配列が格納される。

//+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link      "http://www.mql5.com"
#property version   "1.00"
#include <Arrays\ArrayObj.mqh>
#include <Arrays\ArrayString.mqh>
CArrayString* WordsArray[26];

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   CArrayString* words = WordsArray[index];
   if(words == NULL)
      return false;
   for(int i = 0; i < words.Total(); i++)
      if(word == words.At(i))
         return true;
   return false;
}
bool Add(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   CArrayString* words;
   if(WordsArray[index] == NULL)
      WordsArray[index] = new CArrayString();
   words = WordsArray[index];
   for(int i = 0; i < words.Total(); i++)
      if(word == words.At(i))
         return false;
   words.Add(word);
   return true;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   //ArrayResize(WordsArray, 26);
   Add("apple");
   Add("application");
   if(Contains("application"))
      printf("Словарь содержит слово application");
   else
      printf("Словарь не содержит слово application");
  }
//+------------------------------------------------------------------+

これで、同じ文字で始まる言葉も辞書に登録されるようになりました。しかし、同じ頭文字の単語にアクセスするコストは増加します。なぜなら、今は「アプリケーション」という単語が辞書にあるかどうかを調べるために、「a」で始まるすべての単語を完全に検索する必要があるからです。 もし、ハッシュ関数が1文字違いの単語でも異なる数字を生成するとしたら、同じインデックスを持つ単語を試す確率は0になり、任意の要素へのアクセスはo(1)になる傾向がある。.実際の辞書では、まさにこのようなことが起こっており、そこで使われる関数は衝突を防止しているので、これらのコレクション内の項目へのアクセスは非常に高速で、ほとんどブルートフォースではないと断言できる。

[Реter Konow]

ワシリー・ソコロフ

連想配列はできるだけシンプルに

Genericで紹介されている非常に多くのアルゴリズムは、何らかの形で連想配列や辞書をベースにしています。また、最もよく使われる2つのアルゴリズムのうちの1つです。プログラミングの9割は配列と辞書でカバーできる、と言っても過言ではないでしょう。実践に移る前に、辞書の働きをできるだけわかりやすく、意図的に細部を簡略化して説明しよう。

ここでは、非常に簡単な例として、通常の単語リストで辞書を紹介する。例えば、アルファベットで始まる単語がいくつかあるとします。

英語のアルファベットは26文字です。サイズ26要素の文字列の配列を作成してみましょう。

ここで、単語をその最初の文字に対応するインデックスに格納することに同意すれば、簡単な辞書ができあがる。ゼロからインデックスを作成します。文字「a」はアルファベットの最初の文字なので、単語「apple」は私たちのインデックス0に格納され、インデックス1には「cat」、インデックス3には「dog」、インデックス4にはfog、インデックス24にはwalk、最後のインデックス25には0が格納されることになります。

なお、インデックス5～23は使用しません。これはメモリの無駄遣いですが、例えば「walk」という単語が存在すればインデックス24に位置することが分かっているので、即座にアクセスすることができます。

最初の空の辞書を書いてみましょう。

そこに「りんご」という言葉を加えて検索すれば、この言葉にアクセスするための検索操作は瞬時に完了する。なぜなら、この言葉を見つけるためのインデックスをあらかじめ知っているからです。他のインデックスバリアントはありえないので、全リストに目を通す必要はない。これは、おおよそすべての辞書の基本である。

次の例では、同じ文字から始まる単語を格納できるように改良します。

この解決策は完璧です。すべては、可能な限りシンプルに。関数、配列、正しいデータ整理のみ。そういうことなんです。