16

NumPyとベクトル化操作を使用して、コードのセクションをより高速に実行しようとしています。ただし、このコードをベクトル化する方法について誤解しているようです（おそらく、ベクトル化の理解が不完全なためです）。

ループを使用した作業コードは次のとおりです（AとBは、設定されたサイズの2D配列であり、すでに初期化されています）。

for k in range(num_v):
    B[:] = A[:]
    for i in range(num_v):
        for j in range(num_v):
            A[i][j] = min(B[i][j], B[i][k] + B[k][j])
return A

そして、これが上記のコードをベクトル化する私の試みです：

for k in range(num_v):
    B = numpy.copy(A)
    A = numpy.minimum(B, B[:,k] + B[k,:])
return A

これらをテストするために、私は以下を使用し、上記のコードを「アルゴリズム」と呼ばれる関数でラップしました。

def setup_array(edges, num_v):
    r = range(1, num_v + 1)
    A = [[None for x in r] for y in r]  # or (numpy.ones((num_v, num_v)) * 1e10) for numpy
    for i in r:
        for j in r:
            val = 1e10
            if i == j:
                val = 0 
            elif (i,j) in edges:
                val = edges[(i,j)]
            A[i-1][j-1] = val 
    return A

A = setup_array({(1, 2): 2, (6, 4): 1, (3, 2): -3, (1, 3): 5, (3, 6): 5, (4, 5): 2, (3, 1): 4, (4, 3): 8, (3, 4): 6, (2, 4): -4, (6, 5): -5}, 6) 
B = []
algorithm(A, B, 6)

期待される結果、および最初のコードで得られるものは次のとおりです。

[[0, 2, 5, -2, 0, 10] 
 [8, 0, 4, -4, -2, 9]
 [4, -3, 0, -7, -5, 5]
 [12, 5, 8, 0, 2, 13]
 [10000000000.0, 9999999997.0, 10000000000.0, 9999999993.0, 0, 10000000000.0]
 [13, 6, 9, 1, -5, 0]]

代わりに、2番目の（ベクトル化された）関数は次を返します。

[[ 0. -4.  0.  0.  0.  0.]
 [ 0. -4.  0. -4.  0.  0.]
 [ 0. -4.  0.  0.  0.  0.]
 [ 0. -4.  0.  0.  0.  0.]
 [ 0. -4.  0.  0.  0.  0.]
 [ 0. -4.  0.  0. -5.  0.]]

私は何が欠けていますか？

4

2 に答える 2

16

通常、実行速度が遅すぎると思われるため、コードをベクトル化する必要があります。
コードが遅すぎる場合は、適切なインデックス作成により高速になると言えます。
代わりにA[i][j]書く必要がありますA[i, j]-これは（サブ）配列の一時的なコピーを回避します。
これはコードの最も内側のループで行うため、非常にコストがかかる可能性があります。

ここを見て：

In [37]: timeit test[2][2]
1000000 loops, best of 3: 1.5 us per loop

In [38]: timeit test[2,2]
1000000 loops, best of 3: 639 ns per loop

あなたのコードでこれを一貫して行ってください-私はそれがすでにあなたのパフォーマンスの問題を解決すると強く信じています！

そうは言っても...

...これがベクトル化する方法についての私の見解です

for k in range(num_v):
    numpy.minimum(A, np.add.outer(A[:,k], A[k,:]), A)
return A

numpy.minimumは、2つの配列を比較し、2つの要素のうち小さい方を要素ごとに返します。3番目の引数を渡すと、出力が取得されます。これが入力配列の場合、操作全体が実行されます。

Peter de Rivayが説明しているように、ブロードキャストのソリューションには問題がありますが、数学的には、2つのベクトルを追加することによるある種の外積です。したがって、add関数で外部操作を使用できます。

NumPyのバイナリufuncには、reduce、accumulate、sum、outerなどの特定の種類の特別なベクトル化された操作を実行するための特別なメソッドがあります。

于 2013-01-21T21:41:34.383 に答える
12

この問題は、次の回線でのアレイブロードキャストが原因で発生します。

A = numpy.minimum(B, B[:,k] + B[k,:])

Bはサイズ6x6、B [：、k]は6要素の配列、B [k、：]は6要素の配列です。

（numpy配列型を使用しているため、B [：、k]とB [k、：]の両方が形状Nのランク1配列を返します）

Numpyは、それに合わせてサイズを自動的に変更します。

  1. 最初にB[：、k]がB [k、：]に追加され、6つの要素を持つ中間配列の結果が作成されます。（これはあなたが意図したものではありません）
  2. 次に、この6要素の配列は、行を繰り返すことによって6x6のマトリックスにブロードキャストされます。
  3. 3番目に、元の行列とこのブロードキャスト行列の最小値が計算されます。

これは、numpyコードが次のものと同等であることを意味します。

for k in range(num_v):
   B[:] = A[:]
   C=[B[i][k]+B[k][i] for i in range(num_v)]
   for i in range(num_v):
      for j in range(num_v):
         A[i][j] = min(B[i][j], C[j])

コードを修正する最も簡単な方法は、配列型の代わりに行列型を使用することです。

A = numpy.matrix(A)
for k in range(num_v):
    A = numpy.minimum(A, A[:,k] + A[k,:])

マトリックスタイプはより厳密なブロードキャストルールを使用するため、この場合は次のようになります。

  1. A [：、k]は、列を繰り返すことによって6x6の行列に拡張されます
  2. A [k、：]は、行を繰り返すことによって6x6の行列に拡張されます
  3. ブロードキャストされたマトリックスが加算されて、6x6のマトリックスが作成されます。
  4. 最小値が適用されます
于 2013-01-21T22:33:58.853 に答える