3 
std::map<string, int> dict;
for(int i = 0; i < 300; ++i)
{
    dict["afsfgsdg"] = i*i;
    dict["5t3rfb"] = i;
    dict["fddss"] = i-1;
    dict["u4ffd"] = i/3;
    dict["vgfd3"] = i%3;
}

文字列の値はコンパイル時に既知であるため、コンパイラは実行時にこれらの文字列をハッシュするのではなく、コンパイル時にそれらをハッシュしますか?

4

3 に答える 3

6

std::map何もハッシュしません。比較を使用して要素を検索し、その O(lg n ) 境界は、マップにn 個のキーがある場合に必要な比較の数です。比較自体のコストについては何も表現していません。

つまり、プログラムは、最初にポインター比較を行うことによって、いくつかの短絡的な文字列比較を使用する可能性がありますが、比較の数は、最悪の場合 (項目がツリーの葉の 1 つにある場合、典型的な赤の場合) では対数のままになります。ブラック ツリーの実装)。

于 2013-06-04T12:47:26.257 に答える
3

コンパイラは、実行時にこれらの文字列をハッシュするのではなく、コンパイル時にそれらをハッシュしますか?

いいえ、std::mapハッシングを使用しないため、赤黒木または類似の二分木です。

毎回ツリー内でルックアップを実行します。

最初にコンパイラは に変換"afsfgsdg"しstd::string、次にマップ内の文字列を O(log n) 検索します。

于 2013-06-04T12:46:46.513 に答える
1

漸近的なパフォーマンスのアルゴリズムを分析することは、実行する必要がある操作と、それらが方程式に追加するコストに取り組んでいます。そのためには、最初に実行された操作が何であるかを知り、次にそのコストを評価する必要があります。

バランスのとれた二分木 (たまたまマップ) でキーを検索するには、O( log N ) の複雑な操作が必要です。これらの各操作は、キーが一致するかどうかを比較し、キーが一致しなかった場合は適切なポインター (子) に従うことを意味します。これは、全体のコストが、これら 2 つの操作のコストの log N 倍に比例することを意味します。後続のポインターは一定時間の操作 O(1) であり、キーの比較はキーに依存します。整数キーの場合、比較は高速 O(1) です。2 つの文字列の比較は別の話です。O(L) に関係する文字列のサイズに比例して時間がかかります (ここでは、より一般的な N の代わりに文字列パラメーターの長さとして意図的に L を使用しています。

すべてのコストを合計すると、整数をキーとして使用すると、総コストは O( log N )*( O(1) + O(1) ) になり、O( log N ) と同等になります。(O(1) は、O 表記が黙って隠している定数に隠されます。

文字列をキーとして使用する場合、総コストは O( log N )*( O(L) + O(1) ) であり、一定時間操作はよりコストのかかる線形操作 O(L) によって隠され、次のように変換できます。 O( L * log N )。つまり、文字列をキーとするマップ内の要素を検索するコストは、マップに格納されている要素数の対数に、キーとして使用される文字列の平均長を掛けた値に比例します。

于 2013-06-04T12:48:25.633 に答える