17

私は、約20,000の緯度、経度座標のリストを循環し、各点から基準点までの距離を計算する、非常に単純なpythonルーチンを持っています。 

def compute_nearest_points( lat, lon, nPoints=5 ):
    """Find the nearest N points, given the input coordinates."""

    points = session.query(PointIndex).all()
    oldNearest = []
    newNearest = []
    for n in xrange(nPoints):
        oldNearest.append(PointDistance(None,None,None,99999.0,99999.0))
        newNearest.append(obj2)

    #This is almost certainly an inappropriate use of deepcopy
    #  but how SHOULD I be doing this?!?!
    for point in points:
        distance = compute_spherical_law_of_cosines( lat, lon, point.avg_lat, point.avg_lon )
        k = 0
        for p in oldNearest:
            if distance < p.distance:
                newNearest[k] = PointDistance(
                    point.point, point.kana, point.english, point.avg_lat, point.avg_lon, distance=distance
                    )
                break
            else:
                newNearest[k] = deepcopy(oldNearest[k])
            k += 1
        for j in range(k,nPoints-1):
            newNearest[j+1] = deepcopy(oldNearest[j])
        oldNearest = deepcopy(newNearest)

    #We're done, now print the result
    for point in oldNearest:
        print point.station, point.english, point.distance

    return

私は当初、まったく同じアプローチを使用してこれを C で作成しました。そこでは問題なく動作し、nPoints<=100 の場合は基本的に瞬時です。SqlAlchemy を使って他のことをしたかったので、Python に移植することにしました。

私は最初にメソッドをペッパーするディープコピーステートメントなしでそれを移植しました。これにより、結果が「奇妙」または部分的に正しくなくなりました。それでも、C バージョンとほぼ同じ速さでした。

deepcopy 呼び出しが追加されたので、ルーチンは正しく機能しますが、極端にパフォーマンスが低下し、同じ機能を実行するのに数秒かかります。

これはかなり一般的な仕事のように思えますが、私は明らかに Pythonic の方法でそれを行っていません。正しい結果が得られるが、どこにでもディープコピーを含める必要がないようにするには、どうすればよいですか?

編集:
私ははるかにシンプルで高速なソリューションを見つけました。

def compute_nearest_points2( lat, lon, nPoints=5 ):
    """Find the nearest N points, given the input coordinates."""

    points = session.query(PointIndex).all()
    nearest = []

    for point in points:
        distance = compute_spherical_law_of_cosines( lat, lon, point.avg_lat, point.avg_lon )
        nearest.append( 
            PointDistance(
                point.point, point.kana, point.english, point.avg_lat, point.avg_lon, distance=distance
                )
            )

    nearest_points = sorted(nearest, key=lambda point: point.distance)[:nPoints]     
    for item in nearest_points:
        print item.point, item.english, item.distance
    return

したがって、基本的には、入力の完全なコピーを作成し、新しい値 (基準点からの距離) を追加するだけです。次に、結果のリストに「sorted」を適用し、ソート キーが PointDistance オブジェクトの距離プロパティになるように指定します。

理由はよくわかりませんが、これは deepcopy を使用するよりもはるかに高速です。私はそれが効率的な C 実装の python の「ソート済み」にかかっていると思いますか?

4

2 に答える 2

36

わかりました、最初に最も簡単なこと：

  1. deepcopy正常な方法で自分自身を含むオブジェクトのような病理学的なケースをコピーするために多くの内部簿記を行う必要があるため、一般的に遅いです。たとえば、このページを参照するか、Python パスのどこかにあるdeepcopyのソース コードを見てください。copy.py

  2. sortedC で実装されているため、高速です。Python の同等の並べ替えよりもはるかに高速です。

さて、コメントで尋ねたように、Pythonの参照カウント動作についてもう少し。Python では、変数は参照です。というときは、それ自体がオブジェクトとして存在し、それにタグが付けられているだけだと考えてくださいa=1。C などの他の言語では、変数は (タグではなく) コンテナーであり、 を実行するときは、実際には 1 を に入れます。これは、変数が参照である Python には当てはまりません。これにはいくつかの興味深い結果があり、あなたも偶然見つけたかもしれません:1aa=1a

>>> a = []      # construct a new list, attach a tag named "a" to it
>>> b = a       # attach a tag named "b" to the object which is tagged by "a"
>>> a.append(1) # append 1 to the list tagged by "a"
>>> print b     # print the list tagged by "b"
[1]

リストは可変オブジェクトであるため、この動作が見られます。リストを作成した後にリストを変更でき、リストを参照する変数のいずれかを介してリストにアクセスすると、変更が見られます。リストの不変の等価物はタプルです:

>>> a = ()      # construct a new tuple, attach a tag named "a" to it
>>> b = a       # now "b" refers to the same empty tuple as "a"
>>> a += (1, 2) # appending some elements to the tuple
>>> print b
()

ここで、によって参照される既存のタプルから新しいa += (1, 2)タプルを作成し、オンザフライで構築された別のタプルを作成し、新しいタプルを指すように調整しますが、もちろんまだ古いタプルを参照します。のような単純な数値加算でも同じことが起こります: この場合、もともと が指していた数値はまったく変更されておらず、Python は新しい数値を「構築」し、新しい数値を指すように移動します。つまり、一言で言えば、数値、文字列、およびタプルは不変です。リスト、ディクテーション、およびセットは変更可能です。内部状態を変更できないことを明示的に保証しない限り、ユーザー定義クラスは一般に変更可能です。そして、不変のセットである があります。もちろん、他にもたくさんあります:)a(1, 2)aba = a+2aafrozenset

元のコードが機能しなかった理由はわかりませんが、PointDistanceクラスもデフォルトで変更可能であるため、リストで示したコード スニペットに関連する動作に遭遇した可能性があります。代替手段は、フィールドに名前でアクセスできるタプルのようなオブジェクトを構築するnamedtuplefrom のクラスである可能性があります。collectionsたとえば、次のようにすることもできます。

from collections import namedtuple
PointDistance = namedtuple("PointDistance", "point distance")

これにより、 と の 2 つの名前付きフィールドを持つクラスが作成さPointDistanceれます。メインループでは、これらを適切に割り当てることができます。フィールドが指すポイント オブジェクトはループの過程で変更されず、数値 (定義上、不変) であるため、この方法で安全に実行できるはずです。しかし、はい、一般的には、C で実装されているため、単純に使用する方が速いようです。また、通常の Python リストに基づくヒープ データ構造を実装するモジュールで幸運かもしれません。したがって、トップ要素を簡単に見つけることができます。他のものを並べ替える必要はありません。ただし、Pythonでも実装されているため、可能性としてはpointdistanceforpointfordistancesortedsortedheapqkheapqsortedたくさんのポイントを持っていない限り、より効果的です。

最後に、これまで使用する必要がなかったことを付け加えたいと思いますdeepcopyので、ほとんどの場合、それを回避する方法があると思います.

于 2010-06-15T09:26:44.770 に答える
6

これはあなたの質問に直接対処するものではないことを理解しています（そしてこれは古い質問であることを私は知っています）が、パフォーマンスについての議論があるので、append操作を見る価値があるかもしれません。アレイの「事前割り当て」を検討することをお勧めします。例えば：

array = [None] * num_elements
for i in range(num_elements):
    array[i] = True

対：

array = []
for i in range(num_elements):
    array.append(True)

これらの2つのメソッドを単純timeitに実行すると、中程度の値の配列でも事前に割り当てた場合、25％の改善が見られますnum_elements。

于 2012-12-05T16:15:30.490 に答える