CODEWITHSUNDEEP
c++vectorinitializationmemset
N_ E
N_ E

Reputation: 61

Efficient method to initialize a really large C++ vector with the same values

I was doing this leetcode problem and I had to initialize a very large 2D DP array of size 2^14 x 14 with all entries set to -1 to solve the problem. However I noticed a big performance difference depending on whether I'm using vector or array for this DP array.

Using vector:

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

gave me a runtime of 251 ms

Meanwhile, using array with memset:

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

only gave me a runtime of 95 ms

Is there a way to initialize this array as efficiently using C++ vector?

I have tried alternatives such as using std:fill, but it doesn't produce any runtime difference.

Upvotes: 2

Views: 114

Answers (1)

Jerry Coffin
Jerry Coffin

Reputation: 489998

Using something like this:

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";
}

I get about the same amount of time to initialize one as the other (but both are in the range of hundreds of microseconds, not anything like multiple milliseconds.

Upvotes: 2

Related Questions