كرر نسخ من عناصر المصفوفة: فك تشفير الطول في ماتلاب

Question

أحاول إدراج قيم متعددة في صفيف باستخدام صفيف "قيم" وصفيف "عداد". على سبيل المثال ، إذا:

a=[1,3,2,5]
b=[2,2,1,3]

أريد إخراج بعض الوظائف

c=somefunction(a,b)

أن تكون

c=[1,1,3,3,2,5,5,5]

حيث تتكرر A (1) B (1) عدد المرات ، A (2) تتكرر B (2) مرات ، إلخ ...

هل هناك وظيفة مدمجة في MATLAB تفعل ذلك؟ أود تجنب استخدام حلقة إذا أمكن. لقد جربت اختلافات من "repmat ()" و "kron ()" دون جدوى.

هذا أساسا Run-length encoding.

Answer 1

عرض المشكلة

لدينا مجموعة من القيم ، vals و Runlifts ، runlens:

vals     = [1,3,2,5]
runlens  = [2,2,1,3]

نحن بحاجة لتكرار كل عنصر في vals مرات كل عنصر مقابل في runlens. وبالتالي ، سيكون الناتج النهائي:

output = [1,1,3,3,2,5,5,5]

نهج محتمل

واحدة من أسرع الأدوات مع MATLAB cumsum وهو مفيد للغاية عند التعامل مع المشكلات الخلفية التي تعمل على أنماط غير منتظمة. في المشكلة المذكورة ، تأتي المخالفات مع العناصر المختلفة في runlens.

الآن ، للاستغلال cumsum, ، نحن بحاجة إلى القيام شيئين هنا: تهيئة مجموعة من zeros ووضع القيم "المناسبة" في مواضع "مفتاح" على صفيف الأصفار ، وذلك بعد "cumsum"يتم تطبيقه ، سننتهي بمجموعة نهائية من المتكررة vals من runlens مرات.

خطوات: دعنا نرسم الخطوات المذكورة أعلاه لإعطاء النهج المحتمل منظورًا أسهل:

1) تهيئة صفيف الأصفار: ما الذي يجب أن يكون الطول؟ لأننا نكرر runlens مرات ، يجب أن يكون طول صفيف الأصفار هو تلخيص الجميع runlens.

2) ابحث عن المواضع/المؤشرات الرئيسية: الآن هذه المواضع الرئيسية هي أماكن على طول مجموعة الأصفار حيث كل عنصر من العنصر vals ابدأ في التكرار. وهكذا ، ل runlens = [2,2,1,3], ، ستكون المواقف الرئيسية المعينة على صفيف الأصفار:

[X 0 X 0 X X 0 0] % where X's are those key positions.

3) ابحث cumsum سيكون لوضع القيم "المناسبة" في هذه المواقف الرئيسية. الآن ، لأننا سنفعل cumsum بعد فترة وجيزة ، إذا كنت تفكر عن كثب ، فستحتاج إلى ملف differentiated نسخة من values مع diff, ، لهذا السبب cumsum على هؤلاء سوف أعدنا values. نظرًا لأن هذه القيم المتمايزة سيتم وضعها على صفيف الأصفار في أماكن مفصولة runlens المسافات ، بعد الاستخدام cumsum سيكون لدينا كل vals العنصر المتكرر runlens مرات كما الناتج النهائي.

رمز الحل

إليك التنفيذ الذي يربط جميع الخطوات المذكورة أعلاه -

% Calculate cumsumed values of runLengths. 
% We would need this to initialize zeros array and find key positions later on.
clens = cumsum(runlens)

% Initalize zeros array
array = zeros(1,(clens(end)))

% Find key positions/indices
key_pos = [1 clens(1:end-1)+1]

% Find appropriate values
app_vals = diff([0 vals])

% Map app_values at key_pos on array
array(pos) = app_vals

% cumsum array for final output
output = cumsum(array)

اختراق ما قبل التخصيص

كما يمكن أن نرى أن الكود المدرج أعلاه يستخدم التخصيص المسبق مع الأصفار. الآن ، وفقا لهذا مدونة MATLAB غير الموثقة على التخصيص المسبق بشكل أسرع, ، يمكن للمرء أن يحقق مسبقًا أسرع بكثير مع -

array(clens(end)) = 0; % instead of array = zeros(1,(clens(end)))

الاختتام: رمز الوظيفة

لإنهاء كل شيء ، سيكون لدينا رمز وظيفة مدمجة لتحقيق فك تشفير طول الجري مثل SO -

function out = rle_cumsum_diff(vals,runlens)
clens = cumsum(runlens);
idx(clens(end))=0;
idx([1 clens(1:end-1)+1]) = diff([0 vals]);
out = cumsum(idx);
return;

المرجعية

رمز القياس

المدرجة التالية هي رمز القياس لمقارنة أوقات التشغيل وسرعاتها المذكورة cumsum+diff النهج في هذا المنشور على آخر cumsum-only النهج القائم على MATLAB 2014B-

datasizes = [reshape(linspace(10,70,4).'*10.^(0:4),1,[]) 10^6 2*10^6]; %
fcns = {'rld_cumsum','rld_cumsum_diff'}; % approaches to be benchmarked

for k1 = 1:numel(datasizes)
    n = datasizes(k1); % Create random inputs
    vals = randi(200,1,n);
    runs = [5000 randi(200,1,n-1)]; % 5000 acts as an aberration
    for k2 = 1:numel(fcns) % Time approaches  
        tsec(k2,k1) = timeit(@() feval(fcns{k2}, vals,runs), 1);
    end
end

figure,      % Plot runtimes
loglog(datasizes,tsec(1,:),'-bo'), hold on
loglog(datasizes,tsec(2,:),'-k+')
set(gca,'xgrid','on'),set(gca,'ygrid','on'),
xlabel('Datasize ->'), ylabel('Runtimes (s)')
legend(upper(strrep(fcns,'_',' '))),title('Runtime Plot')

figure,      % Plot speedups
semilogx(datasizes,tsec(1,:)./tsec(2,:),'-rx')        
set(gca,'ygrid','on'), xlabel('Datasize ->')
legend('Speedup(x) with cumsum+diff over cumsum-only'),title('Speedup Plot')

رمز الوظيفة المرتبطة به rld_cumsum.m:

function out = rld_cumsum(vals,runlens)
index = zeros(1,sum(runlens));
index([1 cumsum(runlens(1:end-1))+1]) = 1;
out = vals(cumsum(index));
return;

وقت التشغيل وقطع المؤامرات

الاستنتاجات

يبدو أن النهج المقترح يمنحنا تسريعًا ملحوظًا على cumsum-only النهج الذي يدور حول 3x!

لماذا هذا جديد cumsum+diff النهج القائم أفضل من السابق cumsum-only يقترب؟

حسنًا ، يكمن جوهر السبب في الخطوة الأخيرة من cumsum-only النهج الذي يحتاج إلى تعيين قيم "Cumsumed" إلى vals. في الجديد cumsum+diff النهج القائم ، نحن نفعل diff(vals) بدلا من ذلك الذي تقوم Matlab معالجته فقط n العناصر (حيث N هو عدد أطوال الترتيب) بالمقارنة مع رسم الخرائط sum(runLengths) عدد العناصر ل cumsum-only النهج ويجب أن يكون هذا العدد عدة مرات أكثر من n وبالتالي تسريع ملحوظ مع هذا النهج الجديد!

Answer 2

المعايير

تم تحديثه لـ R2015B: repelem الآن أسرع لجميع أحجام البيانات.

---

الوظائف المختبرة:

1. ماتلاب مدمج repelem الوظيفة التي تمت إضافتها في R2015A
2. Gnovice cumsum المحلول (rld_cumsum)
3. ديفاكار cumsum+diff المحلول (rld_cumsum_diff)
4. Knedlsepp accumarray المحلول (knedlsepp5cumsumaccumarray) من هذا المشنور
5. التنفيذ القائم على الحلقة الساذجة (naive_jit_test.m) لاختبار برنامج التحويل البرمجي في الوقت المناسب

نتائج test_rld.m على R2015ب:

مؤامرة التوقيت القديمة باستخدام R2015أ هنا.

الموجودات:

• repelem هو دائما الأسرع من قبل تقريبا عامل 2.
• rld_cumsum_diff أسرع باستمرار من rld_cumsum.
• repelem أسرع لأحجام البيانات الصغيرة (أقل من حوالي 300-500 عنصر)
• rld_cumsum_diff يصبح أسرع بكثير من repelem حوالي 5000 عنصر
• repelem يصبح أبطأ من rld_cumsum ما بين 30000 و 300000 عنصر
• rld_cumsum لديه نفس الأداء تقريبا مثل knedlsepp5cumsumaccumarray
• naive_jit_test.m لديه سرعة ثابتة تقريبًا وعلى قدم المساواة rld_cumsum و knedlsepp5cumsumaccumarray لأحجام أصغر ، أسرع قليلاً للأحجام الكبيرة

مؤامرة المعدل القديم باستخدام R2015أ هنا.

استنتاج

يستخدم repelem أدناه حوالي 5000 عنصر و cumsum+diff الحل أعلاه.

Answer 3

لا توجد وظيفة مدمجة أعرفها ، ولكن إليك حل واحد:

index = zeros(1,sum(b));
index([1 cumsum(b(1:end-1))+1]) = 1;
c = a(cumsum(index));

تفسير:

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

من أجل الوضوح ، هذا ما تبدو عليه المتجهات المختلفة لقيم a و b الواردة في السؤال:

        index = [1 0 1 0 1 1 0 0]
cumsum(index) = [1 1 2 2 3 4 4 4]
            c = [1 1 3 3 2 5 5 5]

---

تعديل: من أجل الاكتمال ، هناك هو بديل آخر باستخدام arrayfun, ، ولكن يبدو أن هذا يستغرق في أي مكان من 20 إلى 100 مرة لتشغيله من الحل أعلاه مع وجود المتجهات حتى 10،000 عنصر طويل:

c = arrayfun(@(x,y) x.*ones(1,y),a,b,'UniformOutput',false);
c = [c{:}];

Answer 4

هناك أخيرًا (اعتبارًا من R2015A) وظيفة مدمجة وموثقة للقيام بذلك ، repelem. بناء الجملة التالي ، حيث تكون الوسيطة الثانية متجهًا ، وثيقة الصلة هنا:

W = repelem(V,N), ، مع المتجه V وناقل N, ، يخلق ناقل W حيث العنصر V(i) مكرر N(i) مرات.

أو وضع بطريقة أخرى ، "كل عنصر من عناصر N يحدد عدد المرات لتكرار العنصر المقابل لـ V."

مثال:

>> a=[1,3,2,5]
a =
     1     3     2     5
>> b=[2,2,1,3]
b =
     2     2     1     3
>> repelem(a,b)
ans =
     1     1     3     3     2     5     5     5

Answer 5

مشاكل الأداء في Matlab مدمجة repelem تم إصلاحها اعتبارا من R2015B. لقد قمت بتشغيل test_rld.m برنامج من منشور ChappJC في R2015B ، و repelem أصبح الآن أسرع من الخوارزميات الأخرى بحوالي عامل 2: