arrays - teclado - seleccionar elementos de una matriz matlab

Reemplazar todos los ceros en el vector por el valor anterior distinto de cero

Question

Ejemplo del algoritmo Matlab / Octave:

 input vector: [ 1 0 2 0 7 7 7 0 5 0 0 0 9 ]
output vector: [ 1 1 2 2 7 7 7 7 5 5 5 5 9 ]

El algoritmo es muy simple: atraviesa el vector y reemplaza todos los ceros con el último valor distinto de cero. Parece trivial, y es así cuando se hace con un ciclo lento para (i = 1: longitud) y ser capaz de referirse al elemento anterior (i-1), pero parece imposible formularlo en la forma vectorializada rápida. Probé la combinación () y shift () pero solo funciona para la primera aparición de cero, no un número arbitrario de ellos.

¿Se puede hacer en forma vectorizada en Octave / Matlab o se debe usar C para que tenga un rendimiento suficiente en una gran cantidad de datos?

Gracias, Pawel

PD: Tengo otro algoritmo similar lento para forzar a acelerar y parece generalmente imposible referirme a valores previos en una forma vectorizada, como lo haría fácilmente un lag de SQL () o un grupo por o un bucle (i-1). Pero los bucles de Octave / Matlab son terriblemente lentos.

¿Alguien ha encontrado una solución a este problema general o es inútil por razones fundamentales de diseño de Octave / Matlab?

========== EDITAR ===============

Referencia de rendimiento:

==== SOLUCIÓN 1 (lazo lento)

in = out = repmat([ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] ,1 ,100000);
tic; for i=2:length(out) if (out(i)==0) out(i)=out(i-1); endif; endfor; toc;
[in(1:20); out(1:20)] # test to show side by side if ok

Elapsed time is 15.047 seconds.

==== SOLUCIÓN 2 por Dan (~ 80 veces más rápido)

in = V = repmat([ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] ,1 ,100000);
tic;
d = double(diff([0,V])>0);
d(find(d(2:end))+1) = find(diff([0,~V])==-1) - find(diff([0,~V])==1);
out = V(cumsum(~~V+d)-1);
toc;
[in(1:20); out(1:20)] # shows it works ok
Elapsed time is 0.188167 seconds.
# 15.047 / 0.188167 = 79.97 times improvement

==== SOLUCIÓN 3 por GameOfThrows (~ 115 veces más rápido)

in = a = repmat([ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] ,1 ,100000);
tic;
pada = [a,888];
b = pada(find(pada >0));
bb = b(:,1:end-1);
c = find (pada==0);
d = find(pada>0);
length = d(2:end) - (d(1:end-1));
t = accumarray(cumsum([1,length])'',1);
out = R = bb(cumsum(t(1:end-1)));
toc;
Elapsed time is 0.130558 seconds.
# 15.047 / 0.130558 = 115.25 times improvement

==== SOLUCIÓN mágica 4 por Luis Mendo (~ 250 veces más rápido)

Actualizado a un solo y ordenado

in = repmat([ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] , 1, 100000);
tic;
out = nonzeros(in).''(cumsum(in~=0));
toc;
Elapsed time is 0.0597501 seconds.
# 15.047 / 0.0597501 = 251.83 times improvement

Dan, GameOfThrows y Luis - Agradezco mucho su ayuda rápida, nítida y efectiva con este caso. Estas son excelentes soluciones con una excelente aceleración. Me sorprende que tal mejora sea posible y publicaré un segundo desafío ahora. Primero decidí omitirlo, porque lo consideré más difícil y más allá de mi alcance, pero lo que muestra esta evidencia - Espero estar equivocado de nuevo.

Ver también: Desafío de algoritmo trivial / imposible en Octave / Matlab Parte II: memoria de iteraciones

Answer 1

Aquí hay otra solución, usando la interpolación lineal con la búsqueda anterior del vecino .

Supongo que es bastante rápido también, ya que solo hay búsquedas e indexación y no hay cálculos:

in = [1 0 2 0 7 7 7 0 5 0 0 0 9]
mask = logical(in);
idx = 1:numel(in);
in(~mask) = interp1(idx(mask),in(mask),idx(~mask),''previous'');
%// out = in

Explicación

Necesita crear un vector de índice:

idx = 1:numel(in)  $// = 1 2 3 4 5 ...

Y una máscara lógica, enmascarando todos sus valores distintos de cero:

mask = logical(in);

De esta forma, obtendrá los puntos de cuadrícula idx(mask) y los datos de cuadrícula in(mask) para la interpolación. Los puntos de consulta idx(~mask) son índices de datos cero. La información de consulta in(~mask) es luego "calculada" por la siguiente interpolación contigua anterior , por lo que básicamente busca en la cuadrícula cuál es el valor para el punto de la cuadrícula anterior. Exactamente lo que quieres Desafortunadamente, las funciones involucradas tienen una gran sobrecarga para todos los casos imaginables, por eso es aún más lento que la Respuesta de Luis Mendo, aunque no hay cálculos aritméticos involucrados.

Además, uno podría reducir un poco la sobrecarga de interp1 :

F = griddedInterpolant(idx(mask),in(mask),''previous'');
in(~mask) = F(idx(~mask));

Pero no hay demasiado efecto.

in =   %// = out

     1     1     2     2     7     7     7     7     5     5     5     5     9

Punto de referencia

0.699347403200000 %// thewaywewalk
1.329058123200000 %// GameOfThrows
0.408333643200000 %// LuisMendo
1.585014923200000 %// Dan

Código

function [t] = bench()
    in = repmat([ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] ,1 ,100000);

    % functions to compare
    fcns = {
        @() thewaywewalk(in);
        @() GameOfThrows(in);
        @() LuisMendo(in);
        @() Dan(in);
    }; 

    % timeit
    t = zeros(4,1);
    for ii = 1:10;
        t = t + cellfun(@timeit, fcns);
    end
    format long
end

function in = thewaywewalk(in) 
    mask = logical(in);
    idx = 1:numel(in);
    in(~mask) = interp1(idx(mask),in(mask),idx(~mask),''previous'');
end
function out = GameOfThrows(a) 
    pada = [a,888];
    b = pada(find(pada >0));
    bb = b(:,1:end-1);
    c = find (pada==0);
    d = find(pada>0);
    length = d(2:end) - (d(1:end-1));
    t = accumarray(cumsum([1,length])'',1);
    out = bb(cumsum(t(1:end-1)));
end
function out = LuisMendo(in) 
    t = cumsum(in~=0);
    u = nonzeros(in);
    out = u(t).'';
end
function out = Dan(V) 
    d = double(diff([0,V])>0);
    d(find(d(2:end))+1) = find(diff([0,~V])==-1) - find(diff([0,~V])==1);
    out = V(cumsum(~~V+d)-1);
end

Answer 2

Creo que es posible, comencemos con lo básico, quiere capturar donde el número es mayor que 0:

 a = [ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] %//Load in Vector
 pada = [a,888];  %//Pad A with a random number at the end to help in case the vector ends with a 0
 b = pada(find(pada >0)); %//Find where number if bigger than 0
 bb = b(:,1:end-1);     %//numbers that are bigger than 0
 c = find (pada==0);   %//Index where numbers are 0
 d = find(pada>0);     %//Index where numbers are greater than 0
 length = d(2:end) - (d(1:end-1));  %//calculate number of repeats needed for each 0 trailing gap.
 %//R = [cell2mat(arrayfun(@(x,nx) repmat(x,1,nx), bb, length,''uniformoutput'',0))]; %//Repeat the value

 ----------EDIT--------- 
 %// Accumarray and cumsum method, although not as nice as Dan''s 1 liner
 t = accumarray(cumsum([1,length])'',1);
 R = bb(cumsum(t(1:end-1)));

NOTA: utilicé arrayfun , pero también puedes usar accumarray ¿Pienso que esto demuestra que es posible hacer esto en paralelo?

R =

Columnas 1 a 10

 1     1     2     2     7     7     7     7     5     5

Columnas 11 a 13

 5     5     9

PRUEBAS:

a = [ 1 0 2 0 7 7 7 0 5 0 0 0 9 0 0 0 ]

R =

Columnas 1 a 10

 1     1     2     2     7     7     7     7     5     5

Columnas 11 a 16

 5     5     9     9     9     9

ACTUACIÓN:

a = repmat([ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] ,1,10000); %//Double of 130,000
Arrayfun Method : Elapsed time is 6.840973 seconds.
AccumArray Method : Elapsed time is 2.097432 seconds.

Answer 3

Creo que es una solución vectorizada. Funciona en tu ejemplo:

V = [1 0 2 0 7 7 7 0 5 0 0 0 9]
%// This is where the numbers you will repeat lie. You have to cast to a double otherwise later when you try assign numbers to it it caps them at logical 1s
d = double(diff([0,V])>0)
%// find(diff([0,~V])==-1) - find(diff([0,~V])==1) is the length of each zero cluster
d(find(d(2:end))+1) = find(diff([0,~V])==-1) - find(diff([0,~V])==1)
%// ~~V is the same as V ~= 0
V(cumsum(~~V+d)-1)

Answer 4

El siguiente enfoque simple hace lo que quiere, y probablemente sea muy rápido:

in = [1 0 2 0 7 7 7 0 5 0 0 0 9];
t = cumsum(in~=0);
u = nonzeros(in);
out = u(t).'';

Answer 5

Las operaciones de vectores generalmente suponen independencia de los elementos individuales. Si tiene una dependencia de un artículo anterior, el bucle es la mejor manera de hacerlo.

Algunos antecedentes adicionales sobre matlab: en Matlab, las operaciones son generalmente más rápidas no por las operaciones vectoriales específicamente, sino porque una operación vectorial simplemente hace el ciclo en código C ++ nativo en lugar de hacerlo a través del intérprete.