870994_es-ES

liliconcom

VConcat muchas matrices juntas

La concatenación de matrices en un bucle se vuelve más lenta con las iteraciones del bucle.

Por ejemplo este pseudocódigo:

OutputM = [];
for( i=1, i<=N, i++,
  // do some calculations, generate a matrix of results, call it,  ThisM
  OutputM  |/ = ThisM
);

Si hago lo anterior, entonces a medida que N aumenta, la línea VConcat se vuelve cada vez más lenta con cada iteración.

Tenga en cuenta que cada iteración produce una matriz con el mismo número de columnas, pero un número variable de filas.

Es mucho más rápido hacer esto:

OutputList = {}; // will be a list of matrices
for( i=1, i<=N, i++,
  // do some calculations, generate a matrix of results, call it,  ThisM
  insertinto(OutputList, ThisM)
);

Ahora queremos concatenar juntas la lista de matrices que hemos generado.

La pregunta es ¿cómo?

//This doesn't work:
VConcat(OutputMList);
// Neither does this :
VConat(Eval List(OutputMList);
// Nor this:
VConcat(Eval list(Eval(OutputMList);
// I know I can concat multiple matrices, for example this works:
VConat(OutputMList[1],OutputMList[2], OutputMList[3]);
// But the desire is to generalize this

Automatización y scriptingRe: VConcat muchas matrices juntas

No tengo tiempo para comprobar esta idea, pero podría ser más rápido concatenar listas y luego convertir la lista final en matriz.

Re: VConcat muchas matrices juntas

Esto podría contener algunos consejos sobre matrices, Guía de scripts > Scripts eficientes > Usar matrices

Re: VConcat muchas matrices juntas

Esto parece funcionar rápido para mí.

OutputList = {}; // will be a list of matrices
n=50;
for( i=1, i<=N, i++,
  // do some calculations, generate a matrix of results, call it,  ThisM
  ThisM = [1,2,3];
  insertinto(OutputList, ThisM)
);
OutputM = [];
for each({l},OutputList,
OutputM  = OutputM |/  matrix(l);
);

Re: VConcat muchas matrices juntas

Si está concatenando 50 o más, quizás no le convenga usar un bucle para concatenarlos uno a uno. Si ya tiene una lista de matrices para concatenar, puede convertirla en una función vconcat como esta:

	Substitute Into( OutputList, {}, Expr( vconcat ) ); // convert {a,b,c} -> vconcat(a,b,c)
	result2 = Eval( OutputList ); // evaluate the expression

La evaluación puede ser 10 veces más rápida que el bucle:

JSL para hacer el gráfico:

dt = New Table( "timecat", New Column( "nmats" ), New Column( "timeloop" ), New Column( "timeeval" ) );
dt << Graph Builder( Size( 534, 456 ), Show Control Panel( 0 ),
	Variables( X( :nmats ), Y( :timeloop ), Y( :timeeval, Position( 1 ) ) ),
	Elements( Points( X, Y( 1 ), Y( 2 ), Legend( 3 ) ) ),
	SendToReport( Dispatch( {}, "timeloop", ScaleBox,
		{Scale( "Log" ), Format( "Engineering SI", 9, 0 ), Min( 10 ), Max( 1e7 ), Inc( 1 ), Minor Ticks( 1 ),
		Add Ref Line( 1e5, "Solid", "Black", "1/10 second", 1 ), Add Ref Line( 1e6, "Solid", "Black", "one second", 1 ),
		Label Row( Show Minor Labels( 0 ) )} ),
		Dispatch( {}, "graph title", TextEditBox, {Set Text( "smaller is better" )} ),
		Dispatch( {}, "X title", TextEditBox, {Set Text( "number of vconcats" )} ),
		Dispatch( {}, "Y title", TextEditBox, {Set Text( "microseconds" )} )
	)
);

For( N = 1, N < 550, N = Ceiling( n * 1.2 ), // build a bunch of test sets of bigger and bigger sizes
	OutputList = {}; // will be a list of matrices
	For( i = 1, i <= N + 1, i++, 
  // do some calculations, generate a matrix of results, call it,  ThisM
		ThisM = J( i, 30, i ); // rows, cols, initial value. 
		Insert Into( OutputList, ThisM );
	);
// loop is slower ... blue in graph
	start = HP Time();
	result1 = OutputList[1];
	For( i = 2, i <= N Items( OutputList ), i += 1,
		result1 |/= OutputList[i]; // this is the vconcat into operator
	);
	t1 = HP Time() - start;
// eval is faster ... red in graph
	start = HP Time();
	Substitute Into( OutputList, {}, Expr( vconcat ) ); // convert {a,b,c} -> vconcat(a,b,c)
	result2 = Eval( OutputList ); // evaluate the expression
	t2 = HP Time() - start;
// capture the timings
	dt << addrows( 1 );
	dt:nmats[N Rows( dt )] = N;
	dt:timeloop[N Rows( dt )] = t1;
	dt:timeeval[N Rows( dt )] = t2;
	If( !All( result1 == result2 ),
		Throw( "bug?" ) // they should be identical
	);
	Wait( .1 ); // watch the graph grow
);

Re: VConcat muchas matrices juntas

¡Gracias! Esa es la "salsa mágica" que necesitaba.

Concuerdo en que la iteración del bucle se ralentizará para números grandes, es una buena demostración de ello.

La sintaxis 'Substitute Into()' es lo que me había estado perdiendo

Re: VConcat muchas matrices juntas

Reelaboré el gráfico para observar el comportamiento O(N) y añadí un bucle JSL que también lo logra. Las curvas roja, verde y azul ahora miden el tiempo por fila concatenada. Las curvas roja y verde se estabilizan en torno a 0,3 µs/fila, pero la curva azul se vuelve cada vez más lenta por fila copiada para problemas cada vez más graves, ya que el bucle azul vuelve a copiar todos los datos previamente copiados (y reasigna la matriz) por cada matriz añadida al resultado. El último punto azul representa 180 µs * 3,8 millones de filas, o 11 minutos. Los puntos rojo y verde son aproximadamente 200 veces más rápidos.

dt = New Table( "timecat", New Column( "nmats" ), New Column( "loop" ), New Column( "eval" ), New Column( "copy" ) );
dt << Graph Builder( Size( 1000, 500 ), Show Control Panel( 0 ), Legend Position( "Inside Left" ),
	Variables( X( :nmats ), Y( :loop ), Y( :eval, Position( 1 ) ), Y( :copy, Position( 1 ) ) ),
	Elements( Points( X, Y( 1 ), Y( 2 ), Y( 3 ), Legend( 3 ) ) ),
	SendToReport( Dispatch( {}, "loop", ScaleBox,
			{Scale( "Log" ), Format( "Best", 6 ), Min( 0.1 ), Max( 100 ), Inc( 1 ), Minor Ticks( 1 ), Add Ref Line( 0.2, "Solid", "Black", ".2", 1 ),
			Add Ref Line( 0.4, "Solid", "Black", ".4", 1 ), Label Row( Show Minor Labels( 0 ) )} ),
		Dispatch( {}, "graph title", TextEditBox, {Set Text( "smaller is better" )} ),
		Dispatch( {}, "X title", TextEditBox, {Set Text( "number of concats" )} ),
		Dispatch( {}, "Y title", TextEditBox, {Set Text( "microseconds / row" )} ) ) );
		
For( N = 1, N < 3000, N = Ceiling( n * 1.2 ), // build a bunch of test sets of bigger and bigger sizes
	result1 = result2 = result3 = .; // clear previous run memory, if any
	OutputList = {}; // will be a list of matrices
	For( i = 1, i <= N + 1, i++, 
  // do some calculations, generate a matrix of results, call it,  ThisM
		ThisM = J( i, 30, i ); // rows, cols, initial value. 30 makes this demo run in a reasonable time.
		Insert Into( OutputList, ThisM );
	);
// copy... fastest, green in graph, O(N) behavior. Use the red eval below because it is simpler?
	start = HP Time();
	// find total rows and pre-allocate
	nr = 0;
	nc = N Cols( OutputList[1] );
	For( i = 1, i <= N Items( OutputList ), i += 1,
		nr += N Rows( OutputList[i] );
		If( nc != N Cols( OutputList[i] ),
			Throw( "bad cols" )
		);
	);
	result3 = J( nr, nc, . ); // allocate the result, exactly one time
	nr = 0;
	For( i = 1, i <= N Items( OutputList ), i += 1,
		result3[nr + 1 :: nr + N Rows( OutputList[i] ), 0] = OutputList[i]; // copy pieces into the pre-allocated result
		nr += N Rows( OutputList[i] ); // position the next piece after this one
	);
	t3 = HP Time() - start;
// loop is slower ... blue in graph. This exhibits terrible O(N^2) behavior--reallocates the result bigger and bigger
	start = HP Time();
	result1 = OutputList[1];
	For( i = 2, i <= N Items( OutputList ), i += 1,
		result1 |/= OutputList[i]; // this is the vconcat into operator. copies all the previous data into a bigger mat, each time.
	);
	t1 = HP Time() - start;
// eval is faster ... red in graph ... last, because OutputList is modified. Easier than the green copy and same O(N) result.
	start = HP Time();
	Substitute Into( OutputList, {}, Expr( vconcat ) ); // convert {a,b,c} -> vconcat(a,b,c)
	result2 = Eval( OutputList ); // evaluate the expression
	t2 = HP Time() - start;

// capture the timings
	dt << addrows( 1 );
	dt:nmats[N Rows( dt )] = N;
	dt:loop[N Rows( dt )] = t1 / N Rows( result1 );
	dt:eval[N Rows( dt )] = t2 / N Rows( result2 );
	dt:copy[N Rows( dt )] = t3 / N Rows( result3 );
	If( !All( result1 == result2 ) | !All( result1 == result3 ) | !(N Rows( result1 ) == N Rows( result2 ) == N Rows( result3 )),
		Throw( "bug?" ) // they should be identical
	);
	Wait( .1 ); // watch the graph grow
);