6

acm.timus.ru からこの問題を解決しようとしていましたが、これは基本的に、特定の文字列 (最大長 5000) の異なる部分文字列の数を出力することを望んでいます。

私が提示しようとしている解決策は、非常に非効率的であり、制約を考えると制限時間超過の評決を受ける運命にあります。ただし、これら2つのソリューションが異なる唯一の方法は（少なくとも私が見る/理解できる限り）、一方がを使用std::map<long long, bool>し、他方が使用する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;
}
4

3 に答える 3

2

私が見た実際の違い（何か見逃していたら教えてください）は、マップの場合にあなたがすることです

hash_ans[key] = true;

セットケースであなたがしている間

hash_ans.insert(key);

どちらの場合も、何もしない要素がまだ存在しない限り、要素が挿入されます。どちらの場合も、ルックアップは該当する要素を見つけて、失敗時に挿入する必要があります。事実上すべての実装で、コンテナーはツリーを使用するため、ルックアップのコストが等しくなります。さらに、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 の実装の品質と最適化のレベルが異なる場合、これが違いを説明している可能性があります。内部的には、マップとセットの両方が同じタイプのツリー上に構築されることを期待しているので、ここでもあまり期待できません。

于 2013-04-12T18:46:27.827 に答える
1

使用される実装アルゴリズムによって異なります。通常、セットはキー フィールドのみを使用するマップを使用して実装されます。このような場合、マップではなくセットを使用すると、ごくわずかなオーバーヘッドが発生します。

于 2013-04-12T13:21:36.037 に答える
1

この場合、セットはマップよりも少しだけ速いと思います。それでも、TLE 2 や TLE 3 は大した問題ではないので、それほど気にする必要はないと思います。制限時間に近づいている場合、同じソリューションが特定の送信のテスト 2 で制限され、次回はテスト 3 で時間が制限される場合に発生する可能性があります。私はそれらを再送信しますが、失敗します。

この特定の問題は、Ukonen Suffix ツリーを使用して解決しました。

于 2013-04-12T12:32:14.613 に答える