Calculate max(diff(A)) fast and memory efficient.

Say I have a giant array A of 2 gb and I want to make something like an analog edge-detection:

[max, index] = max(diff(A))

This would require at least 4 gb of ram. There is however a more memory efficient way:

A = randi(1e5, 1,5e8);

tic;
[m, index] = max(A);
toc;
disp(index);

tic;
m = 0;
index = -1;
for i = 1:length(A)
    if A(i) > m
        m = A(i);
        index = i;
    end
end
toc;

disp(index);

which outputs:

Elapsed time is 36.869092 seconds.
       37662

Elapsed time is 45.502829 seconds.
       37662

In any programming language with a decent jit the lower part would be as fast or faster than the upper. Is there a fast way to implement this in matlab?

[Matt J]

Your example is a bit confusing because it excludes the diff operations. When run as shown, the max(A) approach gives

 Elapsed time is 0.583208 seconds.

Also, the diff operation is presumably what is responsible for the extra 2GB RAM usage.

Answer 1

[James Tursa]

You could resort to a mex routine. E.g., here is bare bones code (no argument checking) for double input:

#include "mex.h"
void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
{
  double d, f;
  double *pr, *qr;
  mwSize i, n, x;

  n = mxGetNumberOfElements(prhs[0]);
  qr = mxGetPr(prhs[0]);
  pr = qr + 1;
  x = 1;
  d = *pr - *qr;
  for( i=2; i<n; i++ ) {
    f = *++pr - *++qr;
    if( f > d ) {
      d = f;
      x = i;
    }
  }
  plhs[0] = mxCreateDoubleScalar(d);
  if( nlhs == 2 ) {
      plhs[1] = mxCreateDoubleScalar(x);
  }
}

This will avoid the intermediate data copy. To compile it, place the code inside a file called maxdiff.c in your working directory, make that working directory your current directory, then type this at the MATLAB prompt:

mex maxdiff.c

Answer 2

[Sean de Wolski]

You could do a hybrid approach and loop from 1:4 (or 10 or whatever), calculate max(diff(x(of that range of x)) and then keep the biggest one at the end.

Answer 3

[Matthias]

Just as a comparison: I implemented the for loop way in Julia:

elapsed time: 0.016319368 seconds