Prev: kmeans
Next: Multiple object tracking
From: Mohamed on 15 Apr 2010 20:11
Hi,

I need to find the indices of some values within a certain vector. I know that I can use 'for loop' with 'find' commands to get them one by one. But I am asking if there is another technique to find them at one time. I need this because the size of the values is about 10^6 and by using 'for loop' the speed of the code goes down.
From: Walter Roberson on 15 Apr 2010 20:19
Mohamed wrote:

> I need to find the indices of some values within a certain vector. I
> know that I can use 'for loop' with 'find' commands to get them one by
> one. But I am asking if there is another technique to find them at one
> time. I need this because the size of the values is about 10^6 and by
> using 'for loop' the speed of the code goes down.

Ummm, ismember perhaps?
From: us on 15 Apr 2010 20:34
"Mohamed " <mas(a)egypt.ca> wrote in message <hq89uo$6s2$1(a)fred.mathworks.com>...
> Hi,
>
> I need to find the indices of some values within a certain vector. I know that I can use 'for loop' with 'find' commands to get them one by one. But I am asking if there is another technique to find them at one time. I need this because the size of the values is about 10^6 and by using 'for loop' the speed of the code goes down.

show CSSM a small example of your input and desired output...

us
From: Mohamed on 15 Apr 2010 21:12
Walter Roberson <roberson(a)hushmail.com> wrote:

> Ummm, ismember perhaps?

Yes I think this command will solve my problem.

Thank you so much.

---------------

"us " <us(a)neurol.unizh.ch> wrote:

> show CSSM a small example of your input and desired output...

Ok so as an example, we have cumulative distribution function F(x). We have vector of x-data and we can calculate the F(x). I need to randomly generate x according to this distribution. As we know, the range of F(x) is from 0 to 1, so I generate uniform distribution from 0 to 1 with rand(1,N). Then I find the x value which corresponds to F(x) equal to this random value.
Since I don't have a mathematical equation for F(x) so I search first for the index of F(x) and since it is monotonic increasing function then I use this index to find the corresponding value of x.

Thank you "us" for your concern.
From: Walter Roberson on 15 Apr 2010 22:18
Mohamed wrote:

> Ok so as an example, we have cumulative distribution function F(x). We
> have vector of x-data and we can calculate the F(x). I need to randomly
> generate x according to this distribution. As we know, the range of F(x)
> is from 0 to 1, so I generate uniform distribution from 0 to 1 with
> rand(1,N). Then I find the x value which corresponds to F(x) equal to
> this random value. Since I don't have a mathematical equation for F(x)
> so I search first for the index of F(x) and since it is monotonic
> increasing function then I use this index to find the corresponding
> value of x.

ismember is not suitable for that application, as floating point numbers
are unlikely to have an _exact_ comparison in the table. Not unless the
table is 2^53 elements long ;-)


I suggest you create an inverse lookup table, linearly indexed, so that
FI(1 + floor(N*r)) gives the lower bound on your search, where N is
(say) 100, and r is your random value. This breaks the long search over
your thousands of values into a constant-time lookup plus a shorter
search. Depending on the shape of your distribution, a different initial
lookup function might be more efficient: ideally you would like your
initial lookup function to break the search table up into roughly equal
pieces [*]. If your function is highly asymptotic then a ln(x) or
ln(1-x) might be effective. The lookup of the lower bound could be
vectorized; the actual search might or might not be efficiently
vectorizable without wasting time.


[*] Well, really, you'd like either -exactly- equal pieces (or equal
within a fairly small number) so that you could vectorize the searches,
or else you'd like the segment search time to be proportional to the
probability of the segment, so as to minimize the _average_ search time.
Remember that there's always binary search (though if the segments to be
searched are short enough, then vectored linear search can outperform
binary search.)
 | 
Pages: 1
Prev: kmeans
Next: Multiple object tracking