How to find vector elements between two values, efficiently

454 次查看（过去 30 天）
Gonzalo
Gonzalo 2011-5-31
回答： Martin Muehlegger 2019-12-17
I need to find all elements that fall between 2 values (L,U) in a matrix (A) with 2.8 million rows. I'm currently doing this:
[ind,~] = find(A(:,1) >= L & A(:,1) < U);
Variables U and L are updated 41 times inside a loop. This single line of code is slowing down the program by 20 minutes! Any ideas how can I speed this up?
  3 个评论
显示 1更早的评论
Pratik Anandpara
Pratik Anandpara 2016-12-10
how to find its position from matrix,index of that element which we call...@chirag

请先登录，再进行评论。

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

采纳的回答

Matt Fig
Matt Fig 2011-5-31
Do you need the actual indices or the values? If you only need the values, then it would probably be faster to do:
A(A(:,1) >= L & A(:,1) < U)
  3 个评论
显示 1更早的评论
Matt Fig
Matt Fig 2011-5-31
Then you may be stuck unless there are other efficiencies you can make. One alternative that I can think of to get the indices would be to use a dummy variable. I am not sure if this would be faster or not. Make IDX before hand, if you are looping....
IDX = uint32(1:size(A,1));
ind = IDX(A(:,1) >= L & A(:,1) < U);
Gonzalo
Gonzalo 2011-5-31
This method reduces the time by 13,7%, which is good. Thanks.

请先登录，再进行评论。

更多回答（6 个）

James Tursa
James Tursa 2011-6-1
You can try a mex approach. The following file does the exact calculation shown above. If you need to modify it for different columns etc let me know. To mex it, simply put the file someplace on your path, make that directory your current directory, then type
mex findrange.c
The mex program does the calculations fast at the expense of memory. It always allocates enough to hold the indexes of the entire column and then just sets the return size to the amount that it found without reallocating & copying. But from the looks of things this may be a relatively minor temporary memory waste.
/* File: findrange.c */
/* IND = findrange(A,L,U) returns the same result as the following: */
/* IND = find(A(:,1)>=L & A(:,1)<U) */
/* Programmer: James Tursa */
#include "mex.h"
void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
{
mwSize i, k, m;
double L, U;
double *pr, *ind;
if( nlhs > 1 ) {
mexErrMsgTxt("Too many outputs.");
}
if( nrhs != 3 ) {
mexErrMsgTxt("Need exactly 3 inputs.");
}
if( !mxIsDouble(prhs[0]) || mxIsSparse(prhs[0]) || mxGetNumberOfDimensions(prhs[0]) > 2 ) {
mexErrMsgTxt("First argument must be full double 2D matrix.");
}
if( !mxIsNumeric(prhs[1]) || mxGetNumberOfElements(prhs[1]) != 1 ) {
mexErrMsgTxt("2nd argument must be a scalar.");
}
if( !mxIsNumeric(prhs[2]) || mxGetNumberOfElements(prhs[2]) != 1 ) {
mexErrMsgTxt("3rd argument must be a scalar.");
}
L = mxGetScalar(prhs[1]);
U = mxGetScalar(prhs[2]);
pr = mxGetPr(prhs[0]);
m = mxGetM(prhs[0]);
plhs[0] = mxCreateDoubleMatrix(m,1,mxREAL);
ind = mxGetPr(plhs[0]);
for( i=0; i<m; i++ ) {
if( *pr >= L && *pr < U ) {
*ind++ = i+1;
}
pr++;
}
mxSetM(plhs[0],ind-mxGetPr(plhs[0]));
}
  2 个评论
Jan
Jan 2011-6-1
Instead of the DOUBLE output, an UINT32 vector would use the half memory:
uint32_T *ind, i, m;
plhs[0] = mxCreateNumericMatrix(m,1,mxUINT32_CLASS, mxREAL);
ind = (uint32_T *) mxGetData(plhs[0]);
With "for (i = 1; i <= m; i++), ... *ind++=i;" you can save some milliseconds.
James Tursa
James Tursa 2011-6-2
DOUBLE vs UINT32 memory savings:
True. Whether this is an actual savings overall depends on what is done with the result downstream (which OP doesn't show). If operations are done with it that turn it into a double then the memory savings will turn into a memory waste instead.
Changing the loop index to start from 1 instead of 0:
Yeah, I saw that right after I posted it (I habitually start my loops from 0 in C), but then I thought ... "Why don't I just let Jan find it ..."

请先登录，再进行评论。

chirag
chirag 2013-5-18
just type this
op=A(A>l & A<U);
Walter Roberson
Walter Roberson 2011-5-31
How "dense" are the values? It might be faster to use
[ind1, ~] = find(A(:,1)>=L);
ind = ind1(A(ind1,:)<U);
Or reversing the order of the test, putting the test less likely to succeed first.
This could be cost-effective if relatively few matches are found, reducing the number of ind1 subscripts that need to be looked up in the second step.
Angus
Angus 2011-6-22
The fastest way I can think of is the following:
data = randn(3000000,3);
inds = not(abs(sign(sign(L - data) + sign(U - data))));
this will give you a matrix of 1s and 0s indicating the indices where the values are between your two bounds (L, U); note not [L, U].
This should be lightening fast, for 3 columns and 3 million rows it computes in a fraction of a second.
  3 个评论
显示 1更早的评论
Angus
Angus 2011-6-22
Matt. You're right it shouldn't be and isn't. It appeared and I believe I misread that this solution only lowered the execution time by 13.7% on a 20 minute execution time for merely the find statement. The example I gave above with 3 million rows and on 3 columns runs in sub 1 sec. Your answer definitely makes more sense.
Erin Langenstein
Erin Langenstein 2017-8-11
Hi, question: if I were to use inds = not(abs(sign(sign(L - Data) + sign(U - Data)))) and wanted to loop L and U through this with L = 0:1:170 and U = 1:1:171 but I want to get out a Different matrix for every U and L how would I do that? I tried two for loops but it just took forever and only used U = 170 and L= 171 thus only one matrix in the end. Thanks so much, Erin.

请先登录，再进行评论。

Martin Muehlegger
Martin Muehlegger 2019-12-10
编辑：Martin Muehlegger 2019-12-10
I have a datetime array pretty long like 121000 rows
A_time =
'07-Mar-2019 07:07:42'
'07-Mar-2019 07:07:52'
'07-Mar-2019 07:08:02'
'07-Mar-2019 07:08:12'
'07-Mar-2019 07:08:22',...
and a smaller datetime matrix A_bg_date
A_bg_date =
'07-Mar-2019 17:16:48' '07-Mar-2019 17:18:20'
'08-Mar-2019 01:36:47' '08-Mar-2019 01:38:30'
'08-Mar-2019 05:46:47' '08-Mar-2019 05:48:24'
'08-Mar-2019 09:56:48' '08-Mar-2019 09:58:25'
'08-Mar-2019 14:06:48' '08-Mar-2019 14:08:25'
I would like to find the indices of A_time between A_bg_date(j,1) and A_bg_date(j, 2). (filter out certain timestemps)
I tried something like this:
A_time = datetime(A_MUP_res.stick_Data.stick_time,'ConvertFrom','datenum'); % timestemp
bg_times = zeros(1, length(A_time)); % create empty array to store
% j = 1;
j = 1:length(A_bg_date);
for i = 1:length(A_time)
% j = 1:length(A_bg_date);
bg_times = isbetween(A_time(i), A_bg_date(j,1), A_bg_date(j,4));
bg_times = bg_times(i);
% j = j+1;
% bg_times(i) = isbetween(A_time(i), A_bg_date(2,1), A_bg_date(2,4));
end
I have either a index problem or i just get the indices of A_bg_date(1,1) to A_bg_date(1, 2) and it doesn't iterate through my A_bg_date matrix?
Martin Muehlegger
Martin Muehlegger 2019-12-17
Found a solution....
made a index array for my main set (BG) and looped through the indices of my main set (i) and the indices of my subset (BG_A) (j) with a nested loop setting BG(i,1) = j puts the indices (length of subset) in the first row of your main matrix so that you can apply any kind of function to those timestemps
idx = 1:length(A_MUP_res.stick_Data.stick_duty_cps); % create indexrow filled later
% idx2 = zeros(length(A_MUP_res.stick_Data.stick_duty_cps),1);
idx = idx';
BG = horzcat(idx, A_MUP_res.stick_Data.stick_duty_cps);
% j = 1:length(BG_A);
for i = 1:length(A_MUP_res.stick_Data.stick_duty_cps)
for j = 1:length(BG_A)
if BG(i,1) >= BG_A(j,1) && BG(i,1) <= BG_A(j,2)
BG(i,1) = j;
end
end
end
BG;
clear BG idx i j % clean workspace (OPTIONAL)

类别

在 Help Center 和 File Exchange 中查找有关 Matrix Indexing 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by