7

私はそのboardようないくつかのnumpy配列を持っています:

array([[0, 0, 0, 1, 0, 0, 0, 0],
       [1, 0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 0, 1],
       [0, 1, 0, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 1],
       [0, 0, 0, 0, 1, 0, 0, 0],
       [0, 0, 1, 0, 0, 0, 1, 0],
       [1, 0, 0, 0, 0, 1, 0, 0]])

そして、次のコードを使用して、ボードの -7 から 8 までの n 番目の対角線 (およびそのミラー バージョン) の要素の合計を見つけます。

n = 8
rate = [b.diagonal(i).sum()
        for b in (board, board[::-1])
        for i in range(-n+1, n)]

いくつかのプロファイリングの後、この操作は全体の実行時間の約 2/3 を占めています。これは次の 2 つの要因によるものと思われます。

  • この.diagonalメソッドは、ビューの代わりに新しい配列を作成します (numpy 1.7 には.diagそれを解決する新しいメソッドがあるようです)
  • 反復は、リスト内包表記内の python で行われます

それで、これらの合計をより速く見つける方法はありますか（おそらくnumpyのCレイヤーで）？

さらにいくつかのテストを行った後、この操作をキャッシュすることで合計時間を 7.5 倍短縮できました... 間違ったボトルネックを探していたのでしょうか?

もう一つ：

.trace物を置き換える方法を見つけたところdiagonal(i).sum()...パフォーマンスはあまり改善されませんでした（約2〜4％）。

したがって、問題は理解力であるべきです。何か案は？

4

2 に答える 2

7

を使用した解決策がありstride_tricksます。これは、この質問への回答で利用可能な大量の情報に部分的に基づいていますが、問題は重複とは見なされないほど十分に異なっていると思います. 正方行列に適用された基本的な考え方は次のとおりです。より一般的なソリューションを実装する関数については、以下を参照してください。

>>> cols = 8
>>> a = numpy.arange(cols * cols).reshape((cols, cols))
>>> fill = numpy.zeros((cols - 1) * cols, dtype='i8').reshape((cols - 1, cols))
>>> stacked = numpy.vstack((a, fill, a))
>>> major_stride, minor_stride = stacked.strides
>>> strides = major_stride, minor_stride * (cols + 1)
>>> shape = (cols * 2 - 1, cols)
>>> numpy.lib.stride_tricks.as_strided(stacked, shape, strides)
array([[ 0,  9, 18, 27, 36, 45, 54, 63],
       [ 8, 17, 26, 35, 44, 53, 62,  0],
       [16, 25, 34, 43, 52, 61,  0,  0],
       [24, 33, 42, 51, 60,  0,  0,  0],
       [32, 41, 50, 59,  0,  0,  0,  0],
       [40, 49, 58,  0,  0,  0,  0,  0],
       [48, 57,  0,  0,  0,  0,  0,  0],
       [56,  0,  0,  0,  0,  0,  0,  0],
       [ 0,  0,  0,  0,  0,  0,  0,  7],
       [ 0,  0,  0,  0,  0,  0,  6, 15],
       [ 0,  0,  0,  0,  0,  5, 14, 23],
       [ 0,  0,  0,  0,  4, 13, 22, 31],
       [ 0,  0,  0,  3, 12, 21, 30, 39],
       [ 0,  0,  2, 11, 20, 29, 38, 47],
       [ 0,  1, 10, 19, 28, 37, 46, 55]])
>>> diags = numpy.lib.stride_tricks.as_strided(stacked, shape, strides)
>>> diags.sum(axis=1)
array([252, 245, 231, 210, 182, 147, 105,  56,   7,  21,  42,  70, 105,
       147, 196])

もちろん、これが実際にどれだけ速いかはわかりません。しかし、Python のリスト内包表記よりも速いに違いありません。

便宜上、ここでは完全に一般的なdiagonals関数を示します。対角線を最長の軸に沿って移動すると仮定します。

def diagonals(a):
    rows, cols = a.shape
    if cols > rows:
        a = a.T
        rows, cols = a.shape
    fill = numpy.zeros(((cols - 1), cols), dtype=a.dtype)
    stacked = numpy.vstack((a, fill, a))
    major_stride, minor_stride = stacked.strides
    strides = major_stride, minor_stride * (cols + 1)
    shape = (rows + cols - 1, cols)
    return numpy.lib.stride_tricks.as_strided(stacked, shape, strides)
于 2012-05-29T23:31:05.513 に答える
2

コメントに投稿したように、C コードには触れません。

PyPyを試してみてください。実際にはnumpyのサポートは静かで良いです（ただし、直接array.diagonalをサポートしていません）-そのための他のbuidinメソッドがあるかどうかは確認しませんでした。神経質になって、次のコードを試しました。 

try:
    import numpypy  # required by PyPy
except ImportError:
    pass
import numpy

board = numpy.array([[0, 0, 0, 1, 0, 0, 0, 0],
       [1, 0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 0, 1],
       [0, 1, 0, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 1],
       [0, 0, 0, 0, 1, 0, 0, 0],
       [0, 0, 1, 0, 0, 0, 1, 0],
       [1, 0, 0, 0, 0, 1, 0, 0]])

n=len(board)
def diag_sum(i, b):
    s = 0
    if i>=0:
        row = 0
        end = n
    else:
        row = -i
        end = n+i
        i = 0
    while i<end:
        s += b[row, i]
        i+=1
        row+=1
    return s


import time
t=time.time()
for i in xrange(50000):
    # rate = [b.diagonal(i).sum()
    #         for b in (board, board[::-1])
    #         for i in range(-n+1, n)]

    rate = [diag_sum(i,b)
            for b in (board, board[::-1])
            for i in range(-n+1, n)]

print time.time() - t

結果は次のとおりです。

  • 0.64 秒の PyPydiag_sum
  • 6.01s CPython バージョンdiag_sum
  • 5.60s CPython バージョンb.diagonal
于 2012-05-29T10:30:06.460 に答える