11

バックグラウンド：

さまざまな規則的な形状の頂点のネットワークに関連する大量のデータを処理するプログラムを作成しています。私は、ユーザー入力パラメーターの範囲に基づいて、上記の形状の頂点に対応するデカルト座標のリストを生成する作業ジェネレーターを持っています。データはフィルターに渡され、重複するエントリをクリアし、データを並べ替え、その他のさまざまな機能を実行します。ここから、クリーニングされたデータがキャンバス モジュールに送られ、キャンバス モジュールがループして頂点を描画します。

質問：

座標を効率的にループし、各ペアを他のすべてのペアと比較する新しいフィルターを実装する必要があります。つまり、すべてのエントリについて- (x1,y1)> (x2,y2)to (x1,y1)-> (xn,yn)、(x2,y2)-> (x3,y3)to (x2,y2)->など。の場合、2 つの座標セットがそれぞれのリスト エントリ番号とペアになり、新しいリストに追加されます。たとえば、1 つのエントリは次の形式になります。これを達成するための最も効率的な方法は何ですか?(xn,yn)(x1,y1)(x5,y5)[(x5-x1)^2+(y5-y1)^2]=vertex_spacing^2[(x1,y1), (x5,y5), 0, 4]

私の試み:

こことさまざまなガイドで、リストを処理するためのかなりの数の方法を見てきました。ネストされた 'for' ループと 'if' ループを試してみましたが、この方法は機能しますが、実行時間が過度に長くなるだけでなく、問題を多数の小さな for ループに分割しようとしていることがわかりました。

その他の注記:

これの最終的な目的は、結果の座標をフロントエンド インターフェイス要素に使用し、必要に応じて保存およびインポートすることです。リストの位置 0 と 4 の機能は、[(x1,y1), (x5,y5), 0, 4]キャンバス オブジェクトで後で使用するためにインターフェイスが座標をグループ化できるようにすることです。メソッドは、潜在的に数千の座標を処理できる必要があります。

事前に助けてくれてありがとう、もちろん、私が提供した言い回し/情報を改善したり、私が何を求めているのか不明な場合はサンプルコードを追加したりしたいと思っています-私はまだこれにかなり慣れていません! :)

4

4 に答える 4

6

基本的にチェックしているのは次のとおりです。

各頂点について、 を中心とした半径の円上にあるすべての頂点をv見つけます。uuvertex_spacingv

ポイントの分布が、すべてのポイントが近接しているわけではない場合、検索を高速化する 2 つの方法を考えます。

  1. このプロセスを高速化する最も簡単な方法は、ポイントを x 座標で並べ替えることです。そうすれば、多くの比較をスキップできます。簡単な例として、x 座標が[1, 2, 10, 15, 18, 20, 21]と であるとしvertex_spacing = 5ます。他のすべての頂点は明らかに最初の頂点の周りの円の外側にあるため、最初の頂点と 2 番目の頂点を比較するだけで済みます。

    すべての点が近接している場合、このアプローチは役に立たないことに注意してください。つまり、 の場合vertex_spacing = 25、比較をスキップすることはできません。

  2. 同じように、2 次元のkd ツリーを使用できます。これは、並べ替えアプローチと同等ですが、2 次元です。頂点(x, y)とが与えられたvertex_spacing = v場合、範囲 内のすべてのポイントをチェックする必要があります([x-v, x+v], [y-v, y+v])。前と同じ例を使用して、最初の点に座標が(1, 0)あり、2 番目の点に座標があると仮定(2, 10)すると、最初の頂点を何かと比較する必要はありません。

どちらのアプローチもヒューリスティックであり、最悪の場合の実行時間は改善されません (まったく逆: kd ツリーの並べ替え/構築のオーバーヘッドもあります)。ただし、通常、頂点が少なくともvertex_space離れている場合は、速度が上がる可能性があります。あなたの検索がたくさん。

于 2013-08-17T18:57:15.503 に答える
4

Heuster のアルゴリズムの説明を超えるには遅すぎましたが、x 座標による並べ替えアプローチの実装を次に示します。

def pairs(coords, vertex_spacing):
    results = []
    vsquared = vertex_spacing * vertex_spacing
    coords = sorted(coords)
    for ia, (xa, ya) in enumerate(coords):
        for ib, (xb, yb) in enumerate(coords[ia:]):
            dx = xb - xa
            if dx > vertex_spacing:
                break
            dy = yb - ya
            if dx * dx + dy * dy == vsquared:
                results.append([(xa, ya), (xb, yb), ia, ia + ib])
    return results

...そしてここでそれが実行されています：

>>> coords = list((x, y) for x in range(100) for y in range(100))
>>> p = pairs(coords, 5)
>>> from random import choice
>>> choice(p)
[(93, 36), (96, 40), 9336, 9640]
>>> choice(p)
[(9, 57), (13, 54), 957, 1354]
>>> choice(p)
[(46, 69), (46, 74), 4669, 4674]

私のマシンでは、 pairs(coords, 5)10,000 の座標ペアをチェックするのに 1.5 秒かかります (2,500 をチェックするのに 0.15 秒かかります)。

編集ia:スライスの列挙を補うために追加するのを忘れていましibた-修正されました。

于 2013-08-17T19:08:45.007 に答える
2

アルゴリズムの最も遅い部分は、x座標とy座標の個別の処理と斜辺の計算です。これらは両方とも、Python のネイティブの複素数型を使用して高速化できます。

>>> from itertools import starmap
>>> parray = list(starmap(complex, [(5, 1), (8.5, 3), (3.75, 4.25)]))
>>> a = parray[0]
>>> b = parray[1]
>>> a
(5+1j)
>>> b
(8.5+3j)
>>> a-b
(-3.5-2j)
>>> abs(a-b)
4.031128874149275
于 2013-08-18T00:42:14.013 に答える
1

処理を高速化する 1 つの方法は、ある種の空間インデックスを使用して、明らかに離れている検索ポイントを除外することです。役に立つかもしれないモジュールがあります: http://toblerity.org/rtree/ . http://en.wikipedia.org/wiki/R-treeも参照してください。

于 2013-08-17T19:03:37.817 に答える