用相同的值初始化一个非常大的C++向量的有效方法

Question

我正在做这个leetcode问题，我必须初始化一个非常大的2D DP数组，大小为2^14 x 14，所有条目设置为-1来解决这个问题。然而，我注意到一个很大的性能差异，具体取决于我对此 DP 数组使用的是向量还是数组。

使用矢量：

vector<vector<int>> dp(1 << nums.size(), vector<int>(nums.size(), -1));

给了我 251 毫秒的运行时间

同时，使用带有 memset 的数组：

int dp[1 << 14][14];
memset(dp, -1, sizeof(dp));

只给了我 95 毫秒的运行时间

有没有办法使用 C++ 向量高效地初始化该数组？

我尝试过其他替代方案，例如使用 std:fill，但它不会产生任何运行时差异。

Answer 1

使用这样的东西：

template <class T>
class matrix2d {
    std::vector<T> data;
    std::size_t cols;
    std::size_t rows;
public:
    matrix2d(std::size_t y, std::size_t x, T init = T()) : cols(x), rows(y), data(x*y, init) {}

    T &operator()(std::size_t y, std::size_t x) { 
        assert(x<=cols);
        assert(y<=rows);
        return data[y*cols+x];
    }
    T operator()(std::size_t y, std::size_t x) const {
        assert(x<=cols);
        assert(y<=rows);
        return data[y*cols+x];
    }

    friend std::ostream &operator<<(std::ostream &os, matrix2d const &m) {
        for (std::size_t y=0; y<m.rows; y++) {
            for (std::size_t x = 0; x<m.cols; x++) {
                os << m(y,x) << "\t";
            }
            os << "\n";
        }
        return os;
    }
};


int main() { 
  using namespace std::chrono;
  
  auto start = steady_clock::now();
  matrix2d m(1<<14, 14, -1);
  auto stop = steady_clock::now();

  uint64_t total = 0;

  for (int i=0; i<(1<<14); i++) {
    for (int j=0; j<14; j++) {
        total+=m(i,j);
    }
  }

  std::cout << "Total: " << total << "\n";
  std::cout << duration_cast<microseconds>(stop-start).count() << "us\n";

    auto start2 = steady_clock::now();   
    int dp[1 << 14][14];
    memset(dp, -1, sizeof(dp));
    auto stop2 = steady_clock::now();
    std::cout << duration_cast<microseconds>(stop2-start2).count() << "us\n";
}

我初始化一个和另一个的时间大约相同（但两者都在数百微秒的范围内，而不是多毫秒。