C ++：使用向量/数组优化速度？ [英] C++: Optimizing speed with vector/array?

问题描述

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

I have a nested for-loop structure and right now I am re-declaring the vector at the start of each iteration:

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] + =一些值的形式。但我担心大n1或大n2的速度很慢。我不知道向量/数组/等的底层架构，所以我不知道什么最快的方式是处理这种情况。我应该使用数组吗？我应该清除不同？我应该完全不同地处理逻辑？

This allows me to "start fresh" each iteration, which works great because my internal operations are largely in the form of vec[a][b] += some value. But I worry that it's slow for large n1 or large n2. I don't know the underlying architecture of vectors/arrays/etc so I am not sure what the fastest way is to handle this situation. Should I use an array instead? Should I clear it differently? Should I handle the logic differently altogether?

编辑：向量的大小技术上不会改变每次迭代（但它可能会根据函数参数改变）。我只是试图清除它/ etc所以程序是尽可能快的人类可能在所有其他情况下。

The vector's size technically does not change each iteration (but it may change based on function parameters). I'm simply trying to clear it/etc so the program is as fast as humanly possible given all other circumstances.

编辑：

我的不同方法的结果：

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

推荐答案

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

Here is some code that tests a few different methods.

#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是要走的路。

Edit: I've updated the code to make a fairer comparison between the methods. Edit 2: Cleaned up the code a bit, methods 2 or 4 are the way to go.

16327389
15216024
16371469
15279471

关键是你应该尝试不同的方法和

The point is that you should try out different methods and profile your code.

这篇关于C ++：使用向量/数组优化速度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！