Numpy Matrices로 계산 속도를 높이십시오

Question

나는 두 개의 행렬이 있습니다. 둘 다 0으로 가득 차 있습니다. 하나는 큰 하나 (3000 x 2000 요소)이고 다른 하나는 더 작은 (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)에 대해 큰 매트릭스와 작은 매트릭스의 모든 픽셀을 확인하여 1인지 확인합니다. Newmatrix에서 해당 값을 설정하십시오. 나는 일종의 충돌 감지를하고 있습니다.

Answer 1

나는 거기에서 몇 가지 최적화를 생각할 수 있습니다. 당신은 "문장에 4 개의 중첩 된 파이썬을 사용하고 있기 때문에 당신은 가능한 한 느리게 진행됩니다.

나는 당신이 찾고있는 것을 정확히 알 수 없습니다. 그러나 한 가지에 대해, 당신의 큰 매트릭스 "1"s 밀도가 낮 으면, 당신은 확실히 Bigmtarix의 슬라이스에서 Python의 "모든"기능을 사용하여 세트가 있는지 신속하게 확인할 수 있습니다. 요소-당신은 거기서 몇 배 속도를 높일 수 있습니다.

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) 루프를 분류하기 위해 일부 제어 흐름 코드를 추가 할 수 있습니다. (예 : 마지막 "if"내부에 "break"문을 삽입하고 "B"루프의 다른 if..break 쌍.

나는 당신의 의도가 무엇인지 정확히 알 수 없습니다. 그래서 나는 당신에게 더 많은 지정된 코드를 줄 수 없습니다.

Answer 2

예제 코드는 말이되지 않지만 문제에 대한 설명은 큰 비트가 위로 작은 비트가 송환을 시도하는 것처럼 들립니다. Scipy.signal 패키지에는 정확히이를 수행하는 Convolve2D 기능이 있습니다. 그냥 해 convolve2d(bigMatrix, smallMatrix) 결과를 얻으려면. 불행히도 Scipy 구현에는 부울 어레이에 대한 특별한 사례가 없으므로 전체 컨볼 루션이 느리게 느립니다. 다음은 배열에 배열이 포함되어 있다는 사실을 활용하는 기능입니다.

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 ~ 20x20 컨볼 루션의 경우 9 초 이내에 실행됩니다. 실행 시간은 더 작은 배열의 수에 따라 달라지며, 각각의 0이 아닌 요소 당 20ms입니다.

Answer 3

비트가 실제로 int 당 바이트 당 8 개 / 32로 포장되어 있으면 SmallMatrix를 20x16으로 줄일 수 있습니다.
그런 다음 여기에서 한 줄에 대해 다음을 시도하십시오.
(newMatrix[x, y] = 1 언제 어느 x 주위에 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