Stick (line segments) percolation algorithm - graph theory?
Hi experts! I wrote an algorithm for study stick percolation (i.e.: networks between line segments that intersect between them). In my algorithm N sticks (line segments) are created inside a rectanglar box of sides 'b' and 'h' and then, one by one, the algorithm explores the intersection between all line segments. This is a Monte Carlo simulation, so the 'experiment' is executed many times (no less than 100 times). Writen like that, very much RAM is consumed: array_x1=uniform.rvs(loc=-b/2,scale=b,size=N) array_y1=uniform.rvs(loc=-h/2,scale=h,size=N) array_x2=uniform.rvs(loc=-b/2,scale=b,size=N) array_y2=uniform.rvs(loc=-h/2,scale=h,size=N) M =np.zeros([N,N]) foru inxrange(100): ---->This'100'isthe number of experiments. forj inxrange(N): ifj>0: x_A1B1 =array_x2[j]-array_x1[j] y_A1B1 =array_y2[j]-array_y1[j] x_A1A2 =array_x1[0:j]-array_x1[j] y_A1A2 =array_y1[0:j]-array_y1[j] x_A2A1 =-1*x_A1A2 y_A2A1 =-1*y_A1A2 x_A2B2 =array_x2[0:j]-array_x1[0:j] y_A2B2 =array_y2[0:j]-array_y1[0:j] x_A1B2 =array_x2[0:j]-array_x1[j] y_A1B2 =array_y2[0:j]-array_y1[j] x_A2B1 =array_x2[j]-array_x1[0:j] y_A2B1 =array_y2[j]-array_y1[0:j] p1 =x_A1B1*y_A1A2 -y_A1B1*x_A1A2 p2 =x_A1B1*y_A1B2 -y_A1B1*x_A1B2 p3 =x_A2B2*y_A2B1 -y_A2B2*x_A2B1 p4 =x_A2B2*y_A2A1 -y_A2B2*x_A2A1 condition_1=p1*p2 condition_2=p3*p4 fork inxrange (j): ifcondicion_1[k]<=0andcondicion_2[k]<=0: M[j,k]=1 ifj+1<N+4: x_A1B1 =array_x2[j]-array_x1[j] y_A1B1 =array_y2[j]-array_y1[j] x_A1A2 =array_x1[j+1:]-array_x1[j] y_A1A2 =array_y1[j+1:]-array_y1[j] x_A2A1 =-1*x_A1A2 y_A2A1 =-1*y_A1A2 x_A2B2 =array_x2[j+1:]-array_x1[j+1:] y_A2B2 =array_y2[j+1:]-array_y1[j+1:] x_A1B2 =array_x2[j+1:]-array_x1[j] y_A1B2 =array_y2[j+1:]-array_y1[j] x_A2B1 =array_x2[j]-array_x1[j+1:] y_A2B1 =array_y2[j]-array_y1[j+1:] p1 =x_A1B1*y_A1A2 -y_A1B1*x_A1A2 p2 =x_A1B1*y_A1B2 -y_A1B1*x_A1B2 p3 =x_A2B2*y_A2B1 -y_A2B2*x_A2B1 p4 =x_A2B2*y_A2A1 -y_A2B2*x_A2A1 condicion_1=p1*p2 condicion_2=p3*p4 fork inxrange (N-j-1): ifcondicion_1[k]<=0andcondicion_2[k]<=0: M[j,k+j+1]=1 Here, the element Mij=1 if stick i intersect stick j and Mij=0 if not. How can i optimize my algorithm? Graph theory is usefull in this case? Waiting for your answers. Thanks a lot! Best regards
I can see a couple opportunities for improvements in your algorithm. Running your code on a single experiment, I get about 2.9 seconds to run. I get this down to about 1.0 seconds by (1) exploiting the symmetry of the M matrix and (2) avoiding the costly inner loop over k in favor of array operations: def check_segments(j, others, data): x1, y1, x2, y2 = data x_A1B1 = x2[j]-x1[j] y_A1B1 = y2[j]-y1[j] x_A1A2 = x1[others]-x1[j] y_A1A2 = y1[others]-y1[j] x_A2A1 = -1*x_A1A2 y_A2A1 = -1*y_A1A2 x_A2B2 = x2[others]-x1[others] y_A2B2 = y2[others]-y1[others] x_A1B2 = x2[others]-x1[j] y_A1B2 = y2[others]-y1[j] x_A2B1 = x2[j]-x1[others] y_A2B1 = y2[j]-y1[others] p1 = x_A1B1*y_A1A2 - y_A1B1*x_A1A2 p2 = x_A1B1*y_A1B2 - y_A1B1*x_A1B2 p3 = x_A2B2*y_A2B1 - y_A2B2*x_A2B1 p4 = x_A2B2*y_A2A1 - y_A2B2*x_A2A1 condition_1=p1*p2 condition_2=p3*p4 return (p1 * p2 <= 0) & (p3 * p4 <= 0) for j in xrange(1, N): valid = check_segments(j, range(j), (x1, y1, x2, y2)) M[j,0:j] = valid M[0:j,j] = valid I don't see any other particularly simple ways to improve this. You could probably add an interval check to ensure that the x and y intervals for the segments of interest overlap before doing the full check, but how much that would help would depend on the implementations. ~Brett On Fri, Aug 23, 2013 at 5:09 PM, Josè Luis Mietta < joseluismietta@yahoo.com.ar> wrote:
I wrote an algorithm for study stick percolation (i.e.: networks between line segments that intersect between them). In my algorithm N sticks (line segments) are created inside a rectangular box of sides 'b' and 'h' and then, one by one, the algorithm explores the intersection between all line segments. This is a Monte Carlo simulation, so the 'experiment' is executed many times (no less than 100 times). Written like that, very much RAM is consumed: Here, the element Mij=1 if stick i intersects stick j and Mij=0 if not. How can I optimize my algorithm? Graph theory is useful in this case?
Thanks a lot!! José Luis ________________________________ De: Brett Olsen <brett.olsen@gmail.com> Para: Discussion of Numerical Python <numpy-discussion@scipy.org> Enviado: lunes, 26 de agosto de 2013 14:08 Asunto: Re: [Numpy-discussion] Stick (line segments) percolation algorithm - graph theory? I can see a couple opportunities for improvements in your algorithm. Running your code on a single experiment, I get about 2.9 seconds to run. I get this down to about 1.0 seconds by (1) exploiting the symmetry of the M matrix and (2) avoiding the costly inner loop over k in favor of array operations: def check_segments(j, others, data): x1, y1, x2, y2 = data x_A1B1 = x2[j]-x1[j] y_A1B1 = y2[j]-y1[j] x_A1A2 = x1[others]-x1[j] y_A1A2 = y1[others]-y1[j] x_A2A1 = -1*x_A1A2 y_A2A1 = -1*y_A1A2 x_A2B2 = x2[others]-x1[others] y_A2B2 = y2[others]-y1[others] x_A1B2 = x2[others]-x1[j] y_A1B2 = y2[others]-y1[j] x_A2B1 = x2[j]-x1[others] y_A2B1 = y2[j]-y1[others] p1 = x_A1B1*y_A1A2 - y_A1B1*x_A1A2 p2 = x_A1B1*y_A1B2 - y_A1B1*x_A1B2 p3 = x_A2B2*y_A2B1 - y_A2B2*x_A2B1 p4 = x_A2B2*y_A2A1 - y_A2B2*x_A2A1 condition_1=p1*p2 condition_2=p3*p4 return (p1 * p2 <= 0) & (p3 * p4 <= 0) for j in xrange(1, N): valid = check_segments(j, range(j), (x1, y1, x2, y2)) M[j,0:j] = valid M[0:j,j] = valid I don't see any other particularly simple ways to improve this. You could probably add an interval check to ensure that the x and y intervals for the segments of interest overlap before doing the full check, but how much that would help would depend on the implementations. ~Brett On Fri, Aug 23, 2013 at 5:09 PM, Josè Luis Mietta <joseluismietta@yahoo.com.ar> wrote: I wrote an algorithm for study stick percolation (i.e.: networks between line segments that intersect between them). In my algorithm N sticks (line segments) are created inside a rectangular box of sides 'b' and 'h' and then, one by one, the algorithm explores the intersection between all line segments. This is a Monte Carlo simulation, so the 'experiment' is executed many times (no less than 100 times). Written like that, very much RAM is consumed: Here, the element Mij=1 if stick i intersects stick j and Mij=0 if not.
How can I optimize my algorithm? Graph theory is useful in this case?
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
participants (2)
-
Brett Olsen -
Josè Luis Mietta