std::set 比 std::map 更慢的原因是什么？

Question

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

我即将呈现的解决方案效率极低，受到限制条件的影响，注定会超时。然而，这两种解决方案唯一的区别（至少在我看来/理解的范围内）是一个使用std :: map<long long，bool>，而另一个使用std :: set <long long>（请参见最后一个循环的开始。其余部分相同，您可以通过任何diff工具进行检查）。映射解决方案会导致“测试3超时”，而集合解决方案会导致“测试2超时”，这意味着测试2的情况下，映射解决方案比集合解决方案更快。如果我选择Microsoft Visual Studio 2010编译器，则是这种情况。如果我选择GCC，则两种解决方案都会导致在测试3上超时。

我是一名有用的助手，可以为您进行文本翻译。以下是需要翻译的内容：

我并不是在询问如何高效地解决问题。我想问的是，如何解释使用 std::map 显然比使用 std::set 更有效率。我无法理解这种现象的机制，希望有人能够提供任何见解。

Code1（使用 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;
}

代码2（使用set，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;
}

- Armen Tsirunyan

---

你有尝试过自己做一些实验，比如自己测量时间或者进行性能分析吗？ - PlasmaHH

@PlasmaHH：我相信我已经提供了足够的证据，证明其中一个比另一个慢。我想知道这是如何可能的。 - Armen Tsirunyan

@PlasmaHH：我认为这是一个完全合适的问题。 - Games Brainiac

除此之外，我认为来自某些黑盒子的时间限制超过消息并不是比较不同程序速度的好方法，因为你不知道它们如何限制时间、准确性以及其他影响因素。对这两个程序进行分析将更准确地告诉你它们在速度上的差异，并且很可能足以让你自己看到这是如何可能的，或者让其他人通过更详细地查看时间花费的位置来解释给你。 - PlasmaHH

Answer 1

我看到的实际区别（如果我漏掉了什么，请告诉我）在于，在地图案例中，您需要执行以下操作：

hash_ans[key] = true;

在集合情况下，您需要执行以下操作：

hash_ans.insert(key);

在这两种情况下，如果元素不存在，则会插入一个元素；否则不执行任何操作。在这两种情况下，查找需要定位相应的元素并在失败时插入它。实际上，在几乎所有的实现中，容器将使用树，使得查找同样昂贵。更重要的是，C++标准实际上要求set::insert() 和 map::operator[]() 的时间复杂度为O(log n)，因此两个实现的复杂度应该是相同的。

那么，导致其中一个执行速度更快的原因是什么呢？一个区别是，在一种情况下，底层树的节点包含一个string，而在另一种情况下，它是一个pair<string const, bool>。由于该对包含一个字符串，所以它必须更大，并对机器的RAM接口施加更多压力，因此这并不能解释速度提升。它可能会扩大节点大小，以至于其他节点被推出缓存行，这对于多核系统的性能来说可能是不好的。

总之，有一些事情我想尝试：

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

2. 在map上使用insert()
   我认为这不应该是个问题，但即使最终不进行插入，插入可能会导致参数的复制。我希望它没有，所以我对这个改变并不太有信心。

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

4. 查看代码
   如果set和map的实现具有不同的质量和优化水平，则可能会解释差异。但在幕后，我期望map和set都是建立在相同类型的树之上，因此在这里也没有太大的希望。

- Ulrich Eckhardt

Answer 2

一个集合在这种情况下只比映射略快一点，我想。但是我认为你不应该太在意TLE 2或TLE 3，因为这并不是什么大不了的事情。如果你接近时间限制，同样的解决方案可能会在给定提交的测试2上达到时间限制，而下一次则在测试3上达到时间限制。我有一些解决方案仅在时间限制内通过测试，我敢打赌，如果我重新提交它们，它们将失败。

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

- Ivaylo Strandjev

---

那就是问题所在。Set 并不比 Map 更快！！ - Armen Tsirunyan

我已经多次提交了两者以确保。 - Armen Tsirunyan

@ArmenTsirunyan 我不会浪费时间在这上面。你最好在你的机器上对两种解决方案进行基准测试，看看 map 的性能是否比 set 更好。否则，最好专注于实际解决方案。 - Ivaylo Strandjev

Answer 3

这取决于所使用的实现算法。通常情况下，集合是使用映射实现的，只使用键字段。在这种情况下，使用集合相对于使用映射会有非常轻微的开销。

- OlivierD

---

我记得在STLport中，set和map都是基于相同的底层树容器构建的，因此它们的性能应该是类似的。即使不是这样，我也看不出有什么开销无法通过内联来消除，所以我目前不同意你的观点。 - Ulrich Eckhardt

@doomster 我确实说了“非常轻微” :) 由于OP实际上没有提到执行时间的差异，除了“map失败测试2，set失败测试3”，因此很难说。根据给定的信息，人们倾向于认为GCC实现使用相同的算法。正如我在我的答案中（含蓄地）所说，Microsoft可能使用不同的实现。 - OlivierD