std :: mapをstd :: stringキーとintキーで使用するコスト？

Question

私は個々のマップクエリが最大ログ（N）時間を取ることを知っています。しかし、私はマップキーとして文字列を使用する多くの例を見てきました。たとえば、intの代わりにキーにstd :: stringを関連付けるのにかかるコストはどれくらいですか？

std::map<std::string, aClass*> someMap;対std::map<int, aClass*> someMap;

ありがとう！

Answer 1

すでに言及した文字列を比較する時間の複雑さに加えて、文字列キーは、アイテムがコンテナに追加されるたびに追加のメモリ割り当ても発生させます。場合によっては、例えば、並列性の高いシステムでは、グローバルなアロケータ・ミューテックスがパフォーマンス上の問題の原因となる可能性があります。

一般に、状況に応じて最適な代替方法を選択し、実際のパフォーマンステストに基づいて最適化するだけです。ボトルネックとなるものを判断することは悪名高いほど難しい。

Answer 2

コストの差は、2つの文字列を比較する場合と比較して2つの整数を比較する場合のコストの差にリンクされます。

2つの文字列を比較するときは、最初の文字に到達するためにポインタを間接参照して比較する必要があります。それらが同じ場合は、2番目の文字を比較するなどしなければなりません。文字列の接頭辞が長い場合、プロセスが少し遅くなる可能性があります。しかし、intを比較するほど速くなることはほとんどありません。

Answer 3

O（n）時間（nは最大共有プレフィックス）で文字列が比較されるのに対し、intは実際のO（1）時間で比較できるのはコストです。また、文字列の格納には、整数よりも多くの領域が消費されます。 これらの明らかな違い以外に、大きなパフォーマンスコストはありません。

Answer 4

漸近的なパフォーマンスの解析アルゴリズムは、実行する必要のある操作と、それらが式に加えるコストに基づいています。そのためには、実行された操作が何であるかをまず知り、そのコストを評価する必要があります。

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

をすべて合計するとあなたがキーとしてトータルコストを整数を使用すると、O(log N)と等価であるO(log N)*(O(1) + O(1))であることを得るまでの費用がかかる。（O(1)はO表記は静かに隠していることに一定に隠されます。

あなたがキーとして文字列を使用する場合は、総コストはO(log N)*(O(L) + O(1))です一定の時間操作が隠れている場所nをより高価な線形演算O(L)で置き換えてO(L * log N)に変換することができます。つまり、文字列でキーされたマップ内の要素の位置付けのコストは、マップに格納された要素の数の対数とキーとして使用される文字列の平均長を掛けた値に比例します。

big-O表記法は、問題の規模が大きくなったときにアルゴリズムがどのように動作するかを決定する分析ツールとして使用するのが最も適していますが、未処理のパフォーマンスにとって重要な多くの事実を隠します。

最も単純な例として、キーを汎用文字列から1000文字の配列に変更すると、表記法を省略した定数内でそのコストを非表示にすることができます。 1000文字の配列を比較することは、ちょうどかなり時間がかかります。漸近表記では、整数と同様に、ちょうどO(log N)の演算になります。

通常、定数時間操作と見なされる要素の作成コストは、問題のパラメータに依存しないという理由だけで、多くの他の隠されたコストが発生します（ブロックを見つけるコスト各割り当てにおけるメモリの量は、データセットに依存するのではなく、アルゴリズム解析の範囲外のメモリの断片化、malloc内のロックを取得するコスト、2つのプロセスが同じブロックを返そうとしないことを保証するコストプロセッサの数、プロセス、およびそれらが実行するメモリ要求の数に依存するロックの競合によって決まります。アルゴリズムの範囲外です）。 big-O表記でコストを読むときは、それが本当に何を意味するのかを意識しなければなりません。

Answer 5

まず、実際のアプリケーションでは、文字列キーかintキーのどちらが目立つ違いがあるのか​​疑問です。あなたのアプリケーションをプロファイリングすることが重要であるかどうかを教えてくれます。

class Key { 
public: 
    unsigned hash; 
    std::string s; 

    int cmp(const Key& other) { 
     int diff = hash - other.hash; 
     if (diff == 0) 
      diff = strcmp(s, other.s); 
     return diff; 
} 

は今、あなたは二つの文字列のハッシュにint型の比較をやっている：それは問題でない場合

は、あなたがこの（未テスト）のようなものであるためにあなたのキーを変更することができます。ハッシュが異なる場合、文字列は確かに異なっています。ハッシュ値が同じ場合は、Pigeonhole Principleのために文字列を比較する必要があります。

Answer 6

等しい数のキーで2つのマップの値にアクセスするだけの簡単な例 - 1つのintキー同じint値の別の文字列は、文字列で8倍長くなります。