mardi 31 octobre 2017

Why is bool [][] more efficient than vector

I am trying to solve a DP problem where I create a 2D array, and fill the 2D array all the way. My function is called multiple times with different test cases. When I use a vector>, I get a time limit exceeded error (takes more than 2 sec for all the test cases). However, when I use bool [][], takes much less time (about 0.33 sec), and I get a pass.

Can someone please help me understand why would vector> be any less efficient than bool [][].

bool findSubsetSum(const vector<uint32_t> &input)
{
    uint32_t sum = 0;

    for (uint32_t i : input)
        sum += i;

    if ((sum % 2) == 1)
        return false;

    sum /= 2;

#if 1
    bool subsum[input.size()+1][sum+1];
    uint32_t m = input.size()+1;
    uint32_t n = sum+1;

    for (uint32_t i = 0; i < m; ++i)
        subsum[i][0] = true;

    for (uint32_t j = 1; j < n; ++j)
        subsum[0][j] = false;

    for (uint32_t i = 1; i < m; ++i) {
        for (uint32_t j = 1; j < n; ++j) {

            if (j < input[i-1])
                subsum[i][j] = subsum[i-1][j];
            else
                subsum[i][j] = subsum[i-1][j] || subsum[i-1][j - input[i-1]];
        }
    }

    return subsum[m-1][n-1];
#else
    vector<vector<bool>> subsum(input.size()+1, vector<bool>(sum+1));

    for (uint32_t i = 0; i < subsum.size(); ++i)
        subsum[i][0] = true;

    for (uint32_t j = 1; j < subsum[0].size(); ++j)
        subsum[0][j] = false;

    for (uint32_t i = 1; i < subsum.size(); ++i) {
        for (uint32_t j = 1; j < subsum[0].size(); ++j) {

            if (j < input[i-1])
                subsum[i][j] = subsum[i-1][j];
            else
                subsum[i][j] = subsum[i-1][j] || subsum[i-1][j - input[i-1]];
        }
    }

    return subsum.back().back();
#endif
}

Thank you, Ahmed.

Aucun commentaire:

Enregistrer un commentaire