2

Pythonの場合：lon、lat（500 000ポイント以上）の2つの配列があります。 

     lon = numpy.array()
     lat = numpy.array()

     flag = True
     while flag:
        lon1 = lon[:-1]
        lon2 = lon[1:]
        lat1 = lat[:-1]
        lat2 = lat[1:]

        '''distance'''
        x = (lon2 - lon1)
        y = (lat2 - lat1)
        d = numpy.sqrt(x * x + y * y)

        min = numpy.min(d)
        if min < 0.015:
            j = numpy.where(d == min)[0][0]

            lon[j] = (lon[j] + lon[j + 1]) / 2
            lat[j] = (lat[j] + lat[j + 1]) / 2

            lon = numpy.delete(lon, j + 1)
            lat = numpy.delete(lat, j + 1)

        else:
            flag = False

このコードは非常にゆっくりと動作します！

  1. プロンプトを表示してください、コードをより速く実行するにはどうすればよいですか？

  2. scipy.weaveがあることは知っています。プロンプトを表示してください、scipy.weaveを使用してコードを変更する方法は？

    import scipy
from scipy import weave

codeC = """
???
"""
scipy.weave.inline(codeC, ['lon', 'lat'], compiler='gcc')

ありがとう。

アップデート：

    lon1 = lon[:-1]
    lon2 = lon[1:]
    lat1 = lat[:-1]
    lat2 = lat[1:]

    x = (lon2 - lon1)
    y = (lat2 - lat1)
    d = x * x + y * y

    while True and d.size > 1:

        j = np.argmin(d)
        if d[j] > min_radius:
            break

        lon[j] = (lon[j] + lon[j + 1]) / 2
        lat[j] = (lat[j] + lat[j + 1]) / 2

        '''lon = np.delete(lon, j + 1)
           lat = np.delete(lat, j + 1)
           d = np.delete(d, j)'''
        if j == (d.size - 1):
            lon = lon[:j + 1]
            lat = lat[:j + 1]
            d = d[:j]
        else:
            lon = np.hstack((lon[:j + 1], lon[j + 2:]))
            lat = np.hstack((lat[:j + 1], lat[j + 2:]))
            d = np.hstack((d[:j], d[j + 1:]))


        if j > 0:
            x = lon[j] - lon[j - 1]
            y = lat[j] - lat[j - 1]
            d[j - 1] = x * x + y * y
        if j < (d.size - 1):
            x = lon[j + 1] - lon[j]
            y = lat[j + 1] - lat[j]
            d[j] = x * x + y * y

@ ilmiacs、@ Jaime、@ Luke、ありがとう！それははるかに速く動作します！

しかし、全体として、コードは500ポイントの配列で非常に長く機能します...：（（（

4

1 に答える 1

5

ループ内の各反復で、コストのかかる計算全体をやり直しています。1回の反復で1つのノードのみが削除され、1つの要素を削除するときに、配列全体をコピーして距離の計算をやり直します。次に、次のノードを検索します。

したがって、コードは少なくとも実行されるため、最適ではありませんO(N^2)。しかし、あなたが達成したいこと、 O(N log N)またはおそらくO(N)十分であろうことのために。

アルゴリズムを再配置すれば、numpyのない単純なPythonモジュールは十分に高速であるはずです。レシピ：

  1. 距離配列全体を再計算することは避けてください。1つのノードを削除するときに、再計算する必要があるのは2つの値だけです。
  2. コピーは避けてください。それも高価です。

お役に立てれば。

編集：

距離配列を再計算しない実装例は次のとおりです。

lon = numpy.array()
lat = numpy.array()

lon1 = lon[:-1]
lon2 = lon[1:]
lat1 = lat[:-1]
lat2 = lat[1:]

'''distance'''
x = (lon2 - lon1)
y = (lat2 - lat1)
d = x * x + y * y

while True:
    min = numpy.min(d)
    if min < 0.015 * 0.015:
        j = numpy.where(d == min)[0][0]
    else:
        break

    lon[j] = (lon[j] + lon[j + 1]) / 2
    lat[j] = (lat[j] + lat[j + 1]) / 2

    lon = numpy.delete(lon, j + 1)  # <-- you spend most of the time here
    lat = numpy.delete(lat, j + 1)  # <-- and here

    d = numpy.delete(d, j)      # <-- and here

    x = lon[j]-lon[j-1]
    y = lat[j]-lat[j-1]
    d[j-1] = x * x + y * y
    x = lon[j+1]-lon[j]
    y = lat[j+1]-lat[j]
    d[j] = x * x + y * y

これはあなたに後押しを与えるでしょうがO(N^2)、広範囲にわたるコピーのために、あなたはまだです。これを回避するには、配列を二重リンクリストに格納する必要があります。次に、要素を削除すると、O(1)ではなく、になりますO(N)。リンクリストを使用すると、最悪の操作は最小値の検索になります。これは、のソートされたバージョンを導入することで改善できますd。ここで、の位置も追跡しdます。ただし、変更を追跡する必要があります。しかし、最終的には、であるアルゴリズムに到達しますO(N log N)。

編集2：

@Jaimeが指摘しているように、距離の2乗を比較する必要もありません。上記のコードを修正しました。

編集3：

週末の間、私はアルゴリズムについてもっと考えていました。それは非常に興味深い問題であり、考えるのが楽しいことがわかりました。私は自分の考えを共有したかった。

それを機能させることO(N log N)は、私が思っていたほど簡単ではありません。私はリストを保持し、sorted_dそれを管理することを提案しました。リンクが削除されるたびに、の2つのエントリを更新する必要がありますsorted_d。つまり、で2つの対応する距離の新しい位置を見つける必要がありますsorted_d。通常のリストでは、位置を見つけることはの二分法によって行うことができますO(log N)。しかし、私が理解している限り、二等分線はリンクリストでは実行可能ではなく、ターンしO(N)ます。これが問題です。誰かが私が間違っていることを証明し、のソートされたリンクリストに要素を挿入する方法を示してくれたら嬉しいですO(log N)。個人的には見えません。

sorted_dただし、のリンクリストに代わるものがあります。必要なのは、フロートをキーとして機能するBツリーまたはパトリシアツリーだけです。このようなツリーへの挿入は、（非常に高速）'O（log N）`で実行できます。しかし、私はそのようなツリーの標準的な実装を知りません。標準の実装は、文字列または整数で機能します。したがって、floatからintへの順序付けられた衝突のないマッピングがあれば、それを達成できます。このようなマッピングは一般的には存在しませんが、特定のデータセットに対して構築されることは間違いありません。そして、問題のデータセットは間違いなく特定のものです。確かに上限と精度があります。

お役に立てれば。さらに興味があれば、この問題の最適なデータ構造についての私の考えを提示することもできます。

于 2013-01-11T14:37:03.917 に答える