Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
How to decrease the execution time of the piece of code?

Subject: How to decrease the execution time of the piece of code?

From: Liana

Date: 18 Apr, 2011 20:29:07

Message: 1 of 13

Hello,

I have a code (see below) used to fill the connection matrix. This connection matrix is used by the dijkstra algorithm to find the shortest path. If the ith point and its jth neighbor are not inside any obstacle, then ConMat(i,j) = 1 (the transition is available). Otherwise, ConMat(i,j) = 0.
I'd like to know if it's possible to update this code below in order to decrease its execution time? The thing is that I have many points to be evaluated and this code takes a lot of time to be completed. Thanks.

ConMat = zeros(numtri);
for i = 1:numtri
   centroids(i,:) = (tetrahedron_centroid_3d(dt,i))';
   neigh = neighbors(dt,i);
   isInside = isInsideObstacle(dt,i,obstdt);
   % Determine if the point is inside/outside the nearest tetrahedron
   if ~isInside
       for j = 1:4
           if (~isnan(neigh(1,j)))
               isInside = isInsideObstacle(dt,neigh(1,j),obstdt);
               if ~isInside
                   ConMat(i,(neigh(1,j))) = 1;
               end
           end
       end
   end;
end

Subject: How to decrease the execution time of the piece of code?

From: Liana

Date: 18 Apr, 2011 20:58:05

Message: 2 of 13

I have the following idea:
ConMat = zeros(numtri);
centroids(1:numtri,:) = (tetrahedron_centroid_3d(dt,1:numtri))';
neigh(1:numtri,:) = neighbors(dt,1:numtri);
isInside(1:numtri) = isInsideObstacle(dt,1:numtri,obstdt);

a = find(~isInside(1:numtri));
ConMat(a,a) = 1;

Perhaps, there might be any other ways?

"Liana" wrote in message <ioi6uj$gtv$1@fred.mathworks.com>...
> Hello,
>
> I have a code (see below) used to fill the connection matrix. This connection matrix is used by the dijkstra algorithm to find the shortest path. If the ith point and its jth neighbor are not inside any obstacle, then ConMat(i,j) = 1 (the transition is available). Otherwise, ConMat(i,j) = 0.
> I'd like to know if it's possible to update this code below in order to decrease its execution time? The thing is that I have many points to be evaluated and this code takes a lot of time to be completed. Thanks.
>
> ConMat = zeros(numtri);
> for i = 1:numtri
> centroids(i,:) = (tetrahedron_centroid_3d(dt,i))';
> neigh = neighbors(dt,i);
> isInside = isInsideObstacle(dt,i,obstdt);
> % Determine if the point is inside/outside the nearest tetrahedron
> if ~isInside
> for j = 1:4
> if (~isnan(neigh(1,j)))
> isInside = isInsideObstacle(dt,neigh(1,j),obstdt);
> if ~isInside
> ConMat(i,(neigh(1,j))) = 1;
> end
> end
> end
> end;
> end

Subject: How to decrease the execution time of the piece of code?

From: Matt J

Date: 18 Apr, 2011 21:03:04

Message: 3 of 13

"Liana" wrote in message <ioi6uj$gtv$1@fred.mathworks.com>...
> Hello,
>
> I have a code (see below) used to fill the connection matrix. This connection matrix is used by the dijkstra algorithm to find the shortest path. If the ith point and its jth neighbor are not inside any obstacle, then ConMat(i,j) = 1 (the transition is available). Otherwise, ConMat(i,j) = 0.
> I'd like to know if it's possible to update this code below in order to decrease its execution time?
=========================

Have you checked for files on the FEX like the following

http://www.mathworks.com/matlabcentral/fileexchange/30707-travel-guide-gridless-based-djikstra-algorithm

to see what performance they offer (and to check that you're not reinventing the wheel)?

Subject: How to decrease the execution time of the piece of code?

From: Liana

Date: 18 Apr, 2011 21:25:08

Message: 4 of 13

Thank you, Matt! I'm using the dijkstra algorithm that I found on FEX. However, one of its inputs is the connection matrix. To create the connection matrix, I'm using the code above. But it's very-very slow. Therefore, I'm interested in reformulating this code in some way to decrease its execution time.

"Matt J" wrote in message <ioi8u8$mge$1@fred.mathworks.com>...
> "Liana" wrote in message <ioi6uj$gtv$1@fred.mathworks.com>...
> > Hello,
> >
> > I have a code (see below) used to fill the connection matrix. This connection matrix is used by the dijkstra algorithm to find the shortest path. If the ith point and its jth neighbor are not inside any obstacle, then ConMat(i,j) = 1 (the transition is available). Otherwise, ConMat(i,j) = 0.
> > I'd like to know if it's possible to update this code below in order to decrease its execution time?
> =========================
>
> Have you checked for files on the FEX like the following
>
> http://www.mathworks.com/matlabcentral/fileexchange/30707-travel-guide-gridless-based-djikstra-algorithm
>
> to see what performance they offer (and to check that you're not reinventing the wheel)?

Subject: How to decrease the execution time of the piece of code?

From: Matt J

Date: 18 Apr, 2011 21:38:05

Message: 5 of 13

"Liana" wrote in message <ioi8kt$h93$1@fred.mathworks.com>...
> I have the following idea:
> ConMat = zeros(numtri);
> centroids(1:numtri,:) = (tetrahedron_centroid_3d(dt,1:numtri))';
> neigh(1:numtri,:) = neighbors(dt,1:numtri);
> isInside(1:numtri) = isInsideObstacle(dt,1:numtri,obstdt);
>
> a = find(~isInside(1:numtri));
> ConMat(a,a) = 1;
=========================

Well, for one thing, there is no need for FIND, here. Just make "a" a logical index

 a = ~isInside(1:numtri);


The rest of it is pretty hard to evaluate. Most of the functionality seems to be buried inside some major functions like isInsideObstacle and tetrahedron_centroid_3d, whose implementations we cannot see.

We also don't know what dt or obstdt is (arrays, scalars,....) or how they're processed.

Subject: How to decrease the execution time of the piece of code?

From: Liana

Date: 18 Apr, 2011 21:55:20

Message: 6 of 13

Thanks.

1) dt and obstdt contain 3D Delaunay Triangluation of the space and obstacles, accordingly.
2) isInsideObstacle returns 0 or 1, depending of whether the centroid of the i-th tetrahedron is outside or inside any obstacle.
3) tetrahedron_centroid_3d returns X,Y,Z coordinates of the centroid of the i-th tetrahedron.

I don't think I need to post the code of 'isInsideObstacle' and 'tetrahedron_centroid_3d', but I will do it if it might help.

So far I have:
ConMat = zeros(numtri);
centroids(numtri,:) = (tetrahedron_centroid_3d(dt,numtri))';
neigh(numtri,:) = neighbors(dt,numtri);
isInside(numtri) = isInsideObstacle(dt,numtri,obstdt);
a = ~isInside(1:numtri);
ConMat(a,a) = 1;

The problem is that isInside(numtri) is always equal to 0, however if I run my long-running code, then 'isInside' contains both 0 and 1. So, assume there is an error in my shortened formulation.

"Matt J" wrote in message <ioiavt$rqu$1@fred.mathworks.com>...
> "Liana" wrote in message <ioi8kt$h93$1@fred.mathworks.com>...
> > I have the following idea:
> > ConMat = zeros(numtri);
> > centroids(1:numtri,:) = (tetrahedron_centroid_3d(dt,1:numtri))';
> > neigh(1:numtri,:) = neighbors(dt,1:numtri);
> > isInside(1:numtri) = isInsideObstacle(dt,1:numtri,obstdt);
> >
> > a = find(~isInside(1:numtri));
> > ConMat(a,a) = 1;
> =========================
>
> Well, for one thing, there is no need for FIND, here. Just make "a" a logical index
>
> a = ~isInside(1:numtri);
>
>
> The rest of it is pretty hard to evaluate. Most of the functionality seems to be buried inside some major functions like isInsideObstacle and tetrahedron_centroid_3d, whose implementations we cannot see.
>
> We also don't know what dt or obstdt is (arrays, scalars,....) or how they're processed.

Subject: How to decrease the execution time of the piece of code?

From: Liana

Date: 18 Apr, 2011 22:04:04

Message: 7 of 13

One more comment: I have a concave hull that corresponds to obstacles. Therefore, I'm using two Delaunay Triangulations. This approach works fine. The only problem is with the execution time.

"Liana" wrote in message <ioic08$e6l$1@fred.mathworks.com>...
> Thanks.
>
> 1) dt and obstdt contain 3D Delaunay Triangluation of the space and obstacles, accordingly.
> 2) isInsideObstacle returns 0 or 1, depending of whether the centroid of the i-th tetrahedron is outside or inside any obstacle.
> 3) tetrahedron_centroid_3d returns X,Y,Z coordinates of the centroid of the i-th tetrahedron.
>
> I don't think I need to post the code of 'isInsideObstacle' and 'tetrahedron_centroid_3d', but I will do it if it might help.
>
> So far I have:
> ConMat = zeros(numtri);
> centroids(numtri,:) = (tetrahedron_centroid_3d(dt,numtri))';
> neigh(numtri,:) = neighbors(dt,numtri);
> isInside(numtri) = isInsideObstacle(dt,numtri,obstdt);
> a = ~isInside(1:numtri);
> ConMat(a,a) = 1;
>
> The problem is that isInside(numtri) is always equal to 0, however if I run my long-running code, then 'isInside' contains both 0 and 1. So, assume there is an error in my shortened formulation.
>
> "Matt J" wrote in message <ioiavt$rqu$1@fred.mathworks.com>...
> > "Liana" wrote in message <ioi8kt$h93$1@fred.mathworks.com>...
> > > I have the following idea:
> > > ConMat = zeros(numtri);
> > > centroids(1:numtri,:) = (tetrahedron_centroid_3d(dt,1:numtri))';
> > > neigh(1:numtri,:) = neighbors(dt,1:numtri);
> > > isInside(1:numtri) = isInsideObstacle(dt,1:numtri,obstdt);
> > >
> > > a = find(~isInside(1:numtri));
> > > ConMat(a,a) = 1;
> > =========================
> >
> > Well, for one thing, there is no need for FIND, here. Just make "a" a logical index
> >
> > a = ~isInside(1:numtri);
> >
> >
> > The rest of it is pretty hard to evaluate. Most of the functionality seems to be buried inside some major functions like isInsideObstacle and tetrahedron_centroid_3d, whose implementations we cannot see.
> >
> > We also don't know what dt or obstdt is (arrays, scalars,....) or how they're processed.

Subject: How to decrease the execution time of the piece of code?

From: Liana

Date: 18 Apr, 2011 23:47:04

Message: 8 of 13

Let me specify my question. For instance, if I use the following code:
centroids(1,:) = (tetrahedron_centroid_3d(dt,1))';
...then:
centroids(1,:) = 0.6 0.6 0.5

However, if I try to get centroids for 1:numtri:
centroids(numtri,:) = (tetrahedron_centroid_3d(dt,numtri))';
...then:
centroids(1,:) = 0 0 0 (must be 0.6 0.6 0.5)

So, where is an error in the expression:
centroids(numtri,:) = (tetrahedron_centroid_3d(dt,numtri))';
?

Thanks.

"Liana" wrote in message <ioicgk$mou$1@fred.mathworks.com>...
> One more comment: I have a concave hull that corresponds to obstacles. Therefore, I'm using two Delaunay Triangulations. This approach works fine. The only problem is with the execution time.
>
> "Liana" wrote in message <ioic08$e6l$1@fred.mathworks.com>...
> > Thanks.
> >
> > 1) dt and obstdt contain 3D Delaunay Triangluation of the space and obstacles, accordingly.
> > 2) isInsideObstacle returns 0 or 1, depending of whether the centroid of the i-th tetrahedron is outside or inside any obstacle.
> > 3) tetrahedron_centroid_3d returns X,Y,Z coordinates of the centroid of the i-th tetrahedron.
> >
> > I don't think I need to post the code of 'isInsideObstacle' and 'tetrahedron_centroid_3d', but I will do it if it might help.
> >
> > So far I have:
> > ConMat = zeros(numtri);
> > centroids(numtri,:) = (tetrahedron_centroid_3d(dt,numtri))';
> > neigh(numtri,:) = neighbors(dt,numtri);
> > isInside(numtri) = isInsideObstacle(dt,numtri,obstdt);
> > a = ~isInside(1:numtri);
> > ConMat(a,a) = 1;
> >
> > The problem is that isInside(numtri) is always equal to 0, however if I run my long-running code, then 'isInside' contains both 0 and 1. So, assume there is an error in my shortened formulation.
> >
> > "Matt J" wrote in message <ioiavt$rqu$1@fred.mathworks.com>...
> > > "Liana" wrote in message <ioi8kt$h93$1@fred.mathworks.com>...
> > > > I have the following idea:
> > > > ConMat = zeros(numtri);
> > > > centroids(1:numtri,:) = (tetrahedron_centroid_3d(dt,1:numtri))';
> > > > neigh(1:numtri,:) = neighbors(dt,1:numtri);
> > > > isInside(1:numtri) = isInsideObstacle(dt,1:numtri,obstdt);
> > > >
> > > > a = find(~isInside(1:numtri));
> > > > ConMat(a,a) = 1;
> > > =========================
> > >
> > > Well, for one thing, there is no need for FIND, here. Just make "a" a logical index
> > >
> > > a = ~isInside(1:numtri);
> > >
> > >
> > > The rest of it is pretty hard to evaluate. Most of the functionality seems to be buried inside some major functions like isInsideObstacle and tetrahedron_centroid_3d, whose implementations we cannot see.
> > >
> > > We also don't know what dt or obstdt is (arrays, scalars,....) or how they're processed.

Subject: How to decrease the execution time of the piece of code?

From: Matt J

Date: 19 Apr, 2011 04:05:23

Message: 9 of 13

"Liana" wrote in message <ioiiho$qpc$1@fred.mathworks.com>...
>
> However, if I try to get centroids for 1:numtri:
> centroids(numtri,:) = (tetrahedron_centroid_3d(dt,numtri))';
> ...then:
> centroids(1,:) = 0 0 0 (must be 0.6 0.6 0.5)
>
> So, where is an error in the expression:
> centroids(numtri,:) = (tetrahedron_centroid_3d(dt,numtri))';
============================


should probably be

centroids(1:numtri,:) = something

Subject: How to decrease the execution time of the piece of code?

From: Liana

Date: 19 Apr, 2011 04:49:05

Message: 10 of 13

I've tried:

centroids(1:numtri,:) = (tetrahedron_centroid_3d(dt,1:numtri))';
and
centroids(1:numtri,:) = (tetrahedron_centroid_3d(dt,numtri))';

In both cases the error is:
"Subscripted assignment dimension mismatch"

For each i the function (tetrahedron_centroid_3d(dt,i))' returns a vector (1x3), e.g. [1 2 3].

What is wrong? Thanks.

"Matt J" wrote in message <ioj1m3$mfu$1@fred.mathworks.com>...
> "Liana" wrote in message <ioiiho$qpc$1@fred.mathworks.com>...
> >
> > However, if I try to get centroids for 1:numtri:
> > centroids(numtri,:) = (tetrahedron_centroid_3d(dt,numtri))';
> > ...then:
> > centroids(1,:) = 0 0 0 (must be 0.6 0.6 0.5)
> >
> > So, where is an error in the expression:
> > centroids(numtri,:) = (tetrahedron_centroid_3d(dt,numtri))';
> ============================
>
>
> should probably be
>
> centroids(1:numtri,:) = something

Subject: How to decrease the execution time of the piece of code?

From: Liana

Date: 19 Apr, 2011 04:59:07

Message: 11 of 13

I think the problem is here:
a = size((tetrahedron_centroid_3d(dt,1:numtri))');
a =
1 3

That's strange, because 'numtri' is equal to 1000 and 'a' must be equal to 1000x3.


"Liana" wrote in message <ioj481$1vn$1@fred.mathworks.com>...
> I've tried:
>
> centroids(1:numtri,:) = (tetrahedron_centroid_3d(dt,1:numtri))';
> and
> centroids(1:numtri,:) = (tetrahedron_centroid_3d(dt,numtri))';
>
> In both cases the error is:
> "Subscripted assignment dimension mismatch"
>
> For each i the function (tetrahedron_centroid_3d(dt,i))' returns a vector (1x3), e.g. [1 2 3].
>
> What is wrong? Thanks.
>
> "Matt J" wrote in message <ioj1m3$mfu$1@fred.mathworks.com>...
> > "Liana" wrote in message <ioiiho$qpc$1@fred.mathworks.com>...
> > >
> > > However, if I try to get centroids for 1:numtri:
> > > centroids(numtri,:) = (tetrahedron_centroid_3d(dt,numtri))';
> > > ...then:
> > > centroids(1,:) = 0 0 0 (must be 0.6 0.6 0.5)
> > >
> > > So, where is an error in the expression:
> > > centroids(numtri,:) = (tetrahedron_centroid_3d(dt,numtri))';
> > ============================
> >
> >
> > should probably be
> >
> > centroids(1:numtri,:) = something

Subject: How to decrease the execution time of the piece of code?

From: Steven_Lord

Date: 19 Apr, 2011 13:53:25

Message: 12 of 13



"Liana " <liananapalkova@email.arizona.edu> wrote in message
news:ioj4qr$akl$1@fred.mathworks.com...
> I think the problem is here:
> a = size((tetrahedron_centroid_3d(dt,1:numtri))');
> a =
> 1 3
>
> That's strange, because 'numtri' is equal to 1000 and 'a' must be equal to
> 1000x3.

Check the documentation for tetrahedron_centroid_3d and make sure it can
accept a vector of values for its second input.
If it does, you will need to debug why this function returns results of a
different size than you expect.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Subject: How to decrease the execution time of the piece of code?

From: Liana

Date: 19 Apr, 2011 19:33:05

Message: 13 of 13

Thank you, Steven. I got the point.

"Steven_Lord" <slord@mathworks.com> wrote in message <iok443$j21$1@fred.mathworks.com>...
>
>
> "Liana " <liananapalkova@email.arizona.edu> wrote in message
> news:ioj4qr$akl$1@fred.mathworks.com...
> > I think the problem is here:
> > a = size((tetrahedron_centroid_3d(dt,1:numtri))');
> > a =
> > 1 3
> >
> > That's strange, because 'numtri' is equal to 1000 and 'a' must be equal to
> > 1000x3.
>
> Check the documentation for tetrahedron_centroid_3d and make sure it can
> accept a vector of values for its second input.
> If it does, you will need to debug why this function returns results of a
> different size than you expect.
>
> --
> Steve Lord
> slord@mathworks.com
> To contact Technical Support use the Contact Us link on
> http://www.mathworks.com

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us