所以我正在研究UVA问题,我有4个嵌套循环来迭代多边形列表(每个多边形包含一个点列表,其中每个点包含一个整数x和y来表示它的坐标,即多边形[0 ] 是坐标为 Polygon[0].x 和 Polygon[0].y) 的点。
我正在尝试减少程序中 for 循环的数量,以提高其效率并缩短运行时间。我的代码如下:
for i in range(len(polygons)): # iterate over all the different polygons in the test case
for j in range(i+1, len(polygons)): # iterate over all the different polygons in the test case but starting from the second, in order to make comparations between polygons i and j
for a in range(len(polygons[i])):
if (isInside(polygons[i][a].x, polygons[i][a].y, polygons[j])):
union(i,j)
for a in range(len(polygons[j])):
if (isInside(polygons[j][a].x, polygons[j][a].y, polygons[i])):
union(i,j)
f = 1
for a in range(len(polygons[i])): # iterate over all the different points in the polygon i
for b in range(len(polygons[j])): # iterate over all the different points in the polygon j
if (f!=0):
if(doIntersect(polygons[i][a], polygons[i][(a+1)%len(polygons[i])],polygons[j][b], polygons[j][(b+1)%len(polygons[j])])): # check if every single pair of line segments, each one made up of two points, intersect with each other
union(i,j) # the two line segments intersect so we join them by using union
f = 0
我尝试通过使用 itertools.product 来提高效率,如下所示:
def solve():
global polygons, p
ranges = [range(len(polygons)), range(1,len(polygons))]
for i, j in product(*ranges):
for a in range(len(polygons[i])):
if (isInside(polygons[i][a].x, polygons[i][a].y, polygons[j])):
union(i,j)
for a in range(len(polygons[j])):
if (isInside(polygons[j][a].x, polygons[j][a].y, polygons[i])):
union(i,j)
f = 1
ranges2 = [range(len(polygons[i])), range(len(polygons[j]))]
for a,b in product(*ranges2):
if (f!=0):
if(doIntersect(polygons[i][a], polygons[i][(a+1)%len(polygons[i])],polygons[j][b], polygons[j][(b+1)%len(polygons[j])])): # check if every single pair of line segments, each one made up of two points, intersect with each other
union(i,j) # the two line segments intersect so we join them by using union
f = 0
无论如何,我的代码在两种情况下都具有相同的运行时,有没有办法减少我的算法的嵌套循环数量?
预先感谢您提供的任何帮助,非常感谢
最佳答案
您的两个外部循环正在创建列表的组合;使用 itertools.combinations()
iterator对于那些。最里面的双循环产生笛卡尔积,所以使用 itertools.product()
iterator .
不要使用 range(), just loop directly over the polygon lists; use
生成索引enumerate()` 添加索引而不是使索引以相反的方式工作。
为了配对各个部分, pairwise()
recipe来自itertools
食谱部分;这将使您可以使用所有部分。要再次绕回起点(将最后一个坐标与第一个坐标配对),只需将包含第一个元素的列表附加到末尾即可。
摆脱嵌套循环后,您可以使用 break
结束它们而不是使用标志变量。
from itertools import combinations, product
def pairwise(iterable):
"s -> (s0,s1), (s1,s2), (s2, s3), ..."
a, b = tee(iterable)
next(b, None)
return zip(a, b)
for (i, a_poly), (j, b_poly) in combinations(enumerate(polygons), 2):
for a in a_poly:
if isInside(a.x, a.y, b_poly):
union(i, j)
for b in b_poly:
if isInside(b.x, b.y, a_poly):
union(j, i)
# attach the first element at the end so you go 'round'
a_segments = pairwise(a_poly + a_poly[:1])
b_segments = pairwise(b_poly + b_poly[:1])
for a_seg, b_seg in product(a_segments, b_segments):
if doIntersect(*a_seg, *b_seg):
union(i,j)
break
事实上,一旦确定某个东西是并集,您就不必继续其余的测试。您可以使用 any()
function停止测试 isInside()
和doIntersect
早期功能:
for (i, a_poly), (j, b_poly) in combinations(enumerate(polygons), 2):
if any(isInside(a.x, a.y, b_poly) for a in a_poly):
union(i, j)
break # union found, no need to look further
for any(isInside(b.x, b.y, a_poly) for b in b_poly):
union(i, j)
break # union found, no need to look further
# attach the first element at the end so you go 'round'
a_segments = pairwise(a_poly + a_poly[:1])
b_segments = pairwise(b_poly + b_poly[:1])
if any(doIntersect(*a_seg, *b_seg)
for a_seg, b_seg in product(a_segments, b_segments)):
union(i,j)
现在这不仅更具可读性,而且还应该更加高效!
关于Python 减少嵌套循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43921489/