6

我试图从 acm.timus.ru 解决这个问题，它基本上希望我输出给定字符串的不同子字符串的数量（最大长度 5000）。

我即将提出的解决方案效率极低，并且由于限制因素而注定要做出超出时间限制的判决。但是，这两种解决方案的唯一区别（至少据我所见/理解）是一种使用std::map<long long, bool>，而另一种使用std::set <long long>（参见最后一个 for 循环的开头。其余部分相同，您可以检查通过任何差异工具）。地图解决方案导致“测试 3 超过时间限制”，而设置解决方案导致“测试 2 超过时间限制”，这意味着测试 2 使得地图解决方案在其上的工作速度比设置解决方案更快。如果我选择 Microsoft Visual Studio 2010 编译器，就会出现这种情况。如果我选择 GCC，那么这两种解决方案都会导致测试 3 中的 TLE。

我不是在问如何有效地解决问题。我要问的是如何解释 usingstd::map显然比 using 更有效std::set。我只是看不到这种现象的机制，希望有人能有任何见解。

代码 1（使用地图，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()andmap::operator[]()的复杂度为 O(log n)，因此两种实现的复杂度应该是相同的。

现在，一个人表现更好的原因可能是什么？一个区别是，在一种情况下，底层树的节点包含 a string，而在另一种情况下，它是 a pair<string const, bool>。由于该pair包含一个字符串，它必须更大并且对机器的RAM接口施加更大的压力，所以这并不能解释加速。它可以做的是扩大节点大小，以便将其他节点推离缓存线，这可能不利于多核系统的性能。

总而言之，我会尝试一些事情：

  1. 在集合中使用相同的数据
    我会这样做，struct data: string {bool b};即将字符串捆绑在一个结构中，该结构应该具有与地图元素类似的二进制布局。作为比较器，使用less<string>, 以便只有字符串实际参与比较。

  2. 在地图上使用 insert()
    我不认为这应该是一个问题，但是插入可能会导致参数的副本，即使最后没有插入也是如此。我希望它不会，所以我不太相信这会改变任何事情。

  3. 关闭调试
    大多数实现都有一个诊断模式，其中迭代器被验证。您可以使用它来捕获 C++ 只说“未定义行为”的错误，耸耸肩并在您身上崩溃。这种模式通常不满足复杂性保证，并且总是有一些开销。

  4. 阅读代码
    如果 set 和 map 的实现具有不同的质量和优化级别，这可以解释差异。在引擎盖下，我希望地图和场景都建立在相同类型的树上，所以这里也不抱太大希望。

于 2013-04-12T18:46:27.827 回答
1

我猜在这种情况下，集合只比地图快一点。不过我认为你不应该考虑那么多，因为 TLE 2 或 TLE 3 并不是什么大不了的事。如果您接近给定提交的测试 2 的相同解决方案时间限制以及下一次测试 3 的时间限制，则可能会发生这种情况。我有一些解决方案仅在时间限制内通过了测试，我敢打赌，如果我重新提交他们会失败。

我使用 Ukonen 后缀树解决了这个特殊问题。

于 2013-04-12T12:32:14.613 回答
1

这取决于使用的实现算法。通常集合是使用仅使用键字段的映射来实现的。在这种情况下，使用集合而不是地图会产生非常小的开销。

于 2013-04-12T13:21:36.037 回答