Pythonネストされたループを減らす

Question

私はUVAの問題に取り組んでいます。ポリゴンのリストを反復するために4つのネストされたループがあります（各ポリゴンには、各ポイントに座標x、すなわち、ポリゴン[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 

とにかく私のコードは、どちらの場合も同じランタイムを持っている、そこにあります私のアルゴリズムのネストされたループの数を減らす方法？任意の助けを事前に

おかげで、感謝

Answer 1

あなたの二つの外側のループは組み合わせリストのを作成しています。それらにはitertools.combinations() iteratorを使用してください。あなたの一番内側の二重ループはカルチャンス商品を生成するので、itertools.product() iteratorを使用してください。

range(), just loop directly over the polygon lists; use enumerate（） `でインデックスを生成しないでください。インデックスを作成するのではなく、インデックスを追加します。

セクションをペアにするには、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 

実際に、何かが組合であると判断したら、残りのテストを続ける必要はありません。あなたは早くisInside()とdoIntersect機能のテストを停止するany() functionを使用することができます。

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) 

これだけはるかに読みやすい今、それはまた、より効率的であるべきではありません！