c++ - std::set 为什么比 std::map 慢？

Question

我试图解决 this problem from acm.timus.ru这基本上是要我输出给定字符串的不同子字符串的数量(最大长度 5000)。

我将要提出的解决方案效率极低，并且在限制条件下注定会被判定为“超出时间限制”。然而，这两种解决方案唯一不同的地方(至少据我所知)是使用 std::map<long long, bool>。 , 而另一个使用 std::set <long long> (请参阅最后一个 for 循环的开头。其余部分相同，您可以通过任何 diff 工具进行检查)。 map 解决方案导致“测试 3 超出时间限制”，而设置解决方案导致“测试 2 超出时间限制”，这意味着测试 2 map 解决方案比设置解决方案在其上工作得更快。如果我选择 Microsoft Visual Studio 2010 编译器，就会出现这种情况。如果我选择 GCC，那么两种解决方案都会在测试 3 中产生 TLE。

我不是问如何高效解决问题。我在问什么 是如何解释使用 std::map显然比使用 std::set 更有效.我只是没有看到这种现象的机制，希望有人能有任何见解。

代码 1(使用 map ，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

我看到的实际差异(如果我遗漏了什么请告诉我)是在 map 案例中你做的

hash_ans[key] = true;

在设定的情况下你做

hash_ans.insert(key);

在这两种情况下，都会插入一个元素，除非它已经存在，否则它什么都不做。在这两种情况下，查找都需要找到相应的元素并在失败时将其插入。实际上，在每个实现中，容器都将使用树，使得查找同样昂贵。更重要的是，C++ 标准实际上需要 set::insert()和 map::operator[]()复杂度为 O(log n)，因此两种实现的复杂度应该相同。

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

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

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

2. 在 map 上使用 insert()
   我不认为这应该是一个问题，但插入可能会产生参数的拷贝，即使最后没有插入。我希望它不会，所以我不太相信这会改变任何事情。

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

4. 阅读代码
   如果 set 和 map 的实现具有不同的质量和优化级别，这可以解释差异。不过，在幕后，我希望 map 和 set 都构建在同一类型的树上，所以这里也不抱太大希望。