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

run-length-encoding (4)

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]

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

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

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

Replica todos los values hasta el número máximo de runLengths .
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;

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.