CODEWITHSUNDEEP
c++arrays
phoxd
phoxd

Reputation: 1622

Using vector container hangs while using array computes quick for 2D array

I came across an example from leetcode, and looking at solutions I tried to implement it in C++ using vector as follows,

class Solution {
public:
  int minScoreTriangulation(std::vector<int>& A) {
    std::vector<std::vector<int>> memo(A.size(), std::vector<int>(A.size(), 0));
    return tri(A, 0, A.size() - 1, memo);
    }
    
  int tri(std::vector<int>& A, int i, int k, std::vector<std::vector<int>> memo) {
        if( k - i < 2) return 0;
        if( k - i == 2) return A[i] * A[i+1] * A[k];
        if( memo[i][k] != 0) return memo[i][k];
        int min = ((unsigned int) ~0) >> 1; // max positive number
        for(int j = i + 1; j < k; j++) {
          min = std::min(A[i] * A[j] * A[k] + tri(A, i, j, memo) + tri(A, j, k, memo), min);
        }
        memo[i][k] = min;
        return min;
    }
};

Running on small inputs the program works, but it hangs for bigger input,

int main() {
  std::vector<int> v0 = {35,73,90,27,71,80,21,33,33,13,48,12,68,70,80,36,66,3,70,58}; // hangs
  std::vector<int> v1 = {3,7,4,5}; // works fine
  Solution t = Solution();
  std::cout << t.minScoreTriangulation(v0) << std::endl;
  return 0;
}

So I used two dimensional array, and it computed v0 much faster.

class Solution {
public:
  int minScoreTriangulation(std::vector<int>& A) {
    int** memo = new int*[A.size()];
    for(int i=0; i<A.size(); i++) memo[i] = new int[A.size()]{0};
    
    return tri(A, 0, A.size() - 1, memo);
    }
    
  int tri(std::vector<int>& A, int i, int k, int** memo) {
        if( k - i < 2) return 0;
        if( k - i == 2) return A[i] * A[i+1] * A[k];
        if( memo[i][k] != 0) return memo[i][k];
        int min = ((unsigned int) ~0) >> 1; // max positive number
        for(int j = i + 1; j < k; j++) {
          min = std::min(A[i] * A[j] * A[k] + tri(A, i, j, memo) + tri(A, j, k, memo), min);
        }
        memo[i][k] = min;
        return min;
    }
};

Is it possible to make vector run in a reasonable time? Or is it dependent on other factors such as cache?

Upvotes: 1

Views: 51

Answers (1)

PaulMcKenzie
PaulMcKenzie

Reputation: 35455

The issue is that you are passing a std::vector<std::vector<int>> by value instead of by reference:

int tri(std::vector<int>& A, int i, int k, 
        std::vector<std::vector<int>> memo) // <-- Passed by value

This will incur a copy each time memo is passed.

Maybe a very smart optimizing compiler could optimize the copy away, but you cannot rely on this. Instead, make your intentions known:

int tri(std::vector<int>& A, int i, int k, 
        std::vector<std::vector<int>>& memo) // <-- Now passed by reference

Upvotes: 2

Related Questions