Finding collumn with specific values within matrix

TLDR; looking for a value in the sixth row of a 6x2598960 matrix, if values in the first 5 rows are the same as input.

I have a matrix "ind" of 6x2598960 double

Within the matrix every combination of 52 numbers is contained in the first 5 rows.

With ind(1,n)<ind(2,n)<ind(3,n)<ind(4,n)<ind(5,n)

This results in the 2598960 combinations (binomium of newton: 52*51*50*49*48/24)

My question:

Every collumn has a specific unique rational number attached in the sixth row.

Im trying to figure out a fast algorithm to identify value in the sixth row when looking for a specific 5 number input.

The following script works, but: "Elapsed time is 2.124802 seconds."

This feels long to find a single value in a matrix (allthough the matrix has 15M elements).

v1=[1;2;3;5;4];

v2=sort(v1);

for n=1:2598960

if ind(1,n)==v2(1)

if ind(2,n)==v2(2)

if ind(3,n)==v2(3)

if ind(4,n)==v2(4)

if ind(5,n)==v2(5)

index1=ind(6,n);

end

end

end

end

end

end

Anyone any thoughts on how to to increase the speed to find the value in the sixth row?

[James Tursa]

Are the ind values sorted in any way?

Answer 1

[James Tursa]

Is this what you are trying to do?

indt = ind(1:5,:)';
[~,k] = ismember(sort(v1)',indt,'rows');
index1 = ind(6,k)

The first line costs you a lot of time, so this method isn't really of interest unless you can do the indt only once up front and not during any iterative process.

Btw, to speed up your loops you should break out of all the loops after you find the column.

Or, if you really need the most speed possible, a C mex routine would be fairly trivial to write for this.

EDIT

Here is the C-mex routine. I gave it the name find_column.c but you can of course use any other name if you want.

/* File:  find_column.c
 *
 * y = find_column(A,v)
 *
 * Where A = 2D full real double matrix
 *       v = 1D full real double vector
 *       numel(v) = size(A,1)-1
 *
 * y = A(end,c), where v matches A(1:end-1,c) ... first occurrence
 * 
 */
#include "mex.h"
void mexFunction( int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
{
    size_t M, N, i, j;
    double *A, *v;
    
    if( nrhs != 2 ) {
        mexErrMsgTxt("Need exactly two real full double inputs");
    }
    if( !mxIsDouble(prhs[0]) || mxIsComplex(prhs[0]) || mxIsSparse(prhs[0]) ||
        mxGetNumberOfDimensions(prhs[0]) != 2 ) {
        mexErrMsgTxt("1st input must be 2D real full matrix");
    }
    if( !mxIsDouble(prhs[1]) || mxIsComplex(prhs[1]) || mxIsSparse(prhs[1]) ||
        mxGetNumberOfDimensions(prhs[1]) != 2 ||
        (mxGetM(prhs[1]) != 1 && mxGetN(prhs[1]) != 1) ) {
        mexErrMsgTxt("2nd input must be 1D real full vector");
    }
    M = mxGetM(prhs[0]);
    N = mxGetN(prhs[0]);
    if( mxGetNumberOfElements(prhs[1]) != M-1 ) {
        mexErrMsgTxt("numel(2nd input) must be equal to size(1st input,1)-1");
    }
    A = (double *) mxGetData(prhs[0]);
    v = (double *) mxGetData(prhs[1]);
    for( j=0; j<N; j++ ) {
        for( i=0; i<M; i++ ) {
            if( i == M-1 ) {
                plhs[0] = mxCreateDoubleScalar(A[i]);
                return;
            }
            if( A[i] != v[i] ) break;
        }
        A += M;
    }
    plhs[0] = mxCreateDoubleMatrix(0,0,mxREAL);
}

You mex it as follows (you need to have a C compiler installed):

mex find_column.c

You would call it as follows:

index1 = find_column(ind,sort(v1));

The mex routine just does a linear search. If the ind values were sorted in some type of pattern then the search could be improved (e.g., binary search).

[Remco de Vries]

Like wow... Im a third year mathematics student and first year matlab user. Ive got some experience with writing scripts in powershell (sysadmin) and am usually able to figure out HOW to code something. Just usually very uneffective and slow code :P.

Ive asked this community a question twice (first last week, second now) and the answers im getting are so fast and so... well just wow.

For your first piece of code:

Before your input: Elapsed time is 2.124802 seconds.

Now: Elapsed time is 0.281233 seconds.

Ive never worked with C/C++ before. Is this recommended for being more effective/efficient in Matlab, or just in general recommended for future coding endeavours? Ive got my master thesis coming up next year, so there will most likely be a lot more coding coming up. I will use and implement your mex code, it will be my first time using it. Thank you so much!

[Remco de Vries]

Like wow.

So I installed visual studio (in hindsight wasnt necessary).

Installed addon. Used your code and your instructions. Result as follows:

>> mex find_column.c

Building with 'MinGW64 Compiler (C)'.

MEX completed successfully.

>> tic

index1 = find_column(ind,sort(v1));

toc

Elapsed time is 0.005202 seconds.

This is so cool... Thank you so much. Im learning a lot from all of this, and Im also getting really enthousiastic about coding :D.

Edit; Im so impressed by the amount of code you (a random stranger on the internet) wrote for me, and I showed my gf whose working at the other side of the table (#coronaquarantine) . Her response; "Well these kind of things make me think positive about the future."

[James Tursa]

Thank you for your kind words. There are many people on this forum (and other forums) that volunteer their time and expertise to help others, and quite frankly resonponses like yours are one of the main reasons we do it. We enjoy teaching others who want to learn.

Regarding learning C/C++ for future coding, I would say that even if you didn't use it much for mex programming (which is admittedly an advanced MATLAB topic) it is a very good general skill to have. In particular, there is a lot of existing free C/C++ code out there you can use. If you know how to read and interpret it so much the better for you. Depending on your vocation, other popular languages that might be of interest to you are Python and Java.