Как создать вектор, повторяющий разные числа с определенными суммами? [Дубликат]

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

У нас есть массив значений, 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, и поэтому заметное ускорение с этим новым подходом!