870994_fr-FR

liliconcom

VConcat plusieurs matrices ensemble

La concaténation de matrices dans une boucle ralentit avec les itérations de boucle.

Par exemple ce pseudo-code :

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

Si je fais ce qui précède, alors à mesure que N augmente, la ligne VConcat devient de plus en plus lente à chaque itération.

Notez que chaque itération produit une matrice avec le même nombre de colonnes, mais un nombre variable de lignes.

C'est beaucoup plus rapide de faire ceci :

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

Nous voulons maintenant concaténer la liste des matrices que nous avons générées.

La question est comment ?

//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

Automatisation et scriptsRe: VConcat plusieurs matrices ensemble

Je n'ai pas le temps de vérifier cette idée, mais il pourrait être plus rapide de concaténer des listes puis de convertir la liste finale en matrice.

Re: VConcat plusieurs matrices ensemble

Ceci peut contenir quelques conseils concernant les matrices, Guide de script > Scripts efficaces > Utiliser des matrices

Re: VConcat plusieurs matrices ensemble

Cela semble fonctionner rapidement pour moi

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 plusieurs matrices ensemble

Si vous concaténez 50 objets ou plus, il est préférable d'éviter d'utiliser une boucle pour les concaténer un par un. Si vous disposez déjà d'une liste de mats à concaténer, vous pouvez la transformer en une fonction vconcat comme celle-ci :

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

L'évaluation peut être 10 fois plus rapide que la boucle :

JSL pour faire le graphique :

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 plusieurs matrices ensemble

Merci ! C'est la « sauce magique » dont j'avais besoin.

Convenez que l'itération de la boucle ralentira pour des nombres plus grands, c'est une belle démonstration de cela.

La syntaxe « Substitute Into() » est ce qui me manquait

Re: VConcat plusieurs matrices ensemble

J'ai retravaillé le graphique pour observer le comportement O(N) et ajouté une boucle JSL qui permet également d'obtenir ce comportement. Les courbes rouge, verte et bleue mesurent désormais le temps par ligne concaténée. Les courbes rouge et verte se stabilisent autour de 0,3 µs/ligne, mais la courbe bleue ralentit de plus en plus à chaque ligne copiée pour des problèmes de plus en plus complexes, car la boucle bleue recopie toutes les données précédemment copiées (et réaffecte la matrice) pour chaque matrice ajoutée au résultat. Le dernier point bleu représente 180 µs * 3,8 M de lignes, soit 11 minutes. Les points rouges et verts sont environ 200 fois plus rapides.

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