12

我有一个嵌套的 for 循环结构,现在我在每次迭代开始时重新声明向量:

void function (n1,n2,bound,etc){

    for (int i=0; i<bound; i++){
             vector< vector<long long> > vec(n1, vector<long long>(n2));
             //about three more for-loops here
    }
}

这使我可以“重新开始”每次迭代,这非常有效,因为我的内部操作主要采用 vec[a][b] += some value 的形式。但我担心大 n1 或大 n2 会很慢。我不知道向量/数组/等的底层架构,所以我不确定处理这种情况的最快方法是什么。我应该改用数组吗?我应该以不同的方式清除它吗?我应该完全不同地处理逻辑吗?

编辑:向量的大小在技术上不会改变每次迭代(但它可能会根据函数参数而改变)。我只是想清除它/等,以便在所有其他情况下程序尽可能快。

编辑:

我的不同方法的结果:

Timings (for a sample set of data):
reclaring vector method: 111623 ms
clearing/resizing method: 126451 ms
looping/setting to 0 method: 88686 ms
4

8 回答 8

12

我对小范围有明确的偏好(即,如果变量只在那里使用,则在最里面的循环中声明变量),但对于大范围,这可能会导致大量分配。

因此,如果此循环是一个性能问题,请尝试在循环外声明变量并仅在循环内将其清除 - 但是,这只有在向量的(保留)大小保持相同时才有优势。如果您正在调整向量的大小,那么无论如何您都会得到重新分配。

不要使用原始数组——它不会给你任何好处,只会给你带来麻烦。

于 2012-04-13T13:23:50.270 回答
10

这是一些测试几种不同方法的代码。

#include <chrono>
#include <iostream>
#include <vector>

int main()
{
  typedef std::chrono::high_resolution_clock clock;

  unsigned n1 = 1000;
  unsigned n2 = 1000;

  // Original method
  {
    auto start = clock::now();
    for (unsigned i = 0; i < 10000; ++i)
    {
      std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2));
      // vec is initialized to zero already

      // do stuff
    }
    auto elapsed_time = clock::now() - start;

    std::cout << elapsed_time.count() << std::endl;
  }


  // reinitialize values to zero at every pass in the loop
  {
    auto start = clock::now();
    std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2));
    for (unsigned i = 0; i < 10000; ++i)
    {
      // initialize vec to zero at the start of every loop
      for (unsigned j = 0; j < n1; ++j)
        for (unsigned k = 0; k < n2; ++k)
            vec[j][k] = 0;

      // do stuff
    }
    auto elapsed_time = clock::now() - start;

    std::cout << elapsed_time.count() << std::endl;
  }

  // clearing the vector this way is not optimal since it will destruct the
  // inner vectors
  {
    auto start = clock::now();
    std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2));
    for (unsigned i = 0; i < 10000; ++i)
    {
      vec.clear();
      vec.resize(n1, std::vector<long long>(n2));

      // do stuff
    }
    auto elapsed_time = clock::now() - start;

    std::cout << elapsed_time.count() << std::endl;
  }

  // equivalent to the second method from above
  // no performace penalty
  {
    auto start = clock::now();
    std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2));
    for (unsigned i = 0; i < 10000; ++i)
    {
      for (unsigned j = 0; j < n1; ++j)
      {
        vec[j].clear();
        vec[j].resize(n2);
      }

      // do stuff
    }
    auto elapsed_time = clock::now() - start;

    std::cout << elapsed_time.count() << std::endl;
  }
}

编辑:我更新了代码以在方法之间进行更公平的比较。 编辑2:稍微清理一下代码,方法2或4是要走的路。

以下是我电脑上上述四种方法的时序:

16327389
15216024
16371469
15279471

关键是您应该尝试不同的方法并分析您的代码。

于 2012-04-13T13:48:57.527 回答
6

选择容器时,我通常使用此图来帮助我:

在此处输入图像描述

来源


除此之外,

就像之前发布的那样,如果这会导致性能问题,请在 for 循环之外声明容器,并在每次迭代开始时将其清除

于 2012-04-13T13:29:25.790 回答
0

为什么不这样:

{
    vector< vector<long long> > vec(n1, vector<long long>(n2));

    for (int i=0; i<bound; i++){

         //about three more for-loops here

         vec.clear();
    }
}

编辑:添加范围大括号;-)

于 2012-04-13T13:28:42.657 回答
0

除了之前的评论:

如果你使用 Robinson 的交换方法,你可以通过异步处理交换来更快。

于 2012-04-13T13:28:57.147 回答
0

好吧,如果您真的很关心性能(并且您事先知道大小n1和大小n2)但不想使用 C 样式数组,std::array那么可能是您的朋友。

编辑:鉴于您的编辑,它似乎std::array不是一个合适的替代品,因为虽然向量大小不会改变每次迭代,但在编译之前它仍然未知。

于 2012-04-13T13:31:00.987 回答
0

由于每次迭代都必须将向量值重置为 0,因此实际上,这个问题归结为“与循环内的计算相比,为向量分配和取消分配内存的成本是便宜还是昂贵”。

假设计算是算法中昂贵的部分,那么您编写它的方式既清晰、简洁,又显示了预期的范围,并且可能与替代方法一样快。

但是,如果您的计算和更新非常快并且向量的分配/释放相对昂贵,您可以使用std::fill在循环的每次迭代结束/开始时将零填充回数组。

当然,唯一确定的方法是使用分析器进行测量。我怀疑您会发现您采用的方法不会显示为任何类型的热点,您应该保留明显的代码。

于 2012-04-13T14:40:32.247 回答
-1

使用向量与数组的开销很小,尤其是当您从向量中获得很多有用的功能时。在内部,向量分配一个数组。所以矢量是要走的路。

于 2012-04-13T13:25:35.560 回答