Help converting (remaining) MATLAB code to MEX? Removing NANs from matrix, and a sortrows equivalent?

Hi all,

I have a code which merges overlapping intervals that I am transcribing into Mex (for speed purposes).

Intervals are a 2 column matrix, with intervals(:,1) being start times, and intervals(:,2) end times.

The code sorts the intervals, then loops through them, and checks if they overlap with the previous one. It replaces the edges of overlapping intervals with NANs. After the code completes, NANs would then be removed from the matrices, keeping non-overlapping intervals.

Here is the MATLAB code:

function output=mergeIntervals(intervals)

intervals = sortrows(intervals); % This line is still missing from MEX code
for i = 2:size(intervals,1)
    if intervals(i,1) <= intervals(i-1,2)
        if intervals(i,2) < intervals(i-1,2)
            intervals(i,2) = intervals(i-1,2);
        end
        intervals(i,1) = nan;
        intervals(i-1,2) = nan;
    end
end
output = reshape(intervals(~isnan(intervals(:))),[],2); % This line is still missing from MEX code

And the equivalent MEX code

// Start code
#include <mex.h>
#include <math.h>

void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
{
    // Declare variables
    double *intervals;
    int i, m;

      // Allocate values
      m = mxGetM(prhs[0]); // Number of rows
      plhs[0] = mxCreateNumericMatrix(m, 2, mxDOUBLE_CLASS, mxREAL);
      intervals = mxGetPr(plhs[0]);
      intervals = mxGetPr(prhs[0]);

      // The algorithm
      for (i = 1; i < m; ++i)
      {
          if (intervals[i] <= intervals[i - 1 + m])
          {
              if (intervals[i + m] < intervals[i - 1 + m])
              {
                  intervals[i + m] = intervals[i - 1 + m];
              }
              intervals[i] = NAN;
              intervals[i - 1 + m] = NAN;
          }
      }
  }

And here is the equivalent MATLAB code:

Now the idea is to remove NANs from the final matrix.

In Matlab notation, the line would be:

For large matrices, if I were to combine MATLAB sorting and nan removal with the MEX code, the MEX code is around ~20 to 30 times faster...

Is there a fast way to sort the rows within MEX code? What about removing NANs? Doing either one of them in MEX should make the code substantially faster...

Thanks

[Jan]

What is "p1"? The same as "intervals"?

[poultryNews]

Indeed. My bad, I was editing the code and forgot to change it back. The original question has been fixed now. As an FYI for the code, I ended up solving it by running a for loop through all the elements of the matrix and keeping the ones I wanted. Not sure if this is the best way to do it in MEX, but it's around twice as fast as the isnan code in MATLAB. I'm still sorting the rows in Matlab as I figured sortrows is a native C code which is probably fairly well optimized.

[Jan]

By the way: You explained, what the algorithm does. But maybe there is a faster method, so better describe, what you want to achieve. Do I understand correctly:

You have a [Nx2] matrix, which contains interval and the value of the first element in each row is smaller (or smaller equal) than the element in the second column? Do the inputs contain NaN values? No you want to "join" all interval, which overlap. The output is a [M x 2] matrix without overlapping intervals.

How large are your inputs? If you call the function 1 million tiems with a 10x2 matrix the fastest solution will differ from a version handling 1e6 x 2 inputs.

[poultryNews]

Hi Jan,

Yes, you got it right. The inputs are time series intervals such as:

[0.5 1.4;
 1.2 2.7;
 2.5 3.1;
 4.2 7.0;
 7.3 9.0;
 8.0 10.5;
 9.3 9.8];

The idea is to combine all intervals which overlap into a single one. In this case the desired output would be:

[0.5 3.1;
 4.2 7.0;
 7.3 10.5];

The length of the input intervals is generally on the order of 10,000 x 2 to 100,000 x 2, and this algorithm runs on the order of a few thousands times in my routine code. The current implementation runs in O(n) (excluding the sorting bit). If you have any ideas to speed up the code, I'd be more than happy to hear them!

[Bruno Luong]

There are few other algorithms on FEX, including mine.

Not sure how it compares to yours, but might be you should benchmark them before select one before mex conversion.

[Bruno Luong]

[0.5 3.1;
 4.2 7.0;
 7.3 10.5];

I think the interval [0.5,3.1] is incorrect, none of the original intervals do cover (2,2.5)

[poultryNews]

Good catch. Fixed the example. Will try out your algorithm and see how it compares. Thanks for the suggestion!

[poultryNews]

After checking your code out, I realized that this is exactly what I had done in my MEX code to go around the NAN issue.

[Bruno Luong]

If you don't want to bother with sorting, code just the loop with C-mex and let MATLAB takes care of the rest, including sorting (MATLAB sorting is very good).

I usually use qsort when I do MEX programming with MSVC.

Otherwise you can just find the algorithm on the internet and code it yourself, it's not difficult, and I have done it in this FEX, but usually hard to beat factory MATLAB/MS sorting.