Повторить копии элементов массива: декодирование длины в MATLAB

Ответ 1

Заявление о проблемах

У нас есть массив значений, vals и runlengths, 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 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)

Предоплата Hack

Как видно, в приведенном выше коде используется предварительное распределение с нулями. Теперь, согласно этому UNDOCUMENTED MATLAB blog on faster pre-allocation, можно добиться гораздо более быстрого предварительного выделения с помощью

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

Завершение: код функции

Чтобы обойти все, у нас был бы компактный функциональный код для достижения такого декодирования длины строки, как это было -

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 - количество runLengths) по сравнению с отображением sum(runLengths) числа элементов для cumsum-only, и это число должно быть во много раз больше n и, следовательно, заметное ускорение с помощью этого нового подхода!

Ответ 2

Контрольные показатели

Обновлен для R2015b: repelem теперь самый быстрый для всех размеров данных.

Проверенные функции:

• Встроенная функция MATLAB repelem, которая была добавлена ​​в R2015a
• Решение gnovice cumsum (rld_cumsum)
• Решение Divakar cumsum + diff (rld_cumsum_diff)
• Решение knedlsepp accumarray (knedlsepp5cumsumaccumarray) из этого сообщения
• Реализация на основе наивного цикла (naive_jit_test.m) для тестирования компилятора "точно в срок"

Результаты test_rld.m на R2015 b:

Старый график времени с использованием R2015 a здесь.

Выводы

• repelem всегда самый быстрый, примерно в 2 раза.
• rld_cumsum_diff последовательно быстрее, чем rld_cumsum.
• repelem быстрее всего подходит для небольших размеров данных (менее 300-500 элементов)
• rld_cumsum_diff становится значительно быстрее, чем repelem около 5 & thinsp; 000 элементов
• repelem становится медленнее, чем rld_cumsum где-то между 30 и thinsp; 000 и 300 & thinsp; 000 элементов
• rld_cumsum имеет примерно такую ​​же производительность, как knedlsepp5cumsumaccumarray
• naive_jit_test.m имеет почти постоянную скорость и наравне с rld_cumsum и knedlsepp5cumsumaccumarray для меньших размеров, немного быстрее для больших размеров

Старый график скорости с использованием R2015 a здесь.

Заключение

Используйте repelem ниже около 5 & thinsp; 000 элементов и cumsum + diff решение выше.

Ответ 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]

EDIT:. Для полноты есть еще одна альтернатива, использующая ARRAYFUN, но это кажется занять от 20-100 раз дольше, чем указанное решение с векторами длиной до 10 000:

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

Ответ 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

Ответ 5

Проблемы с производительностью в встроенном MATLAB repelem были исправлены с R2015b. Я запустил программу test_rld.m из сообщения chappjc в R2015b, а repelem теперь быстрее, чем другие алгоритмы, примерно в 2 раза: