У нас есть массив значений, 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'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)
Предварительное выделение Hack
Как можно видеть, приведенные выше код использует предварительное распределение с нулями. Теперь, согласно этому блоку UNDOCUMENTED MATLAB, для более быстрого предварительного выделения , можно добиться гораздо более быстрого предварительного выделения с помощью -
array(clens(end)) = 0; % instead of array = zeros(1,(clens(end)))
Wrapping up: Function Code
Чтобы обойти все, у нас был бы компактный функциональный код для достижения этого декодирования длины строки, например:
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
, и поэтому заметное ускорение с этим новым подходом!
Удаляет стартовую точку с запятой (;)
Как: ;extension=php_intl.dll
к extension=php_intl.dll
Это помогло мне.
Это помогло моему случаю установить правильную вихревую версию
sudo apt-get install php5-curl