performance - Decodificación de longitud de ejecución en MATLAB

run-length-encoding

Question

Para un uso inteligente de la indexación lineal o accumarray , a veces he sentido la necesidad de generar secuencias basadas en la codificación de longitud de ejecución . Como no hay una función incorporada para esto, solicito la forma más eficiente de decodificar una secuencia codificada en RLE.

Especificación:

Para hacer una comparación justa, me gustaría configurar algunas especificaciones para la función:

• Si se especifican values de segundo argumento opcionales de la misma longitud, la salida debe estar de acuerdo con esos valores, de lo contrario solo los valores 1:length(runLengths) .
• Manejar con gracia:
  • ceros en runLengths
  • values son una matriz de celdas.
• El vector de salida debe tener el mismo formato de columna / fila que runLengths

En resumen: la función debe ser equivalente al siguiente código:

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

Ejemplos:

Aquí hay algunos casos de prueba.

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

y su salida:

>> 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]

Answer 1

Enfoque 1

Esto debería ser razonablemente rápido. Utiliza bsxfun para crear una matriz de tamaño numel(runLengths) x numel(runLengths) , por lo que puede no ser adecuado para grandes tamaños de entrada.

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

Enfoque 2

Este enfoque, basado en cumsum , es una adaptación de la utilizada en esta otra respuesta . Utiliza menos memoria que el enfoque 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

Answer 2

A partir de R2015a, la función repelem es la mejor opción para hacer esto:

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

Para versiones anteriores a R2015a, esta es una alternativa rápida:

Alternativa al repelem :

Tuve la sensación de que el enfoque de gnovice podría mejorarse mediante el uso de una mejor corrección de longitud cero que la máscara de preprocesamiento. Así que le accumarray una oportunidad a accumarray . Parece que esto le da a la solución otro impulso más:

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

Answer 3

La solución presentada aquí básicamente hace la run-length decoding en dos pasos:

1. Replica todos los values hasta el número máximo de runLengths .
2. Utilice la capacidad de enmascaramiento de bsxfun para seleccionar de cada columna las runlengths correspondientes.

El resto de las cosas dentro del código de función es cuidar los tamaños de entrada y salida para satisfacer los requisitos establecidos en la pregunta.

El código de función que figura a continuación sería una versión "limpiada" de una de mis respuestas anteriores a un problema similar . Aquí está el código.

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;

El código que figura a continuación sería un híbrido ( cumsum + replicate_bsxfunmask ) y sería adecuado cuando tenga un buen número de valores atípicos o valores atípicos realmente grandes. También para que sea simple, por ahora esto funciona solo en matrices numéricas. Aquí está la implementación:

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;

Answer 4

Para descubrir cuál es la solución más eficiente, proporcionamos un script de prueba que evalúa el rendimiento. La primera gráfica muestra tiempos de ejecución para la longitud creciente del vector runLengths , donde las entradas se distribuyen uniformemente con una longitud máxima de 200. Una modificación de la solución de gnovice es la más rápida, con la solución de Divakar en segundo lugar.

Esta segunda gráfica utiliza casi los mismos datos de prueba, excepto que incluye una ejecución inicial de longitud 2000 . Esto afecta principalmente a ambas soluciones bsxfun , mientras que las otras soluciones funcionarán de manera bastante similar.

Las pruebas sugieren que una modificación de la respuesta original de gnovice será la más eficaz .

Si desea hacer la comparación de velocidad usted mismo, aquí está el código utilizado para generar la gráfica anterior.

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