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

Постановка задачи

У нас есть массив значений, 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 и поместить «соответствующие» значения в «ключевые» позиции по массиву нhive, так что после применения « cumsum » мы получим окончательный массив повторных vals runlens раз.

Шаги: давайте укажем вышеупомянутые шаги, чтобы дать перспективный подход более простой взгляд:

1) Инициализировать массив нhive: какова должна быть длина? Поскольку мы повторяем времена runlens , длина массива нhive должна быть суммой всех runlens .

2) Найти ключевые позиции / индексы: теперь эти ключевые позиции являются местами вдоль массива нhive, где каждый элемент из vals начинает повторяться. Таким образом, для runlens = [2,2,1,3] ключевые позиции, отображаемые в массив нhive, будут:

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

3) Найдите подходящие значения: последний гвоздь, который нужно забить перед использованием cumsum это поставить «соответствующие» значения в эти ключевые позиции. Теперь, поскольку мы будем делать cumsum вскоре после этого, если вы подумаете внимательно, вам понадобится differentiated версия values с diff , так что cumsum на них вернет наши values . Так как эти дифференцированные значения будут помещены на массив нhive в местах, разделенных расстояниями runlens , после использования cumsum мы бы каждый элемент vals повторяли runlens times как окончательный вывод.

Код решения

Вот реализация, выполняющая все вышеупомянутые шаги –

 % 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) 

Предварительный взнос

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

 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 основанным cumsum-only на MATLAB 2014B на 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 с cumsum-only , который составляет около 3х !

Почему этот новый cumsum+diff лучше, чем предыдущий cumsum-only ?

Ну, суть причины заключается в завершающем шаге cumsum-only который должен отображать «cumsumed» значения в vals . В новом cumsum+diff мы используем diff(vals) вместо этого, для которого MATLAB обрабатывает только n элементов (где n – количество runLengths) по сравнению с отображением sum(runLengths) числа элементов для cumsum-only подход, и это число должно быть во много раз больше, чем n и поэтому заметное ускорение с этим новым подходом!

Ориентиры

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

---

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

1. repelem функция repelem , добавленная в R2015a
2. Решение gnovice cumsum ( rld_cumsum )
3. cumsum + diff rld_cumsum_diff ( rld_cumsum_diff )
4. решение для accumarray ( knedlsepp5cumsumaccumarray ) из этой публикации
5. Реализация на основе наивного цикла ( naive_jit_test.m ) для тестирования компилятора «точно в момент времени»

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

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

Выводы :

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

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

Вывод

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

Нет встроенной функции, о которой я знаю, но вот одно решение:

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

Объяснение:

Сначала вектор нhive создается той же длины, что и выходной массив (т. Е. Сумма всех репликаций в 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{:}]; 

Наконец, (в 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 

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