Repetir las copias de los elementos de la matriz: Run-descodificación de longitud en MATLAB

Question

Estoy intentando insertar varios valores en una matriz mediante una matriz 'valores' y un array 'counter'. Por ejemplo, si:

a=[1,3,2,5]
b=[2,2,1,3]

Quiero la salida de alguna función

c=somefunction(a,b)

ser

c=[1,1,3,3,2,5,5,5]

Cuando un (1) se repite b número (1) de veces, a (2) se repite B (2) veces, etc ...

¿Hay una función incorporada en MATLAB que hace esto? Me gustaría evitar el uso de un bucle si es posible. He intentado variaciones de 'repmat ()' y 'Kron ()' en vano.

Esto es básicamente Run-length encoding .

Answer 1

Planteamiento del problema

Tenemos una matriz de valores, vals y longitudes de recorrido, runlens:

vals     = [1,3,2,5]
runlens  = [2,2,1,3]

Se necesitan repetir cada elemento en tiempos vals cada elemento correspondiente en runlens. Por lo tanto, la salida final sería:

output = [1,1,3,3,2,5,5,5]

enfoque prospectivo

Una de las herramientas más rápidas con MATLAB es cumsum y está muy útil cuando se trata de problemas de vectorización que el trabajo sobre los patrones irregulares. En el problema planteado, la irregularidad viene con los diferentes elementos en runlens.

Ahora, para explotar cumsum, tenemos que hacer dos cosas aquí: inicializar una matriz de zeros y lugar "apropiado" los valores en las posiciones "clave" sobre la matriz de ceros, de tal manera que después de aplicar "cumsum", terminaríamos con una matriz final del vals repetido de veces runlens.

Pasos: número de Let los anteriores pasos mencionados para dar el enfoque prospectivo una perspectiva más fácil:

1) Inicializar ceros matriz: ¿Cuál debe ser la longitud? Desde estamos repitiendo veces runlens, la longitud de la matriz de ceros debe ser la suma de toda la runlens.

2) encontrar posiciones claves / índices: Ahora estas posiciones clave son lugares a lo largo de la matriz de ceros donde cada elemento de vals empieza a repetir. Así, por runlens = [2,2,1,3], las posiciones clave mapeadas a la matriz de ceros sería:

[X 0 X 0 X X 0 0] % where X's are those key positions.

3) Encontrar los valores adecuados: El último clavo a ser martillado antes de usar cumsum sería poner los valores "apropiadas" en esas posiciones clave. Ahora, ya que estaríamos haciendo cumsum poco después, si se piensa detenidamente, se necesitaría una versión differentiated de values con diff , por lo que los haría cumsum en traer de vuelta nuestra values . Puesto que estos valores diferenciados serían colocados en una matriz de ceros en lugares separados por las distancias runlens, después de usar cumsum tendríamos cada elemento vals repitió veces runlens como la salida final.

código de la solución

Aquí está la aplicación cosido de todos los anteriores pasos mencionados -

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

Pre-asignación Hack

Como puede verse que los anteriores usos de codigo escrito con ceros de asignación de pre. Ahora, de acuerdo con esta el blog INDOCUMENTADOS MATLAB en rápido pre-asignación , se puede lograr mucho más rápido pre -allocation con -

array(clens(end)) = 0; % instead of array = zeros(1,(clens(end)))

Concluyendo: Función Código

Para terminar todo, que tendría un código de función compacto para lograr esto por longitud de decodificación como tal -

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;

Benchmarking

Código Benchmarking

Listado próxima es el código de la evaluación comparativa para comparar los tiempos de ejecución y aceleraciones para el enfoque cumsum+diff se indica en este post sobre el href="https://stackoverflow.com/a/1975835/3293881"> otro enfoque basado cumsum-only en 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')

Asociados código de función para 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;

tiempo de ejecución y velocidad de Parcelas

Conclusiones

El enfoque propuesto nos parece estar dando una aceleración notable sobre el enfoque cumsum-only, que es aproximadamente 3

¿Por qué enfoque se basa esta nueva cumsum+diff mejor que el enfoque anterior cumsum-only?

Bueno, la esencia de la razón se encuentra en la etapa final de la aproximación cumsum-only que necesita asignar los valores "cumsumed" en vals. En el nuevo enfoque basado cumsum+diff, estamos haciendo diff(vals) lugar para el que MATLAB está procesando únicos elementos n (donde n es el número de longitudes de recorrido) en comparación con la asignación del número sum(runLengths) de elementos para el enfoque cumsum-only y este número debe ser muchas veces más de n y por lo tanto la aceleración notable con este nuevo enfoque!

Answer 2

Puntos de Referencia

Actualización de R2015b . repelem ahora más rápido para todos los tamaños de datos

---

Probado funciones:

1. de MATLAB incorporada repelem función que se agregó en R2015a
2. solución cumsum de gnovice ( rld_cumsum )
3. solución cumsum diff + de Divakar ( rld_cumsum_diff )
4. solución accumarray de knedlsepp ( knedlsepp5cumsumaccumarray ) de este post
5. Ingenuo aplicación basada en bucles ( naive_jit_test.m ) para probar el compilador Just-In-Time

Resultados de la test_rld.m en R2015 b :

trama de tiempo mayor que usa el R2015 a aquí .

Conclusiones

• repelem es siempre el más rápido en aproximadamente un factor de 2.
• rld_cumsum_diff es consistentemente más rápido que rld_cumsum.
• repelem es el más rápido para los tamaños pequeños de datos (menos de aproximadamente 300-500 elementos)
• rld_cumsum_diff se convierte en mucho más rápido que repelem alrededor de 5 000 elementos
• repelem vuelve más lento que en algún rld_cumsum entre 30 000 y 300 000 elementos
• rld_cumsum tiene más o menos el mismo rendimiento que knedlsepp5cumsumaccumarray
• naive_jit_test.m tiene una velocidad casi constante ya la par con rld_cumsum y knedlsepp5cumsumaccumarray para tamaños más pequeños, un poco más rápido para grandes tamaños

línea de la velocidad mayor que usa el R2015 a aquí .

Conclusión

Uso repelem debajo de aproximadamente 5 000 elementos y la solución cumsum + diff anteriormente .

Answer 3

No hay ninguna función integrada que conozco, pero aquí es una solución:

index = zeros(1,sum(b));
index([1 cumsum(b(1:end-1))+1]) = 1;
c = a(cumsum(index));

Explicación:

Un vector de ceros se crea por primera vez de la misma longitud que la matriz de salida (es decir la suma de todas las repeticiones en b). Ones se colocan entonces en el primer elemento y cada elemento posterior representando donde el comienzo de una nueva secuencia de valores será en la salida. La suma acumulada de la index vector se puede usar entonces para indexar en a, replicando cada valor el número deseado de veces.

En aras de la claridad, esto es lo que los diferentes vectores parecen a los valores de a y b dadas en la pregunta:

        index = [1 0 1 0 1 1 0 0]
cumsum(index) = [1 1 2 2 3 4 4 4]
            c = [1 1 3 3 2 5 5 5]

---

EDIT: En aras de la exhaustividad, hay es otra alternativa usando ARRAYFUN , pero esto parece tomar de 20-100 veces más en ejecutarse que la solución anterior con vectores de hasta 10.000 elementos de largo:

c = arrayfun(@(x,y) x.*ones(1,y),a,b,'UniformOutput',false);
c = [c{:}];

Answer 4

Hay, finalmente, (a partir de R2015a ) una función incorporada y documentada para hacer esto, repelem . La siguiente sintaxis, donde el segundo argumento es un vector, es relevante aquí:

  

W = repelem(V,N), con V vector y N vector, crea una W vector donde elemento V(i) se repite veces N(i).

O dicho de otra manera, "Cada elemento de N especifica el número de veces que desea repetir el elemento correspondiente de V."

Ejemplo:

>> a=[1,3,2,5]
a =
     1     3     2     5
>> b=[2,2,1,3]
b =
     2     2     1     3
>> repelem(a,b)
ans =
     1     1     3     3     2     5     5     5

Answer 5

Los problemas de rendimiento en MATLAB incorporada repelem se han fijado como de R2015b. He ejecutar el programa test_rld.m desde el puesto de chappjc en R2015b y repelem es ahora más rápido que otros algoritmos en un factor 2: