Pregunta Acelerando Iteraciones- MATLAB


Considera 2 vectores A = [20000000 x 1] y B = [20000000 x 1 ]

Necesitaría encontrar la suma de todas las A correspondientes a cada elemento único de B.

Aunque esto parece realmente fácil, esto está demorando para siempre en MATLAB.

Actualmente, estoy usando

u = unique(B);
length_u = length(u);
C = zeros(length_u,1);

for i = 1:length_u
   C(i,1) = sum(A(B==u(i)));
end

¿Hay alguna forma de hacerlo correr más rápido? Intenté dividir el ciclo y ejecutar 2 parfor bucles utilizando la caja de herramientas de computación paralela (porque tengo solo 2 núcleos). Todavía toma horas.

P.S: Sí, debería obtener una mejor computadora.


7
2018-06-26 07:28


origen


Respuestas:


Debes ver esta respuesta primero.
Si debe, puede usar una combinación de histc y accumarray

A = randi( 500, 1, 100000 );
B = randi( 500, 1, 100000 );

ub = unique( B );

[ignore idx] = histc( B, [ub-.5 ub(end)+.5] );
C = accumarray( idx', A' )';

ver una comparación de juguetes a la ingenua for-loop implementación en ideone.

¿Como funciona?

Usamos el segundo outout de histc para mapear elementos de B (y después A) a los contenedores definidos por los elementos de ub (los elementos únicos de B)
accumarray luego se usa para sumar todas las entradas de A de acuerdo con el mapeo definido por idx.
Nota: Supongo que los elementos únicos de B están separados por al menos 0.5


6
2018-06-26 07:57



Si B contiene solo enteros, puede hacerlo fácilmente en una línea, utilizando el hecho de que sparse agrega elementos con el mismo índice:

C = nonzeros(sparse(B,1,A));

3
2018-06-26 09:04



Mayor simplificación del código sugerido por Shai:

A = randi( 500, 1, 100000 );
B = randi( 500, 1, 100000 );

[~,~,idb] = unique( B );

C = accumarray( idb', A' )';

los "idb" aquí da un vector igual que el de "idx" en el código sugerido por Shai.


3
2018-06-26 10:57



Modifiqué la suma. En lugar de tener que verificar cada elemento, más se ajusta al caso (B==u(i)) o no, ordené la matriz y paré en el momento en que cambió el elemento. Al comenzar la siguiente suma de ese elemento. De esa manera, solo tuve que recorrer cada elemento en A, en lugar de length_u veces. Aquí está el código que utilicé:

A= rand(100000,1);
B= round(rand(100000,1)*25000);
u = unique(B);
length_u = length(u);
C = zeros(length_u,1);
E = zeros(length_u,1);
tic;
for k = 1:length_u
   C(k,1) = sum(A(B==u(k)));
end
t_OP=toc;

tic
D= sortrows([A,B],2);
n=1;
for l=1:numel(u)
    m=n;
    while m<numel(B) && D(m+1,2)==u(l) 
        m=m+1;
    end
    E(l,1) = sum(D(n:m,1));
    n=m+1;
end
t_trial=toc;
display(t_OP)
display(t_trial)

Usé tu código también. El tiempo transcurrido para su código fue: t_OP=10.9398 y para mi modificación: t_trial=0.0962. Espero que esto ayude. Me aseguré de que el código funcionara mediante la construcción sum(E-C) que era 0.
EDITAR: Speedtest
  Lo comparé con @ShaiLa solución también. Esto resultó en

t_OP =

   10.8147
t_trial =

    0.0984
t_Shai =

    0.0154


EDITAR: Comentario de @moarningsun
   En lugar de usar el while-lazo. Puede usar la segunda salida de unique si ordena su matriz antes de construir la suma.

tic
A = randi( 25000, 1, 100000 );
B = randi( 25000, 1, 100000 );
D= sortrows([A',B'],2);
[u, idx] = unique(D(:,2));
idx = [idx; numel(D(:,2))+1];
for l=1:numel(u)
    E(l,1) = sum(D(idx(l):idx(l+1)-1,1));
end
t_trial=toc;

1
2018-06-26 08:18