358069_es-ES

liliconcom

Algoritmo de vecino más cercano: necesita ayuda de optimización

Hola a todos,

 

He creado el siguiente script. Está destinado a analizar una tabla de datos donde cada fila corresponde a un chip en una oblea, y cada fila tiene una coordenada (x, y) y algunos parámetros. El script recorrerá cada fila, buscará otras filas que correspondan a matrices que sean "vecinas" de esta matriz y calculará la desviación estándar y media de algún parámetro para esa vecindad.

 

El problema aquí es que mientras funciona, lleva mucho tiempo ejecutarse cuando se analizan conjuntos de datos con decenas de miles de filas.

 

Realmente agradecería si alguien pudiera dar consejos sobre cómo optimizar el script para reducir el tiempo de cálculo.

 

Código a continuación:

dt0 = current data table();
 dt0 << new column("NN_median");
 dt0 << new column("NN_stdev");

for ( i = 1, i <= N Rows(dt0), i++,

 //Find rows corresponding to neighboring dies
 m = dt0[0,{"x", "y"}];
 v = ( abs( m[0,1] - :x[i] ) <= 2 )
  &
  ( abs( m[0,2] - :y[i] ) <= 2 );
 rows = loc(v);
 
 // Create new DT of neighborhood

 dt1 = dt0 << subset( Rows(rows), Columns(:param), invisible );
 
 //Calculate Median and Std Dev
 tb = Tabulate(
  Add Table(
   Column Table( Statistics( Median, Std Dev ) ),
   Row Table( Analysis Columns( column("param") ) )
  )
 );

 dt2 = tb << make into data table( invisible );
 tb << close window;
 
 current data table(dt2);
 placeholder_median = :Median[1];
 placeholder_stdev = :Std Dev[1];
 
 close(dt2, no save);
 close(dt1, no save);
 
 current data table(dt0);
 :NN_median[i] = placeholder_median;
 :NN_stdev[i] = placeholder_stdev;

);

ScriptingRe: algoritmo de vecino más cercano: necesita ayuda de optimización

Obtuve los mismos resultados en 11 segundos usando

dt0 = Current Data Table();
dt0 << New Column( "NN_median" );
dt0 << New Column( "NN_stdev" );
 
m = dt0[0, {"x", "y"}];
For( i = 1, i <= N Rows( dt0 ), i++, 

 //Find rows corresponding to neighboring dies
 
 v = (Abs( m[0, 1] - :x[i] ) <= 2) & (Abs( m[0, 2] - :y[i] ) <= 2);
 rows = Loc( v );
 dt0:NN_stdev[i] = Std Dev( dt0:param[rows] );
 dt0:NN_median[i] = Quantile( .5, dt0:param[rows] );
);

mientras que su código también durante 13 minutos

Re: Algoritmo del vecino más cercano: necesita ayuda para la optimización

Tomemos el conjunto de datos de muestra *) y hagamos algunas evaluaciones comparativas

– comencemos con un ejemplo de cómo NO debes hacerlo…

*) los casos de uso reales son ~ 500 x 500 troqueles y cientos de obleas.

Names Default To Here( 1 );

dt0 = Open( "$SAMPLE_DATA/Wafer Stacked.jmp" );

wait(0);
t0 = hptime();

dt0 << New Column( "row", set each value( Row() ) );

max dist = 1; // just keep the direct neighbors	

// create a lookup table
dtx = As Table( (-21 :: 21)`, <<INVISIBLE></INVISIBLE>

Re: Algoritmo del vecino más cercano: necesita ayuda para la optimización

Names Default To Here( 1 );

dt0 = Open( "$SAMPLE_DATA/Wafer Stacked.jmp" );
wait(0);
	

t0 = hptime();
// get the coordinates
dtLookup = dt0 << Summary(Group( :X_Die, :Y_Die ),output table name( "xyLocations" ), Private);
dtLookup << Delete Columns( :N Rows );

dt0 << New Column( "row", set each value( Row() ) );

max dist = 1; // just keep the direct neighbors	

// create the KDTable 
mat = dtLookup << getAsMatrix;
tbl = KDTable( mat );
dtLookup << New Column( "row_lookup", set each value( Row() ) );

// add column with neighboring rows
Eval (Eval Expr(dtLookup << New Column( "neighbors",Vector,
	Expression,
	set each value(
		{neighbors, dist} = tbl << K nearest rows( 100, Row() );
		neighbors[Where( dist <= Expr(max dist) )];
	)
)));
	
// map the neighbors to the main table
dt0 << Update(
	With( dtLookup ),
	Match Columns( :X_Die = :X_Die, :Y_Die = :Y_Die ),
	Add Columns from Update Table( :row_lookup, :neighbors ),
	Replace Columns in Main Table( None )
);
Close(dtLookup, noSave);
wait(0);
t1=hptime();

//map the rows from the lookup table to the correct rows

// split the table to find the rows faster
// to speed things up, one could do the neighbours averaging here, but that's not the target
mySubsets = dt0 << Subset( By( :Lot, :Wafer ), All rows, Selected columns only( 0 ), Private( 1 ) );

For Each( {myTable}, mySubsets,

// so complicated ?!?!
dthelp= new table("help", add rows(col maximum(myTable:row_lookup)), new column("row_lookup",set each value(row())), private(1));
dthelp << Update(
	With( myTable ),
	Match Columns( :row_lookup = :row_lookup ),
	Add Columns from Update Table( :row ),
	Replace Columns in Main Table( None )
);
	myTable:neighbors << set each value(
		input = :neighbors; // take the neighbors from the lookup table 
		Transform each({row},input, dthelp[row,"row"]);
		);
	close(dthelp, noSave)
);

//merge the subsets and map the neighbors back to the main table 
tmp = mySubsets[1] << Concatenate( mySubsets[2 :: N Items( mySubsets )], Private() );
For Each( {myTable}, mySubsets, Close( myTable, noSave ) );
dt0 << Delete Columns( :neighbors );
dt0 << Update(
	With( tmp ),
	Match Columns( :Lot = :Lot, :Wafer = :Wafer, :X_Die = :X_Die, :Y_Die = :Y_Die ),
	Add Columns from Update Table( :neighbors ),
	Replace Columns in Main Table( None )
);
Close( tmp, noSave );

wait(0);
t2= hptime();

// now use the cool new column 
dt0 << New Column( "Defects average", Formula( Mean( :Defects[:neighbors] ) ) );
wait(0);
t3=hptime();

print("create lookup", (t1-t0)/1000000);
print("correct the rows", (t2-t1)/1000000);
print("calculate neighbor average", (t3-t2)/1000000);