因此,我正在研究UVA问题,并且我有4个嵌套循环来遍历多边形列表(每个多边形都包含一个点列表,其中每个点都包含一个整数x和y来表示其坐标,即,polygon [0]是一个点,其坐标为面[0] .x和面[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()迭代器。您最里面的双循环会产生 笛卡尔积 ,因此请使用itertools.product()迭代器。
itertools.combinations()
itertools.product()
不要使用range(), just loop directly over the polygon lists; useenumerate()来生成索引以添加索引,而不要使索引相反。
range(), just loop directly over the polygon lists; use
到配对部分,该pairwise()配方从itertools食谱部; 这样您就可以使用所有细分。要再次从头开始绕圈(将最后一个坐标与第一个坐标配对),只需将列表的第一个元素附加到末尾即可。
pairwise()
itertools
一旦摆脱了嵌套循环,就可以使用break结束循环而不是使用标志变量。
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()功能停止测试isInside()和doIntersect早期的功能:
any()
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)
这不仅现在可读性强,而且还应该更有效!