Prev: Refresh Simulink library browser
Next: Using Apache CXF in from MATLAB
From: Paul on 28 Jul 2010 17:27
Sorry, some corrections:
I search something like 150,000 Rprimes. Each gets searched something like 12 times, for a total number of searches of 1,800,000.

F_i=log(sbesselk(i,exp(R_i))). This allows for nice compression of the function. As the function is close to an exponential, it's log is nearly linear over a range of input values.
From: Bruno Luong on 28 Jul 2010 17:50
HISTC is the builtin function for search in sorted list. But why not using a fast search and interpolation, for example the mex file posted here:

http://www.mathworks.com/matlabcentral/newsreader/view_thread/258413

In any case try to vectorize the code rather of calling individual searching within for-loop.

Bruno
From: Matt Fig on 28 Jul 2010 18:32
I would suggest that rather than calling your search engine in a FOR loop, you can vectorize it something like this example:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
x = sort(rand(3000,1)*5); % The data points, x-vals of function y(x).
xf = [2;3;4]; % Want to find index bracket to all elements of this.

% Algorithm
x1 = ones(size(xf));
x2 = length(x)*x1;

while any((x2-x1)>1)
xM = x1 + floor((x2-x1)/2);
cond = xf>x(xM);
x1(cond) = xM(cond);
x2(~cond) = xM(~cond);
end

(x(x1)<=xf)&(xf<=x(x2)) % Check that we have bracketed the search data
% Now the interpolations step is easy....
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Yet another suggestion would be that if you are going to call the search in a FOR loop, you first sort the search values (xf) then use the index found for xf(ii) as the starting point in the search for the index for xf(ii+1). This might even be faster than vectorization if the data is spaced well. Of course a MEX-file is probably faster anyway....
From: Paul on 28 Jul 2010 22:03
"Matt Fig" <spamanon(a)yahoo.com> wrote in message <i2qb5m$gok$1(a)fred.mathworks.com>...
> I would suggest that rather than calling your search engine in a FOR loop, you can vectorize it something like this example:
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> x = sort(rand(3000,1)*5); % The data points, x-vals of function y(x).
> xf = [2;3;4]; % Want to find index bracket to all elements of this.
>
> % Algorithm
> x1 = ones(size(xf));
> x2 = length(x)*x1;
>
> while any((x2-x1)>1)
> xM = x1 + floor((x2-x1)/2);
> cond = xf>x(xM);
> x1(cond) = xM(cond);
> x2(~cond) = xM(~cond);
> end
>
> (x(x1)<=xf)&(xf<=x(x2)) % Check that we have bracketed the search data
> % Now the interpolations step is easy....
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
>
> Yet another suggestion would be that if you are going to call the search in a FOR loop, you first sort the search values (xf) then use the index found for xf(ii) as the starting point in the search for the index for xf(ii+1). This might even be faster than vectorization if the data is spaced well. Of course a MEX-file is probably faster anyway....

@Matt - That code you offered is quite spectacular and nicely parallel. The algorithm I have above, even running only one value at a time in a for loop, along with the data set above, is still 3x faster for 160,000 random values over the interval. It has however gotten me thinking of how i can parallelize the binary search i use so far. And given me some great hints on how to do so.

@Bruno - Ill look at that mex file tomorrow. What are the inputs it takes? Same as interp1? Is it like interp1q? I don't know what you are talking about with HISTC being the default. For my Matlab it is the cumulative histogram and im honestly not clever enough to get from histograms to searching sorted lists.

To both of you! Thank you so much for all your help and suggestions. They have really given me a lot to think about in terms of vectorizing my calls.
From: Paul on 28 Jul 2010 22:09
Corrections (again):

@Bruno - sorry, i missed the mention of interp1q in the link you sent me. A 20x speedup would be wonderful! Going to investigate that tomorrow.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: Refresh Simulink library browser
Next: Using Apache CXF in from MATLAB