تحويل مصفوفة ثنائية إلى ناقل آخر غير صفرية مؤشر بطريقة سريعة ، vectorized الأزياء

Question

لنفترض في MATLAB ، أن لدي مصفوفة ، ، عناصرها إما 0 أو 1.

كيف يمكنني الحصول على ناقلات مؤشر آخر غير الصفر عنصر من عناصر كل عمود في أسرع vectorized الطريقة ؟

يمكنني أن أفعل

[B, I] = max(cumsum(A));

واستخدام I, لكن هل هناك طريقة أسرع ؟ (أفترض cumsum تكلفة قليلا من الوقت حتى suming 0 و 1).

تحرير: أعتقد أنني vectorized حتى أكثر مما كنت في حاجة سريعة السيدFooz' حلقة كبيرة ولكن كل حلقة في مطلب يبدو أن تكلفة لي الكثير في التصحيح الوقت حتى لو كان سريع.

Answer 1

كما هو مبين من قبل السيد Fooz, بالنسبة الحلقات يمكن أن تكون سريعة جدا الآن مع أحدث إصدارات MATLAB.ومع ذلك, إذا كنت تريد حقا أن يكون الاتفاق vectorized رمز أقترح تحاول هذه:

[B,I] = max(flipud(A));
I = size(A,1)-I+1;

هذا هو أسرع من CUMSUM القائم على الإجابة, ولكن لا يزال تماما بأسرع السيد Fooz هي الخيارات حلقات.

اثنين إضافية من الأشياء في الاعتبار:

• ما هي النتائج التي كنت ترغب في الحصول على عمود يحتوي على أي منها في ذلك على الإطلاق ؟ مع الخيار أعلاه أعطيتك, أعتقد أنك سوف تحصل على مؤشر حجم(A,1) (أيعدد الصفوف في A) في مثل هذه الحالة.لديك الخيار, أعتقد أنك سوف تحصل على 1 في هذه الحالة ، في حين متداخلة-ل-حلقات خيار من السيد Fooz سوف تعطيك 0.

• السرعة النسبية من هذه الخيارات المختلفة من المرجح أن تختلف بناء على حجم A وعدد غير أصفار كنت أتوقع أن يكون.

Answer 2

سريع هو ما يجب أن تقلق بشأنه ، وليس بالضرورة كامل كمية موجهة.الإصدارات الأخيرة من Matlab هي كثيرا أكثر ذكاء حول التعامل مع الحلقات بكفاءة.إذا كان هناك اتفاق vectorized طريقة للتعبير عن شيء, انها عادة ما تكون أسرع ، ولكن الحلقات لا ينبغي (دائما) أن يخشى كما اعتادت أن تكون.

clc

A = rand(5000)>0.5;
A(1,find(sum(A,1)==0)) = 1; % make sure there is at least one match

% Slow because it is doing too much work
tic;[B,I1]=max(cumsum(A));toc

% Fast because FIND is fast and it runs the inner loop
tic;
I3=zeros(1,5000);
for i=1:5000
  I3(i) = find(A(:,i),1,'last');
end
toc;
assert(all(I1==I3));

% Even faster because the JIT in Matlab is smart enough now
tic;
I2=zeros(1,5000);
for i=1:5000
  I2(i) = 0;
  for j=5000:-1:1
    if A(j,i)
      I2(i) = j;
      break;
    end
  end
end
toc;
assert(all(I1==I2));

على R2008a, Windows, x64 ، cumsum نسخة يأخذ 0.9 ثانية.حلقة العثور على نسخة يأخذ 0.02 ثانية.حلقة مزدوجة النسخة ويأخذ مجرد 0.001 ثانية.

تحرير: واحد الذي هو أسرع يعتمد على البيانات الفعلية.المزدوج حلقة يأخذ 0.05 ثانية عند تغيير 0.5 إلى 0.999 (لأنه يأخذ وقتا أطول لتصل إلى كسر ؛ في المتوسط).cumsum حلقة&تجد التنفيذ يكون أكثر اتساقا سرعات.

تحرير 2: gnovice هو flipud حل ذكي.للأسف, على آلة الاختبار يستغرق 0.1 ثانية, حتى انها أسرع بكثير من cumsum ، لكن أبطأ من يحلق الإصدارات.