Python 减少嵌套循环

Question

所以我正在处理一个 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

不管怎样，我的代码在两种情况下都具有相同的运行时间，有没有办法减少我的算法的嵌套循环数量？

在此先感谢您提供的帮助，非常感谢

Answer 1

您的两个外部循环正在创建列表的组合；使用 itertools.combinations() iterator for those. Your innermost double loop produces the carthesian product, so use the itertools.product() iterator.

不要使用 range(), just loop directly over the polygon lists; useenumerate()` 生成索引来添加索引，而不是让索引以相反的方式工作。

要配对部分，itertools 食谱部分的 pairwise() recipe；这将使您可以使用所有细分市场。要再次绕到起点（将最后一个坐标与第一个坐标配对），只需将一个包含第一个元素的列表附加到末尾即可。

摆脱嵌套循环后，您可以使用 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 减少嵌套循环

Python Reducing Nested Loops

python

nested-loops

python-3.x