c++ - 比较两个向量，使其更有效

Question

使用 kcachegrind 并在调试模式下运行代码，我发现我的程序的瓶颈是比较两个向量的点。

if (v1 == v2) {
  // DO
}

我怎样才能使它更有效率？这是否更好

if (v1[0] == v2[0]) {
   if (v1 == v2) {
      // DO
   }
}

第一行将过滤一些无用的比较。

在此之前我尝试过

if (!v2.empty())
  if (v1 == v2) 
   // DO

但是我发现它们几乎总是不空的。因此也包括了 empty() 的额外时间。

我不得不说向量的大小大多很小。2~4个元素。在极少数情况下，它们会扩展到 10 个。

更新： 感谢 Mats Petersson，似乎通过在优化模式下编译，有更多的性能改进。

score 5 · Accepted Answer

如果它真的是你程序的瓶颈，你应该重构你的设计。比较两个范围总是在O(N)中运行。

如果您真的想保留您的设计，那么您可以选择：保留这些性能或进行猜测。您可能想要寻找变化最大的向量部分。当然，如果你有完全随机的 push_backs，那就不值得了。然后，您可以首先开始测试这些元素。

score 4 · Accepted Answer

我会试一试，但我希望内部结构v1 == v2变成：

 for(int i = 0; i < v1.size && i < v2.size; i++)
 {
    if (v1[i] != v2[i])
       return false;
 }

[上面可能不是它的实际实现方式，而是显示为“它像这样工作”]

因此，如果索引 0 是最常见的不同元素，您只会几乎没有收获。

无论如何，尝试一下（这可能比在这里问更快！）

当然，鉴于评论，这个特定问题的主要部分是“不要在关闭优化的情况下对代码进行基准测试/分析”。当测量微小的细节和紧密的循环代码时，很容易获得 10 倍的性能下降，然后优化被关闭 [如果“调试模式”还启用额外的检查和此类事情以确保没有越界使用，等等，我们可以看到慢 100-1000 倍的代码]

score 2 · Accepted Answer

第二个代码块只是稍微高效一点，但它是不正确的：考虑如果一个或两个向量为空会发生什么。这里唯一的节省来自避免在第一个字符中字符串不同时的调用开销和循环设置开销。这些节省不值得使您的程序复杂化，因为它们太小了。

如果您想节省更多，请考虑使用以不同方式实现相等的自定义类替换字符串：例如，您可以预先计算并存储向量的哈希码，并仅在哈希时使用逐元素比较代码不同。

score 2 · Accepted Answer

由于您的类型是基本整数类型，您可以尝试使用 * 将它们作为内存块进行比较memcmp

memcpy获取两个缓冲区 ( void*) 并返回 0 如果缓冲区具有相等的内存块

bool equal = v1.size() == v2.size() && memcmp(&v1.front(), &v2.front(), sizeof(v1[0]) * v1.size()) == 0;

(*) - 我强调了这个词，试图表明它没有必要会有所帮助，但这是一种可能性

score 0 · Accepted Answer

我想您将拥有的任何实现都将从验证数组大小是否相等开始，然后继续逐个检查元素并比较它们（尽快返回 false - 在第一个差异上）。所以你的建议没有多大帮助，std::mismatch 也没有。

但是，如果您可以对向量进行排序，那么更智能的检查可能是可行的。你能？

5 回答 5