MATLAB 中的游程解码 [英] Run-length decoding in MATLAB

问题描述

为了巧妙地使用线性索引或 accumarray，我有时觉得需要根据 gnovice 的 原始答案 将是性能最好的.

<小时>

如果您想自己进行速度比较，这里是用于生成上面图表的代码.

function theLastRunLengthDecodingComputationComparisonYoullEverNeed()Funcs = {@knedlsepp0, ...@LuisMendo1bsxfun，...@LuisMendo2cumsum，...@gnovice3cumsum，...@Divakar4replicate_bsxfunmask，...@knedlsepp5cumsumaccumarray};%% 运行次数增加，运行长度中的最大尺寸较低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);对于 i = 1:2时间 = compareFunctions(Funcs, paramGenerators{i}, 0.5);完成计算 = any(~isnan(times),2);h = figure('可见', '关闭');loglog(ns(finishedComputations),times(finishedComputations,:));Legend(cellfun(@func2str,Funcs,'uni',0),'Location','NorthWest','Interpreter','none');title('运行长度解码的运行时比较 - 运行次数增加');xlabel('length(runLengths)');ylabel('秒');print(['-f',num2str(h)],'-dpng','-r100',['RunLengthComparsion',num2str(i)]);结尾结尾函数时间 = compareFunctions(Funcs, paramGenerators, timeLimitInSeconds)如果 nargin<3timeLimitInSeconds = Inf;结尾时间 = zeros(numel(paramGenerators),numel(Funcs));对于 i = 1:numel(paramGenerators)参数 = feval(paramGenerators{i});对于 j = 1:numel(Funcs)如果 max(times(:,j))1V = reshape(values(V), 1, []);结尾V = shiftdim(V, ~isrow(runLengths));结尾%%//###############################函数 V = LuisMendo1bsxfun(runLengths, values)nn = 1:numel(runLengths);if nargin==1 %//处理单输入情况值 = nn;结尾V = 值(非零值(bsxfun(@times，nn，...bsxfun(@le, (1:max(runLengths)).', runLengths(:).'))));if size(runLengths,1)~=size(values,1) %//调整输出向量的方向V = V.';%'结尾结尾%%//###############################函数 V = LuisMendo2cumsum(runLengths, values)if nargin==1 %//处理单输入情况值 = 1:numel(runLengths);结尾[ii, ~, jj] = find(runLengths(:));V(cumsum(jj(end:-1:1))) = 1;V = 值(ii(cumsum(V(end:-1:1))));if size(runLengths,1)~=size(values,1) %//调整输出向量的方向V = V.';%'结尾结尾%%//###############################函数 V = gnovice3cumsum(runLengths, values)isColumnVector = size(runLengths,1)>1;if nargin==1 %//处理单输入情况值 = 1:numel(runLengths);结尾values = reshape(values(runLengths~=0),1,[]);if isempty(values) %//如果没有运行V = [];返回;结尾runLengths = nonzeros(runLengths(:));index = zeros(1,sum(runLengths));index(cumsum([1;runLengths(1:end-1)])) = 1;V = 值(累积总和(索引))；if isColumnVector %//调整输出向量的方向V = V.';%'结尾结尾%%//###############################函数 V = Divakar4replicate_bsxfunmask(runLengths, values)if nargin==1 %//处理单输入情况值 = 1:numel(runLengths);结尾%//进行大小检查以确保值和游程长度都是行向量.如果大小(值，1)>1值 = 值.';%//'结尾如果大小(运行长度，1)>1yes_transpose_output = false;runLengths = runLengths.';%//'别的yes_transpose_output = true;结尾maxlen = max(runLengths);all_values = repmat(values,maxlen,1);%//OR all_values = values(ones(1,maxlen),:);V = all_values(bsxfun(@le,(1:maxlen)',runLengths));%//'%//将 V 的形状恢复为游程的形状如果是_transpose_outputV = V.';%//'结尾结尾%%//###############################函数 V = knedlsepp5cumsumaccumarray(runLengths, values)isRowVector = size(runLengths,2)>1;%//实际计算使用列向量V = cumsum(accumarray(cumsum([1; runLengths(:)]), 1));V = V(1:end-1);%//在第二个参数的情况下如果 nargin>1V = reshape(values(V),[],1);结尾%//如果原始是行向量，则转置如果是行向量V = V.';%'结尾结尾

For clever usage of linear indexing or accumarray, I've sometimes felt the need to generate sequences based on run-length encoding. As there is no built-in function for this, I am asking for the most efficient way to decode a sequence encoded in RLE.

Specification:

As to make this a fair comparison I would like to set up some specifications for the function:

• If optional second argument values of same length is specified, the output should be according to those values, otherwise just the values 1:length(runLengths).
• Gracefully handle:
  • zeros in runLengths
  • values being a cell array.
• Output vector should have same column/row format as runLengths

In short: The function should be equivalent to the following code:

function V = runLengthDecode(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

Examples:

Here are a few test cases

runLengthDecode([0,1,0,2])
runLengthDecode([0,1,0,4], [1,2,4,5].')
runLengthDecode([0,1,0,2].', [10,20,30,40])
runLengthDecode([0,3,1,0], {'a','b',1,2})

and their output:

>> runLengthDecode([0,1,0,2])
ans =
     2     4     4

>> runLengthDecode([0,1,0,4], [1,2,4,5].')
ans =    
     2     5     5     5     5

>> runLengthDecode([0,1,0,2].', [10,20,30,40])
ans =
    20
    40
    40

>> runLengthDecode([0,3,1,0],{'a','b',1,2})
ans = 
    'b'    'b'    'b'    [1]

解决方案

To find out which one is the most efficient solution, we provide a test-script that evaluates the performance. The first plot depicts runtimes for growing length of the vector runLengths, where the entries are uniformly distributed with maximum length 200. A modification of gnovice's solution is the fastest, with Divakar's solution being second place.

This second plot uses nearly the same test data except it includes an initial run of length 2000. This mostly affects both bsxfun solutions, whereas the other solutions will perform quite similarly.

The tests suggest that a modification of gnovice's original answer will be the most performant.

---

If you want to do the speed comparison yourself, here's the code used to generate the plot above.

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

这篇关于MATLAB 中的游程解码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！