help-octave
[Top][All Lists]

Re: Any possible optimization?

 From: CdeMills Subject: Re: Any possible optimization? Date: Mon, 10 Jan 2011 09:39:49 -0800 (PST)

c.-2 wrote:
>
>
> On 10 Jan 2011, at 16:15, Daniel Arteaga wrote:
>
>> Hi all
>>
>> The following function is called many times in my code (always from the
>> same point), and it is actually the bottleneck of the computation:
>>
>> function [s,t] = intersectionPoint(a,b,c,d)
>>
>>      % Solve the system of equations
>>      % (1 - s) ax + s bx = (1 - t) cx + t dx
>>      % (1 - s) ay + s by = (1 - t) cy + t dy
>>
>>      A = [ b(1) - a(1), c(1) - d(1); b(2) - a(2), c(2) - d(2)];
>>      B = [ c(1) - a(1); c(2) - a(2)];
>>
>>      v = A\B;
>>      s = v(1);
>>      t = v(2);
>>
>> endfunction
>>
>>
>> Is there any easy way to get a speed increase? Is it worth transforming
>> it into an .oct file? Or maybe including the expressions inline to avoid
>> the function call overhead?
>>
>> Any suggestion is appreciated.
>>
>> Thank you very much,
>>
>> Daniel Arteaga
>>
>
> Your system can be easily solved explicitely so the function can be
> written as:
>
> function [s,t] = intersectionPoint2(a,b,c,d)
>
>   aa = (b - a);
>   bb = (c - d);
>   cc = (c - a);
>   det = (-aa(2)* bb(1) + aa(1)* bb(2));
>   s   = (bb(2)* cc(1) - bb(1) *cc(2))/det;
>   t   = -(aa(2)* cc(1) - aa(1) *cc(2))/det;
>
> endfunction
>
>

If the function is called many times from the same place, the best way is to
not use function call at all and vectorise the code. Let say that your
points coordinates are in row matrices:
aa = b-a; bb = c-d; cc = c-a;
my_idet = 1./(aa(:, 1).*bb(:, 2)-aa(:, 2).*bb(:, 1));
s = (bb(:, 2).*cc(:, 1) - bb(:, 1).*cc(:, 1)).*my_idet;
t = (aa(:, 1).*cc(:, 2) - aa(:, 2).*cc(:, 1)).*my_idet;

This way, there is no 'for' loop, nor function call. The names of variables
should not alias function names (det). The last small optimisation is that
(I learned it a long time ago), floating point division is slower than
multiplication, so the inverse of the determinant is computed only once.

Regards

Pascal
--
View this message in context:
http://octave.1599824.n4.nabble.com/Any-possible-optimization-tp3207360p3207655.html
Sent from the Octave - General mailing list archive at Nabble.com.

reply via email to