Декодирование длины пробега в MATLAB

Ответ 1

Чтобы узнать, какое из них является наиболее эффективным решением, мы предоставляем test- script, который оценивает производительность. На первом графике показаны периоды времени для увеличения длины вектора runLengths, где записи равномерно распределены с максимальной длиной 200. Модификация gnovice-решения является самой быстрой, с Решение Divakar занимает второе место.

Этот второй график использует почти те же данные теста, за исключением того, что он включает начальный прогон длины 2000. Это в основном влияет на оба решения bsxfun, тогда как другие решения будут работать совершенно аналогично.

Тесты показывают, что модификация gnovice оригинальный ответ будет самой результативной.

Если вы хотите выполнить сравнение скорости самостоятельно, здесь используется код, используемый для создания графика выше.

function theLastRunLengthDecodingComputationComparisonYoullEverNeed()
Funcs =  {@knedlsepp0, ...
          @LuisMendo1bsxfun, ...
          @LuisMendo2cumsum, ...
          @gnovice3cumsum, ...
          @Divakar4replicate_bsxfunmask, ...
          @knedlsepp5cumsumaccumarray
          };    
%% Growing number of runs, low maximum sizes in runLengths
ns = 2.^(1:25);
paramGenerators{1} = arrayfun(@(n) @(){randi(200,n,1)}, ns,'uni',0);
paramGenerators{2} = arrayfun(@(n) @(){[2000;randi(200,n,1)]}, ns,'uni',0);
for i = 1:2
    times = compareFunctions(Funcs, paramGenerators{i}, 0.5);
    finishedComputations = any(~isnan(times),2);
    h = figure('Visible', 'off');
    loglog(ns(finishedComputations), times(finishedComputations,:));
    legend(cellfun(@func2str,Funcs,'uni',0),'Location','NorthWest','Interpreter','none');
    title('Runtime comparison for run length decoding - Growing number of runs');
    xlabel('length(runLengths)'); ylabel('seconds');
    print(['-f',num2str(h)],'-dpng','-r100',['RunLengthComparsion',num2str(i)]);
end
end

function times = compareFunctions(Funcs, paramGenerators, timeLimitInSeconds)
if nargin<3
    timeLimitInSeconds = Inf;
end
times = zeros(numel(paramGenerators),numel(Funcs));
for i = 1:numel(paramGenerators)
    Params = feval(paramGenerators{i});
    for j = 1:numel(Funcs)
        if max(times(:,j))<timeLimitInSeconds
            times(i,j) = timeit(@()feval(Funcs{j},Params{:}));
        else
            times(i,j) = NaN;
        end
    end
end
end
%% // #################################
%% // HERE COME ALL THE FANCY FUNCTIONS
%% // #################################
function V = knedlsepp0(runLengths, values)
[~,V] = histc(1:sum(runLengths), cumsum([1,runLengths(:).']));%'
if nargin>1
    V = reshape(values(V), 1, []);
end
V = shiftdim(V, ~isrow(runLengths));
end

%% // #################################
function V = LuisMendo1bsxfun(runLengths, values)
nn = 1:numel(runLengths);
if nargin==1 %// handle one-input case
    values = nn;
end
V = values(nonzeros(bsxfun(@times, nn,...
    bsxfun(@le, (1:max(runLengths)).', runLengths(:).'))));
if size(runLengths,1)~=size(values,1) %// adjust orientation of output vector
    V = V.'; %'
end
end

%% // #################################
function V = LuisMendo2cumsum(runLengths, values)
if nargin==1 %// handle one-input case
    values = 1:numel(runLengths);
end
[ii, ~, jj] = find(runLengths(:));
V(cumsum(jj(end:-1:1))) = 1;
V = values(ii(cumsum(V(end:-1:1))));
if size(runLengths,1)~=size(values,1) %// adjust orientation of output vector
    V = V.'; %'
end
end

%% // #################################
function V = gnovice3cumsum(runLengths, values)
isColumnVector =  size(runLengths,1)>1;
if nargin==1 %// handle one-input case
    values = 1:numel(runLengths);
end
values = reshape(values(runLengths~=0),1,[]);
if isempty(values) %// If there are no runs
    V = []; return;
end
runLengths = nonzeros(runLengths(:));
index = zeros(1,sum(runLengths));
index(cumsum([1;runLengths(1:end-1)])) = 1;
V = values(cumsum(index));
if isColumnVector %// adjust orientation of output vector
    V = V.'; %'
end
end
%% // #################################
function V = Divakar4replicate_bsxfunmask(runLengths, values)
if nargin==1   %// Handle one-input case
    values = 1:numel(runLengths);
end

%// Do size checking to make sure that both values and runlengths are row vectors.
if size(values,1) > 1
    values = values.'; %//'
end
if size(runLengths,1) > 1
    yes_transpose_output = false;
    runLengths = runLengths.'; %//'
else
    yes_transpose_output = true;
end

maxlen = max(runLengths);

all_values = repmat(values,maxlen,1);
%// OR all_values = values(ones(1,maxlen),:);

V = all_values(bsxfun(@le,(1:maxlen)',runLengths)); %//'

%// Bring the shape of V back to the shape of runlengths
if yes_transpose_output
    V = V.'; %//'
end
end
%% // #################################
function V = knedlsepp5cumsumaccumarray(runLengths, values)
isRowVector = size(runLengths,2)>1;
%// Actual computation using column vectors
V = cumsum(accumarray(cumsum([1; runLengths(:)]), 1));
V = V(1:end-1);
%// In case of second argument
if nargin>1
    V = reshape(values(V),[],1);
end
%// If original was a row vector, transpose
if isRowVector
    V = V.'; %'
end
end

Ответ 2

Как и в R2015a, функция repelem - лучший выбор для этого:

function V = runLengthDecode(runLengths, values)
if nargin<2
    values = 1:numel(runLengths);
end
V = repelem(values, runLengths);
end

Для версий до R2015a это быстрая альтернатива:

Альтернатива repelem:

У меня возникло ощущение, что подход gnovice можно улучшить, используя лучшее исправление с нулевой задержкой, чем маска предварительной обработки. Поэтому я дал accumarray выстрел. Похоже, что это дает еще один импульс:

function V = runLengthDecode(runLengths, values)
%// Actual computation using column vectors
V = cumsum(accumarray(cumsum([1; runLengths(:)]), 1));
V = V(1:end-1);
%// In case of second argument
if nargin>1
    V = reshape(values(V),[],1);
end
%// If original was a row vector, transpose
if size(runLengths,2)>1
    V = V.'; %'
end
end

Ответ 3

Подход 1

Это должно быть достаточно быстро. Оно использует bsxfun, чтобы создать матрицу размера numel(runLengths) x numel(runLengths), поэтому она может не подходить для огромных размеров ввода.

function V = runLengthDecode(runLengths, values)
nn = 1:numel(runLengths);
if nargin==1 %// handle one-input case
    values = nn;
end
V = values(nonzeros(bsxfun(@times, nn,...
    bsxfun(@le, (1:max(runLengths)).', runLengths(:).'))));
if size(runLengths,1)~=size(values,1) %// adjust orientation of output vector
    V = V.';
end

Подход 2

Этот подход, основанный на cumsum, является адаптированием того, что используется в this другой ответ. Он использует меньше памяти, чем подход 1.

function V = runLengthDecode2(runLengths, values)
if nargin==1 %// handle one-input case
    values = 1:numel(runLengths);
end
[ii, ~, jj] = find(runLengths(:));
V(cumsum(jj(end:-1:1))) = 1;
V = values(ii(cumsum(V(end:-1:1))));
if size(runLengths,1)~=size(values,1) %// adjust orientation of output vector
    V = V.';
end

Ответ 4

Представленное здесь решение в основном выполняет run-length decoding в два этапа -

• Повторите все values до максимального числа runLengths.
• Используйте bsxfun возможность маскировки, чтобы выбрать из каждого столбца соответствующий runLengths.

Остальная часть содержимого внутри кода функции заключается в том, чтобы заботиться о размерах ввода и вывода для удовлетворения требований, заданных в вопросе.

Следующий код функции будет "очищенной" версией одного из моих предыдущих ответов на аналогичную проблему. Здесь код -

function V = replicate_bsxfunmask(runLengths, values)

if nargin==1   %// Handle one-input case
    values = 1:numel(runLengths);
end

%// Do size checking to make sure that both values and runlengths are row vectors.
if size(values,1) > 1
    values = values.'; %//'
end
if size(runLengths,1) > 1
    yes_transpose_output = false;
    runLengths = runLengths.'; %//'
else
    yes_transpose_output = true;
end

maxlen = max(runLengths);

all_values = repmat(values,maxlen,1);
%// OR all_values = values(ones(1,maxlen),:);

V = all_values(bsxfun(@le,(1:maxlen)',runLengths)); %//'

%// Bring the shape of V back to the shape of runlengths
if yes_transpose_output
    V = V.'; %//'
end

return;

Следующий код будет гибридным (cumsum + replicate_bsxfunmask) и будет подходящим, если у вас будет большое количество выбросов или действительно огромные выбросы. Также, чтобы это было просто, на данный момент это работает только с числовыми массивами. Здесь реализация -

function out = replicate_bsxfunmask_v2(runLengths, values)

if nargin==1                       %// Handle one-input case
    values = 1:numel(runLengths);
end

if size(values,1) > 1
    values = values.';  %//'
end

if size(runLengths,1) > 1
    yes_transpose_output = true;
    runLengths = runLengths.';  %//'
else
    yes_transpose_output = false;
end

%// Regularize inputs
values = values(runLengths>0);
runLengths = runLengths(runLengths>0);

%// Main portion of code
thresh = 200; %// runlengths threshold that are to be processed with cumsum

crunLengths = cumsum(runLengths); %%// cumsums of runlengths
mask = runLengths >= thresh; %// mask of runlengths above threshold
starts = [1 crunLengths(1:end-1)+1]; %// starts of each group of runlengths

mask_ind = find(mask); %// indices of mask

post_mark = starts(mask);
negt_mark = crunLengths(mask)+1;

if  ~isempty(negt_mark) && negt_mark(end) > crunLengths(end)
    negt_mark(end) = [];
end

%// Create array & set starts markers for starts of runlengths above thresh
marked_out = zeros(1,crunLengths(end));
marked_out(post_mark) = mask_ind;
marked_out(negt_mark) = marked_out(negt_mark) -1*mask_ind(1:numel(negt_mark));

%// Setup output array with the cumsumed version of marked array
out = cumsum(marked_out);

%// Mask for final ouput to decide between large and small runlengths
thresh_mask = out~=0;

%// Fill output array with cumsum and then rep-bsxfun based approaches
out(thresh_mask) = values(out(thresh_mask));

values = values(~mask);
runLengths = runLengths(~mask);

maxlen = max(runLengths);
all_values = repmat(values,maxlen,1);
out(~thresh_mask) = all_values(bsxfun(@le,(1:maxlen)',runLengths)); %//'

if yes_transpose_output
    out = out.';  %//'
end

return;