quick search in two vectors

Question

Yingke 2012-5-16

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/38558-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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Jan 2012-5-16

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/38558-quick-search-in-two-vectors#answer_48074

在 MATLAB Online 中打开

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.

3 个评论
显示 1更早的评论隐藏 1更早的评论

Jan 2012-5-17

Code changed to UINT32 type.

Yingke 2012-5-17

Thanks again!

请先登录，再进行评论。

Answer 2

per isakson 2012-5-16

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/38558-quick-search-in-two-vectors#answer_48079

在 MATLAB Online 中打开

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

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Yingke 2012-5-17

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 2012-5-16

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/38558-quick-search-in-two-vectors#answer_48037

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.