5
\$\begingroup\$

I found this problem from leetcode.com. We are asked to find the longest increasing path in a matrix. I finally came up with a recursion to achieve this but I found that when I increase the rows and columns to a large size then my program takes a long time to run.

I am wondering if there is any way I can optimize my code for speed, or perhaps if there is a better approach I can consider. I know that some have used dynamic programming and depth first search to achieve good speeds but to be honest I haven't really gotten there yet in my programming level.

#include <algorithm>
#include <cmath>
#include <vector>
#include <iostream>
#include <random>

using namespace std;


#define MATRIX_SIZE 1000

void printPath() {

}

int check(int i, int j, vector<vector<int> > matrix, vector<vector<int> > length) {
    if (length[i][j] == -1) {
        int currentValue = matrix[i][j];

        int len = 0;
        if ((i > 0) && (matrix[i-1][j] > currentValue)) { // check up
            len = max(len, check(i-1, j, matrix, length));
        }
        if ((i + 1 < matrix.size()) && (matrix[i+1][j] > currentValue)) { // check left
            len = max(len, check(i+1, j, matrix, length));
        }
        if ((j > 0) && (matrix[i][j-1] > currentValue)) { // check down
            len = max(len, check(i, j-1, matrix, length));
        }
        if ((j+1 < matrix[i].size()) && (matrix[i][j+1] > currentValue)) { // check right
            len = max(len, check(i, j+1, matrix, length));
        }
        length[i][j] = len + 1; // Include current cell
    }
    return length[i][j];
}

int longestPath(vector<vector<int> > matrix) {
    int n = matrix[0].size();
    int m = matrix.size();
    vector<vector<int> > length(m, vector<int>(n,-1));

    int len = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            len = max(len, check(i, j, matrix, length));
        }
    }
    return len;
}


int main() {
    // Specify the number of rows and columns of the matrix
    int n = MATRIX_SIZE;
    int m = MATRIX_SIZE;

    // Declare random number generator
    mt19937 gen(10);
    uniform_int_distribution<> dis(1, 1000000);

    // Fill matrix
    vector<vector<int> > matrix;
    for(int i = 0; i < m; i++) {
            vector<int> row;
        for(int j = 0; j < n; j++) {
            row.push_back(0);
        }
        matrix.push_back(row);
    }

    // Apply random number generator to create matrix
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            matrix[i][j] = dis(gen);
        }
    }

    // Print matrix to see contents
//  for(int i = 0; i < m; i++) {
//      for(int j = 0; j < n; j++) {
//          cout << matrix[i][j] << " ";
//      }
//      cout << endl;
//  }
//  cout << endl;

    int result = longestPath(matrix);
    cout << result << endl;





}
\$\endgroup\$
  • \$\begingroup\$ "a long time to compile" Do you mean it takes a long time to run? I don't think the army sizes would change compilation times? \$\endgroup\$ – Cris Luengo Apr 26 '18 at 6:58
  • 1
    \$\begingroup\$ I think you should consider starting your search at each local minimum. There is no point in finding the longest path starting at any other point, because it won't be maximal by definition. Optimal would be to process these local minima in order of lowest value first. That way you'll do the least work. (Sorry, this is sort of a mini-review, I think it's too short to post as an answer, but I don't have anything else to add.) \$\endgroup\$ – Cris Luengo Apr 26 '18 at 7:03
7
\$\begingroup\$

Don't do using namespace std;.


void printPath() {

}

This empty function does not do anything, so better remove it to make the code cleaner.


// Print matrix to see contents
//  for(int i = 0; i < m; i++) {
//      for(int j = 0; j < n; j++) {
//          cout << matrix[i][j] << " ";
//      }
//      cout << endl;
//  }
//  cout << endl;

Commented code clutters the code and can confuse the reader. "Is it still needed? Then why is it commented out? If not, why is it still there?". Apparently it is not used anymore, and it also tells the reader nothing about the code, so better delete it.


// Specify the number of rows and columns of the matrix
int n = MATRIX_SIZE;
int m = MATRIX_SIZE;

The comment here should not be needed, because the code explains itself. Maybe it would be even more explicit if you named the variables rows and columns. If n and m do not change, and you have MATRIX_SIZE defined anyways, you could just use MATRIX_SIZE instead of the variables.


// Declare random number generator
mt19937 gen(10);
uniform_int_distribution<> dis(1, 1000000);

A more explicit variable name would make this comment obsolete. Less comments means less to read and makes the code easier to understand. Comments should tell the reader why the code does something, but the code should explain what it does itself. rng would be short and is a well known acronym for random number generator.

\$\endgroup\$
  • \$\begingroup\$ Thank you, those are good points. But I am still looking for something that will speed up the code. \$\endgroup\$ – Snarfy Apr 26 '18 at 15:31
  • \$\begingroup\$ When you try to access a number in a vector of vectors, you need an extra indirection. The data is also scattered all over the memory and the cpu has to jump to all these spots in the memory. Better just use one vector to hold all the numbers if you care about speed. Or use a linear algebra library. \$\endgroup\$ – R zu Apr 27 '18 at 17:42
  • \$\begingroup\$ Hmm.. Should reserve space before doing tons of push_back. Otherwise, the program often reallocates memory for the vectors during the loop. And allocation of memory is really really slow. Maybe if a z order curve representation of the matrix would make this faster. But I am not sure. \$\endgroup\$ – R zu Apr 27 '18 at 17:51
4
\$\begingroup\$

longest_path and check both take their vector parameters by value, which means the compiler will make copies of the vectors when calling the functions. This consume a lot of execution time since they are large two-dimensional matrices. Also, your caching of the calculated value for length will be lost since it is only stored in the local copy.

The vector parameters should be passed in by reference (const for matrix since it is not modified):

int check(int i, int j, const vector<vector<int> > &matrix, vector<vector<int> > &length)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.