Quantcast

Recursion

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Recursion

Thomas D. Dean-2
I have an application that is called with two points and returns the
distance between the points and a mid point.  One example returns a
distance of 5474.  My function is not linear.  But, a more simple
example illustrates my problem.

function [dist, mid] = gc(p1,p2)
   p3 = p2 - p1;
   dist = sqrt(p3*p3');
   mid = (p1 + p2) ./ 2;
endfunction;

[distance, midpoint] = gc(P1,P2)
while distance > 300
   [distance, midpoint] = gc(P1,midpoint)
endwhile;

This gives me 7 points.  But, I want all the points from
P1, midpoint1, midpoint2, ..., P2

I could recurse, call the first time.
recurse on each half, p1, m1 and m1,p2

How do I do this and get all the points in order?

Tom Dean

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recursion

Thomas D. Dean-2
On 03/06/2017 07:06 PM, Thomas D. Dean wrote:
> I have an application that is called with two points and returns the
> distance between the points and a mid point.  One example returns a
> distance of 5474.  My function is not linear.  But, a more simple
> example illustrates my problem.
>
Here is a better example, which produces the output I want to save.  The
printf(...) statement displays the data I want to keep, in the order I
want it.

function [dist, mid] = gcr(p1,p2)
   p3 = p2 - p1;
   dist = sqrt(p3*p3');
   mid = (p1 + p2) ./ 2;
   if dist < 300
     printf("[%.1f %.1f] [%.1f %.1f] %.1f [%.1f %.1f]\n",p1,p2,dist,mid)
   endif;
   if dist > 300
     savemid = mid;
     [dist, mid] = gcr(p1, mid);
     [dist, mid] = gcr(savemid, p2);
   endif;
endfunction;

P1=[1000,2000]
P2=[8000,9000]
[distance, midpoint] = gcr(P1,P2)

Tomj Dean

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recursion

Kire Pudsje


On Tue, Mar 7, 2017 at 4:24 AM, Thomas D. Dean <[hidden email]> wrote:
On 03/06/2017 07:06 PM, Thomas D. Dean wrote:
I have an application that is called with two points and returns the
distance between the points and a mid point.  One example returns a
distance of 5474.  My function is not linear.  But, a more simple
example illustrates my problem.

Here is a better example, which produces the output I want to save.  The printf(...) statement displays the data I want to keep, in the order I want it.


Do you really want to recurse?

function [dist, mid] = gcr(p1,p2)
  p3 = p2 - p1;
  dist = sqrt(p3*p3');
  mid = (p1 + p2) ./ 2;
endfunction;

list = [1000,2000; 8000,9000];
idx = 1;
while idx < size(list,1)
  [distance, midpoint] = gcr(list(idx, :), list(idx+1, :));
  if distance > 300
    list = [list(1:idx, :); midpoint; list((idx+1):end, :)];
  else
    idx++;
  end
end
 

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recursion

Thomas D. Dean-2
On 03/06/2017 08:25 PM, Kire Pudsje wrote:

>
>
> On Tue, Mar 7, 2017 at 4:24 AM, Thomas D. Dean <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     On 03/06/2017 07:06 PM, Thomas D. Dean wrote:
>
>         I have an application that is called with two points and returns the
>         distance between the points and a mid point.  One example returns a
>         distance of 5474.  My function is not linear.  But, a more simple
>         example illustrates my problem.
>
>     Here is a better example, which produces the output I want to save.
>     The printf(...) statement displays the data I want to keep, in the
>     order I want it.
>
>
> Do you really want to recurse?
>
> function [dist, mid] = gcr(p1,p2)
>   p3 = p2 - p1;
>   dist = sqrt(p3*p3');
>   mid = (p1 + p2) ./ 2;
> endfunction;
>
> list = [1000,2000; 8000,9000];
> idx = 1;
> while idx < size(list,1)
>   [distance, midpoint] = gcr(list(idx, :), list(idx+1, :));
>   if distance > 300
>     list = [list(1:idx, :); midpoint; list((idx+1):end, :)];
>   else
>     idx++;
>   end
> end
>

I avoided this because of list copy/allocation.  My application has a
larger list and this is the inner-most part of the application.

Be nice to vectorize...

Maybe the better way is to pre-allocate the list, recurse, and insert
data into it where I have the print statement.

Tom Dean

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recursion

Kire Pudsje


On Tue, Mar 7, 2017 at 9:24 PM, Thomas D. Dean <[hidden email]> wrote:
On 03/06/2017 08:25 PM, Kire Pudsje wrote:


On Tue, Mar 7, 2017 at 4:24 AM, Thomas D. Dean <[hidden email]
<mailto:[hidden email]>> wrote:

    On 03/06/2017 07:06 PM, Thomas D. Dean wrote:

        I have an application that is called with two points and returns the
        distance between the points and a mid point.  One example returns a
        distance of 5474.  My function is not linear.  But, a more simple
        example illustrates my problem.

    Here is a better example, which produces the output I want to save.
    The printf(...) statement displays the data I want to keep, in the
    order I want it.


Do you really want to recurse?


I avoided this because of list copy/allocation.  My application has a larger list and this is the inner-most part of the application.

Be nice to vectorize...

Maybe the better way is to pre-allocate the list, recurse, and insert data into it where I have the print statement.

I do not know how large a list you are talking about, I checked, but with a reduced distance of 1, resulting in a list of 16385 points, the total time is dominated by the call to gcr. As your gcr function is probably more complex it will be even more skewed.
Be sure to check the bottlenecks with the profiler. Since octave is an interpreted language, optimizing can be non-intuitive. You would expect preallocation can help, but you probable need some extra code updating indices, which needs to be interpreted again, and can slow things down.

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Loading...