quick search in two vectors

There are 2 vectors with the same length va and vb ; We want to find out the index i where va(i) = m and vb(i) = n. Currently, we have 2 possible solutions:

1) index = find(va == m & vb == n);

2) mask = va == m; local_mask = vb(mask) == n; %we only need to look at part of vb here. msk = find(msk); index = msk(local_mask);

We think (after testing) that 2) is faster than 1).

Since we are intensively update va and vb, and make query every time, 2) is not good enough.

The length of va and vb is more than 1 million. They are not sorted. m and n are not constant.

So, is there any better solution? Thank you very much.

PS。construct sparse matrix or a hash table is too expensive for us.

Answer 1

[Jan]

A C-Mex does not have to create the large intermediate arrays for "tmp1 = va==m", "tmp2 = vb==n" and "tmp1 & tmp2". The algorithm is much easier, if there is an upper limit of the number of outputs:

#include "mex.h"
void mexFunction(int nlhs, mxArray *plhs[], 
                 int nrhs, const mxArray *prhs[])
{
  uint32_T *va, *vb, m, n, *out;
  mwSize i, j, len;
  const mwSize MaxOutLen = 1000;
  mxArray* out_M;
  mwSize dims[2];

    // Read inputs:
    va  =  (uint32_T *) mxGetData(prhs[0]);
    m   = *(uint32_T *) mxGetData(prhs[1]);
    vb  =  (uint32_T *) mxGetData(prhs[2]);
    n   = *(uint32_T *) mxGetData(prhs[3]);
    len = mxGetNumberOfElements(prhs[0]);

    // Create output:
    dims[0] = 1;
    dims[1] = MaxOutLen;
    plhs[0] = mxCreateNumericArray(2, dims, mxUINT32_CLASS, mxREAL);
    out     = (uint32_T) mxGetData(plhs[0]);

    // Search for matching elements:
    j = 0;
    for (i = 0; i < len; i++) {
      if (va[i] == m && vb[i] == n) {
        out[j++] = i + 1;
        if (j >= MaxOutLen) {
          mexErrMsgTxt("*** MaxOutLen exceeded.");
        }
      }
    }

    // Crop unneeded elements, re-allocation 
    mxSetN(plhs[0], j);

    return;
  }

[EDITED, input type UINT32]

va = round(rand(1, 1e6) * 1000);
vb = round(rand(1, 1e6) * 1000);
tic
out1 = find(va == 3 & vb == 3);
toc
tic
out2 = myMexFcn(va, 3, vb, 3);
toc

 Elapsed time is 0.012186 seconds.
 Elapsed time is 0.004881 seconds.

[Yingke]

YES！ It helps a lot! Thank you.

I am not familiar with MEX. Now it is time to learn it.

Thanks again!

By the way, if the input data type is UINT32, I shall change : 'double *va' and 'mxCreateDoubleMatrix', Right?

[Jan]

Code changed to UINT32 type.

[Yingke]

Thanks again!

Answer 2

[per isakson]

strfind is a bit faster than find with whole numbers (floating integers, flints). The difference used to be larger. With R2012a 64bit:

    >> n= randi( 1e5, [ 1, 1e6 ] );
    tic, ix = find( n==17 ); toc
    tic, ixsf = strfind( n, 17 ); toc
    Elapsed time is 0.004021 seconds.
    Elapsed time is 0.001884 seconds.

    >> ix==ixsf
    ans =
         1     1     1     1     1     1     1     1     1     1     1     1

[Yingke]

I am using 2011b.

n= randi( 1e5, [ 1, 1e6 ] );

tic, ix = find( n==17 ); toc

tic, ixsf = strfind( n, 17 ); toc

Elapsed time is 0.006589 seconds.

Elapsed time is 0.004662 seconds.

strfind is only a little faster in this case. In my program it works even worse. If there is any other solution I will try 2012a. Thank you!!

Answer 3

[Sean de Wolski]

You might want to look at ismember() with the 'rows' flag. Keep column vectors vb, va together in one matrix as v. I don't know if this will be faster or not.

[Yingke]

Thank you very much for your reply.

Unfortunately, ismember is slower than solution 1).

Anyway, thank you all the same.