quick search in two vectors
2 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
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 comentarios
Respuesta aceptada
Jan
el 16 de Mayo de 2012
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 comentarios
Más respuestas (2)
per isakson
el 16 de Mayo de 2012
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
Sean de Wolski
el 16 de Mayo de 2012
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.
Ver también
Categorías
Más información sobre Characters and Strings en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!