تسريع العمليات الحسابية مع المصفوفات نمباي

Question

ولقد اثنين من المصفوفات. تمتلئ مع كل من الآحاد والأصفار و. واحد هو واحد كبير (3000 x 2000 العناصر)، والآخر هو أصغر (20 × 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

ما يجري بطيئة بشكل مؤلم. أفعل أي شيء خطأ؟ هل هناك طريقة ذكية لجعل هذا العمل بشكل أسرع؟

وتحرير: أساسا أنا، لكل (س، ص) في مصفوفة كبيرة، والتحقق من كل بكسل من كلا مصفوفة كبيرة وصغيرة مصفوفة حول (س، ص) لمعرفة ما إذا كانوا 1. إذا كانت 1 ، ثم أنا وضعت تلك القيمة على newMatrix. أنا أفعل نوعا من الكشف عن التصادم.

Answer 1

وأستطيع أن أفكر في بضع تحقيق أمثلية هناك - كما كنت تستخدم 4 الثعبان متداخلة "ل" التصريحات، كنت على وشك بطيئة كما يمكن أن يكون.

وأنا لا يمكن معرفة بالضبط ما كنت أبحث عنه - ولكن لشيء واحد، إذا مصفوفة كبيرة بك الكثافة "1" ليالي منخفضة، يمكنك بالتأكيد استخدام "أي" وظيفة الثعبان على شرائح 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
        (...) 

وعند هذه النقطة، إذا كان لا يزال بحاجة إلى التفاعل على كل عنصر، يمكنك القيام زوج آخر من المؤشرات على المشي كل موقف داخل الخطوة - ولكن أعتقد أنك حصلت على فكرة

وبصرف النظر عن استخدام العمليات الرقمية الداخلية مثل هذا "أي" الاستخدام، ويمكن بالتأكيد إضافة بعض السيطرة كود تدفق لكسر قبالة حلقة (ب، أ) عندما تم العثور على أول بكسل مطابقة. (مثل، إدراج "كسر" بيان داخل الأخير الخاص بك "لو" وزوج if..break آخر لل"ب" حلقة.

وأنا حقا لا يمكن معرفة بالضبط ما هو القصد الخاص - لذلك لا استطيع ان اعطيكم رمز أكثر specifc.

Answer 2

ومثال التعليمة البرمجية الخاصة بك لا معنى له، ولكن وصف مشكلتك يبدو وكأنه كنت تحاول القيام التفاف 2D من bitarray صغيرة على bitarray كبيرة. هناك وظيفة convolve2d في حزمة scipy.signal أن يفعل هذا بالضبط. فقط لا 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

في الجهاز الخاص بي تشغيله في أقل من 9 ثانية ل3000x2000 كتبها 20X20 الإلتواء. إدارة الوقت يعتمد على عدد من تلك الموجودة في مجموعة صغيرة، ويجري 20ms لكل عنصر صفرية.

Answer 3

إذا معبأة بت الخاص بك حقا 8 لكل بايت / 32 في كثافة العمليات، ويمكنك الحد من smallMatrix ل20x16،
ثم حاول ما يلي، وهنا لصف واحد.
(newMatrix[x, y] = 1 عندما <م> أي بت من 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