MATLAB: Quick search in two vectors

search

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.

Best Answer

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.
Related Question