std :: setはstd :: mapよりどのように遅く設定されていますか？

Question

this problem from acm.timus.ruを解決しようとしていましたが、基本的に与えられた文字列（最大長5000）の異なる部分文字列の数を出力したいと思っていました。

私が提示しようとしている解決策は、制約が与えられた場合、時間制限超過判定のためには必然的に非効率的で運命的です。しかし、これらの2つのソリューションが異なる（少なくとも私が見る/理解できる限り）唯一の方法は、を使用し、もう1つはstd::set <long long>を使用するということです（最後のforループの最初を参照してください。任意の差分ツールで確認できます）。マップソリューションは「テスト3で時間制限を超過する」結果となりますが、設定ソリューションでは「テスト2で時間制限が超過する」という結果になります。つまり、テスト2ではマップソリューションが設定ソリューションより速く動作します。これは、Microsoft Visual Studio 2010コンパイラを選択した場合です。私がGCCを選択すると、両方のソリューションがテスト3のTLEになります。

問題を効率的に解決する方法はありません。私は をどのように尋ねているのですか？std::mapを使用すると、明らかにstd::setを使用するより効率的であると説明できます。私はこの現象の仕組みを見て、誰かが洞察力を持つことができればと思っています。

CODE1（マップ、TLE 3を使用）：

#include <iostream> 
#include <map> 
#include <string> 
#include <vector> 

using namespace std; 

int main() 
{ 
    string s; 
    cin >> s; 
    vector <long long> p; 
    p.push_back(1); 
    for (int i = 1; i < s.size(); i++) 
     p.push_back(31 * p[i - 1]); 
    vector <long long> hash_temp; 
    hash_temp.push_back((s[0] - 'a' + 1) * p[0]); 
    for (int i = 1; i < s.size(); i++) 
     hash_temp.push_back((s[i] - 'a' + 1) * p[i] + hash_temp[i - 1]); 
    int n = s.size(); 
    int answer = 0; 
    for (int i = 1; i <= n; i++) 
    { 
     map <long long, bool> hash_ans; 
     for (int j = 0; j < n - i + 1; j++) 
     { 
     if (j == 0) 
      hash_ans[hash_temp[j + i - 1] * p[n - j - 1]] = true; 
     else 
      hash_ans[(hash_temp[j + i - 1] - hash_temp[j - 1]) * p[n - j - 1]] = true; 
     } 
     answer += hash_ans.size(); 
    } 
    cout << answer; 
} 

CODE2（セット、TLE 2を使用）：

#include <iostream> 
#include <string> 
#include <vector> 
#include <set> 

using namespace std; 

int main() 
{ 
    string s; 
    cin >> s; 
    vector <long long> p; 
    p.push_back(1); 
    for (int i = 1; i < s.size(); i++) 
     p.push_back(31 * p[i - 1]); 
    vector <long long> hash_temp; 
    hash_temp.push_back((s[0] - 'a' + 1) * p[0]); 
    for (int i = 1; i < s.size(); i++) 
     hash_temp.push_back((s[i] - 'a' + 1) * p[i] + hash_temp[i - 1]); 
    int n = s.size(); 
    int answer = 0; 
    for (int i = 1; i <= n; i++) 
    { 
     set <long long> hash_ans; 
     for (int j = 0; j < n - i + 1; j++) 
     { 
     if (j == 0) 
      hash_ans.insert(hash_temp[j + i - 1] * p[n - j - 1]); 
     else 
      hash_ans.insert((hash_temp[j + i - 1] - hash_temp[j - 1]) * p[n - j - 1]); 
     } 
     answer += hash_ans.size(); 
    } 
    cout << answer; 
} 

Answer 1

実際の違いは（私が何かを逃した場合は教えて）、設定された場合に、あなたはどちらの場合も

hash_ans.insert(key); 

を行いながら、マップケースの中にあなたが

hash_ans[key] = true; 

を行うことをしています、既に存在していなければ要素が挿入され、要素は何もしません。どちらの場合も、ルックアップは、対応する要素の位置を特定し、失敗した場合にそれを挿入する必要があります。効果的にそこにあるすべての実装では、コンテナはツリーを使用して、ルックアップを同じように高価にします。さらに、C++標準では実際にはset::insert()とmap::operator[]()が複雑でO（log n）である必要があるため、両方の実装の複雑さは同じでなければなりません。

ここで、パフォーマンスが向上する理由は何でしょうか。 1つの違いは、ある場合には、下にあるツリーのノードにはstringが含まれ、もう一方ではpair<string const, bool>が含まれています。ペアには文字列が含まれているため、マシンのRAMインターフェイスに大きな文字を入力する必要があります。そのため、スピードアップについては説明していません。他のノードがキャッシュラインからプッシュされるように、ノードのサイズを大きくすることができます。これは、マルチコアシステムではパフォーマンスが悪い可能性があります。要約すると

は、私が試してみたいくつかのものがあります：

1. がセット
   で同じデータを使用して、私はstruct data: string {bool b};でこれを行うだろうつまり、同様のを持っている必要があり、構造体の文字列をバンドルバイナリレイアウトをマップの要素として使用します。比較器としては、less<string>を使用します。そのため、文字列のみが実際に比較に使用されます。

2. マップ上にinsert（）を使用する
   これは問題ではないと思われますが、最後に挿入が行われない場合でも、挿入によって引数のコピーが発生する可能性があります。私はそれがしないことを願っていますので、私はこれが何かを変えると確信していません。

3. デバッグをオフにする
   ほとんどの実装では、イテレータが検証される診断モードがあります。これを使用して、C++が「未定義の動作」としか言わず、あなたの肩や肩をすくめてしまうエラーを捕まえることができます。このモードは、しばしば複雑さの保証を満たさず、常にオーバーヘッドがあります。

4. コードを読み取る
   setとmapの実装に異なる品質と最適化レベルがある場合は、その違いを説明できます。フードの下では、マップとセットが同じタイプのツリー上に構築されていることを期待しています。

Answer 2

セット、この場合のマップよりも少しだけ速くなります私は推測する。それでもTLE 2やTLE 3が本当に大したことではないと思っているのではないでしょうか。それは、あなたが指定したサブミット時にテスト2で同じ解決時間制限を設定し、次にテスト3でタイムリミットを設定するように制限されている場合に発生する可能性があります。私はいくつかの解決策をタイムリミットだけに渡し、私はそれらを再提出し、彼らは失敗するでしょう。

この特有の問題は、私がうこのんSufixツリーを使って解決した問題です。

Answer 3

使用する実装アルゴリズムによって異なります。通常、セットはキーフィールドを使用してのみマップを使用して実装されます。そのような場合、地図とは対照的にセットを使用するための非常にわずかなオーバーヘッドがあります。私が見