كرر نسخ من عناصر المصفوفة: فك تشفير الطول في ماتلاب
-
21-09-2019 - |
سؤال
أحاول إدراج قيم متعددة في صفيف باستخدام صفيف "قيم" وصفيف "عداد". على سبيل المثال ، إذا:
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
.
المحلول
عرض المشكلة
لدينا مجموعة من القيم ، 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
وبالتالي تسريع ملحوظ مع هذا النهج الجديد!
نصائح أخرى
المعايير
تم تحديثه لـ R2015B: repelem
الآن أسرع لجميع أحجام البيانات.
الوظائف المختبرة:
- ماتلاب مدمج
repelem
الوظيفة التي تمت إضافتها في R2015A - Gnovice
cumsum
المحلول (rld_cumsum
) - ديفاكار
cumsum
+diff
المحلول (rld_cumsum_diff
) - Knedlsepp
accumarray
المحلول (knedlsepp5cumsumaccumarray
) من هذا المشنور - التنفيذ القائم على الحلقة الساذجة (
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
الحل أعلاه
لا توجد وظيفة مدمجة أعرفها ، ولكن إليك حل واحد:
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{:}];
هناك أخيرًا (اعتبارًا من 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
مشاكل الأداء في Matlab مدمجة repelem
تم إصلاحها اعتبارا من R2015B. لقد قمت بتشغيل test_rld.m
برنامج من منشور ChappJC في R2015B ، و repelem
أصبح الآن أسرع من الخوارزميات الأخرى بحوالي عامل 2: