Python 减少嵌套循环 [英] Python Reducing Nested Loops

问题描述

所以我正在处理一个 UVA 问题，我有 4 个嵌套循环来迭代多边形列表(每个多边形包含一个点列表，其中每个点包含一个整数 x 和 y 来表示它的坐标，即多边形 [0] 是坐标为多边形[0].x 和多边形[0].y) 的点.

So I am working on a UVA problem and I have 4 nested loops to iterate over a list of polygons (each polygon contains a list of points where each point contains an integer x and y to represent it's coordinates, i.e polygon[0] is a point which coordinates are polygon[0].x and polygon[0].y).

我正在尝试减少程序中的 for 循环次数，以提高效率并缩短运行时间.我的代码如下:

I am trying to reduce the number of for loops in the program in order to make it more efficient and have a lower runtime. My code is as follows:

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 使其更高效，如下所示:

And I tried to make it more efficient by using itertools.product as follows:

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

无论如何，我的代码在两种情况下都具有相同的运行时间，有没有办法减少算法的嵌套循环数?

Anyhow my code is having the same runtime in both cases, is there a way to reduce the number of nested loops for my algorithm?

预先感谢您提供的任何帮助，非常感谢

Thanks in advance for any given help, much appreciated

推荐答案

你的两个外部循环正在创建列表的组合；使用 itertools.combinations() 迭代器 对于那些.您最内层的双循环产生 carthesian 乘积，因此请使用 itertools.product() 迭代器.

Your two outer loops are creating combinations of lists; use the itertools.combinations() iterator for those. Your innermost double loop produces the carthesian product, so use the itertools.product() iterator.

不要用range()生成索引，直接在多边形列表上循环；使用enumerate()` 添加索引，而不是让索引反过来工作.

Don't generate indices with range(), just loop directly over the polygon lists; useenumerate()` to add indices rather than make indices work the other way around.

要配对部分，pairwise() recipe 来自 itertools 食谱部分；这将使您可以使用所有细分.要再次循环到起点(将最后一个坐标与第一个坐标配对)，只需将带有第一个元素的列表附加到末尾即可.

To pair up sections, the pairwise() recipe from the itertools recipes section; that'll let you get all segments to work with. To circle round to the start again (pairing up the last coordinate with the first), just append a list with the first element to the end.

一旦你摆脱了嵌套循环，你可以使用 break 来结束它们，而不是使用标志变量.

Once you get rid of nested loops, you can use break to end them rather than use a flag variable.

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 函数:

In fact, once you have determined something is a union, you don't have to continue with the rest of the tests. You could use the any() function to stop testing the isInside() and doIntersect functions early:

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)

这不仅现在更具可读性，而且应该更高效！

This is not only far more readable now, it should also be more efficient!

这篇关于Python 减少嵌套循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！