Performance in multi-loop applications

3

When searching a bit, I found several Java code to calculate the determinant of an array. I passed one of them to javascript and it looked like this:

function determinant(A, N) {
  var det = 0;
  if (N == 1) {
    det = A[0][0];
  } else if (N == 2) {
    det = A[0][0] * A[1][1] - A[1][0] * A[0][1];
  } else {
    det = 0;
    for (var j1 = 0; j1 < N; j1++) {
      var m = [];
      for (var k = 0; k < (N - 1); k++) {
        m[k] = [];
      }
      for (var i = 1; i < N; i++) {
        var j2 = 0;
        for (var j = 0; j < N; j++) {
          if (j == j1)  continue;
          m[i - 1][j2] = A[i][j];
          j2++;
        }
      }
      det += Math.pow(-1.0, 1.0 + j1 + 1.0) * A[0][j1] * determinant(m, N - 1);
    }
  }
  return det;
}
It's pretty much the same thing. It works and calculates the determinant normally. However, when the array passes 12x12, both on the front end and backend with nodejs, the application takes a long time to calculate the result. When you calculate.

I know the reason for this is the various loops, apart from being a "recursive" function, which runs within itself several times.

However, when testing the Math.js to calculate the determinant, regardless of the array order, either 30x30, it calculates the result in less of 1s. Taking a look at the code for the determinant, I found this:

function _det (matrix, rows, cols) {
    if (rows == 1) {
      return object.clone(matrix[0][0]);
    }else if (rows == 2) {
      return subtract(
          multiply(matrix[0][0], matrix[1][1]),
          multiply(matrix[1][0], matrix[0][1])
      );
    }else{
      var compute_mu = function (matrix) {
        var i, j;
        var mu = new Array(matrix.length);
        var sum = 0;
        for (i = 1; i < matrix.length; i++) {
          sum = add(sum, matrix[i][i]);
        }
        for (i = 0; i < matrix.length; i++) {
          mu[i] = new Array(matrix.length);
          mu[i][i] = unaryMinus(sum);
          for (j = 0; j < i; j++) {
            mu[i][j] = 0;
          }
          for (j = i + 1; j < matrix.length; j++) {
            mu[i][j] = matrix[i][j];
          }
          if (i+1 < matrix.length) {
            sum = subtract(sum, matrix[i + 1][i + 1]);
          }
        }
        return mu;
      };
      var fa = matrix;
      for (var i = 0; i < rows - 1; i++) {
        fa = multiply(compute_mu(fa), matrix);
      }
      if (rows % 2 == 0) {
        return unaryMinus(fa[0][0]);
      } else {
        return fa[0][0];
      }
    }
}

The code is not much different from some other examples I've seen, but how does it get such incredible performance gain?

Is there any specificity of the code itself? Or the use of various functions external to this block? Or even the organization as a whole?

I confess that I was wondering about the performance of this lib, very good by the way. Thanks for any explanation. Thanks in advance.

    
asked by anonymous 16.07.2016 / 13:21

1 answer

0

The main difference is the recursive function, which gives a big kill on performance.

Briefly, math.js is already fully optimized, so it is not worth rewriting its functions, except for study reasons.

    
19.08.2016 / 03:45