在 C++ 向量中迭代的最快方法

Question

我正在寻找有关矢量迭代的一些技巧。我正在尝试完成一项挑战，其中您必须实现一个函数 (SumOfTwo)，该函数将两个向量和一个总和作为参数，并且必须检查两个向量中是否有任何一对数字，如果相加可以给出总和作为参数传递。

我的函数工作正常，只是它没有涵盖 500 毫秒的时间限制。我觉得有比两个 for 循环更好的迭代两个向量的方法，但我觉得很卡...

bool sumOfTwo(std::vector<int> a, std::vector<int> b, int v) {
    if((a.empty()) || b.empty()){
        return false;
    }
    for (std::vector<int>::iterator it1 = a.begin(); it1<=a.end(); ++it1)     {
            for (std::vector<int>::iterator it2 = b.begin(); it2<=b.end(); ++it2) {
                if ((*it1 + *it2) == v){
                    return true;
                }
            }
    }
    return false;
}

Answer 1

关于样式提示，将您的代码更改为以下内容（为了效率和整洁）

bool sumOfTwo(const std::vector<int>& a, const std::vector<int>& b, int v) {
    for (auto i1 : a)     {
            for (auto i2 : b) {
                if ((i1 + i2) == v){
                    return true;
                }
            }
    }
    return false;
}

考虑使用 std::unordered_set 并对其进行交叉引用，以确定求和是否可以实现最大效率。请记住 std::unordered_set 中的查找是 O(1)

Answer 2

为什么算法很慢？

目前您正在迭代两个向量，但您正在进行嵌套迭代。我们称向量的长度为 m 和 n（任意）。您当前的算法是 O(n*m)，这对于大向量来说相当慢。

如果 m = n = 1000，在最坏的情况下（没有两个元素的总和为 v），您将进行数百万次运算——哇！

如何提高性能？

我可以想到一个巨大的加速：给定一个向量 a、一个向量 b 和所需的总和 v，您可以从v 和 a 的元素差异，并检查 b 中的任何值是否在集合中。

伪代码为：

if a.empty or b.empty:
    return false

set = emptySet

for e in a:
    set.add(v - e)

for e in b:
    if e in set:
        return true

return false

无序集中的查找应该是 O(1)，所以现在这是一个 O(max(m, n)) 算法，其中 m 是 a 的长度，n 是 [=15 的长度=].

如果 m = n = 1000，在最坏的情况下，您现在正在执行数千次操作——好多了，对吗？

在 C++ 中实现这个留给 reader。 :)

提示：通过引用传递对于向量来说是个好主意。

Answer 3

感谢大家的大力帮助！我解决时间限制的方法是：

bool sumOfTwo(std::vector<int>& a, std::vector<int>& b, int v) {
   if((a.empty()) || b.empty()){
       return false;
   }
   std::unordered_set<int> s;
   for (const auto i : a) {
       s.insert(v-i);
   }
   for (const auto i : b) {
      auto search = s.find(i);
      if (search != s.end()) {
          return true;
      }
   }
   return false;
}

在 C++ 向量中迭代的最快方法

Quickest way to iterate in a C++ vector

c++

iteration

vector

time-limiting

为什么算法很慢？

如何提高性能？