numpy行列を使用した計算の高速化

Question

2つの行列があります。両方ともゼロと1で埋められます。 1つは大きな要素（3000 x 2000要素）で、もう1つは小さな要素（20 x 20）要素です。私は次のようなことをしています：

newMatrix = (size of bigMatrix), filled with zeros
l = (a constant)

for y in xrange(0, len(bigMatrix[0])):
    for x in xrange(0, len(bigMatrix)):

        for b in xrange(0, len(smallMatrix[0])):
            for a in xrange(0, len(smallMatrix)):

                if (bigMatrix[x, y] == smallMatrix[x + a - l, y + b - l]):
                    newMatrix[x, y] = 1

これは非常に遅いです。私は何か間違っていますか？この作業を高速化するスマートな方法はありますか？

編集：基本的に、私は大きな行列の各（x、y）について、（x、y）の周りの大きな行列と小さな行列のすべてのピクセルをチェックして、それらが1かどうかを確認します。 、その値をnewMatrixに設定します。ある種の衝突検出を行っています。

Answer 1

そこで最適化がいくつか考えられます- 4つのネストされたpython＆quot; for＆quot;を使用しているため、ステートメント、あなたはできる限り遅くなっています。

探しているものが正確にわからない- ただし、1つには、大きな行列の「1」の密度が低い場合、Pythonの「任意」を使用できます。 bigMtarixのスライスで機能して、そこに設定された要素があるかどうかをすばやく確認します-そこに数倍の速度向上が得られます：

step = len(smallMatrix[0])
for y in xrange(0, len(bigMatrix[0], step)):
    for x in xrange(0, len(bigMatrix), step):
        if not any(bigMatrix[x: x+step, y: y + step]):
            continue
        (...) 

この時点で、まだ各要素で対話する必要がある場合は、別のインデックスのペアを実行して、ステップ内の各位置をウォークします-しかし、あなたはそのアイデアを得たと思います。

このような「任意」のような内部の数値演算の使用は別として、使用法では、最初に一致するピクセルが見つかったときに（b、a）ループを中断するための制御フローコードを確実に追加できます。 （たとえば、最後の＆quot; if＆quot;と＆quot; b＆quot;ループの別のif..breakペア内に＆quot; break＆quot;ステートメントを挿入します。

私は本当にあなたの意図が何であるかを正確に理解することはできません-そのため、より具体的なコードを提供することはできません。

Answer 2

サンプルコードは意味をなしませんが、問題の説明は、小さなビット配列を大きなビット配列に2次元畳み込みしようとしているように聞こえます。これを行うscipy.signalパッケージにはconvolve2d関数があります。結果を取得するには、 convolve2d（bigMatrix、smallMatrix）を実行します。残念ながら、scipyの実装にはブール配列の特別なケースがないため、完全な畳み込みはかなり遅いです。配列には1と0しか含まれていないという事実を利用する関数を次に示します。

import numpy as np

def sparse_convolve_of_bools(a, b):
    if a.size < b.size:
        a, b = b, a
    offsets = zip(*np.nonzero(b))
    n = len(offsets)
    dtype = np.byte if n < 128 else np.short if n < 32768 else np.int
    result = np.zeros(np.array(a.shape) + b.shape - (1,1), dtype=dtype)
    for o in offsets:
        result[o[0]:o[0] + a.shape[0], o[1]:o[1] + a.shape[1]] += a
    return result

私のマシンでは、3000x2000 x 20x20の畳み込みで9秒未満で実行されます。実行時間は、小さな配列内の1の数に依存し、ゼロ以外の要素ごとに20ミリ秒です。

Answer 3

ビットが実際にバイトごとに8個/ intごとに32個パックされている場合、 また、smallMatrixを20x16に減らすことができます。
次に、ここで単一の行について以下を試してください。
（ newMatrix [x、y] = 1 x、yの周りの20x16の任意のビットが1の場合?? あなたは本当に何を探していますか？）

python -m timeit -s '
""" slide 16-bit mask across 32-bit pairs bits[j], bits[j+1] """

import numpy as np

bits = np.zeros( 2000 // 16, np.uint16 )  # 2000 bits
bits[::8] = 1
mask = 32+16
nhit = 16 * [0]

def hit16( bits, mask, nhit ):
    """
        slide 16-bit mask across 32-bit pairs bits[j], bits[j+1]
        bits: long np.array( uint16 )
        mask: 16 bits, int
        out: nhit[j] += 1 where pair & mask != 0
    """
    left = bits[0]
    for b in bits[1:]:
        pair = (left << 16) | b
        if pair:  # np idiom for non-0 words ?
            m = mask
            for j in range(16):
                if pair & m:
                    nhit[j] += 1
                    # hitposition = jb*16 + j
                m <<= 1
        left = b
    # if any(nhit):  print "hit16:", nhit

' \
'
hit16( bits, mask, nhit )
'

# 15 msec per loop, bits[::4] = 1
# 11 msec per loop, bits[::8] = 1
# mac g4 ppc