358069_it-IT

liliconcom

Algoritmo del vicino più vicino: serve aiuto per l'ottimizzazione

Ciao a tutti,

 

Ho creato il seguente script. Ha lo scopo di analizzare una tabella di dati in cui ogni riga corrisponde a un chip in un wafer e ogni riga ha una coordinata (x,y) e alcuni parametri. Lo script esaminerà ogni riga, cercherà altre righe che corrispondono ai dadi "vicini" a questo dado e calcolerà la mediana e la deviazione standard di alcuni parametri per quel quartiere.

 

Il problema qui è che, sebbene funzioni, richiede molto tempo per l'esecuzione durante l'analisi di set di dati con decine di migliaia di righe.

 

Apprezzerei davvero se qualcuno potesse fornire indicazioni su come ottimizzare lo script per ridurre i tempi di calcolo.

 

Codice qui sotto:

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;

);

Modellazione statistica avanzataAutomazione e scriptingRicerche sui consumatori e sul mercatoPersonalizzazione di massaIngegneria della qualità e dei processiRe: Algoritmo del vicino più vicino: è necessario aiuto per l'ottimizzazione

Grazie! Man mano che procedo, sto imparando la sintassi degli script JMP. Il tuo codice sicuramente ignora alcune operazioni non necessarie.

Re: Algoritmo del vicino più vicino: è necessario aiuto per l'ottimizzazione

Non ho eseguito alcun benchmarking, ma potrei aspettarmi che l'utilizzo di "KDTable()" sia utile per problemi più ampi e generali:

Names Default To Here( 1 );

n = 100;  // Size of square

// Make a table of x and y locations
dtx = AsTable((1::n)`, << Invisible);
dty = AsTable((1::n)`, << Invisible);
dt = dty << Join( With( dtx ), Cartesian Join );
Close(dtx, NoSave);
Close(dty, NoSave);
Column(dt, 1) << setName("x");
Column(dt, 2) << setName("y");
dt << deleteProperty("Source");
dt << setName("xy Locations");

// Put these locations into a matrix
mat = dt << getAsMatrix;
tbl = KDTable( mat );

// Pick a point in the interior, so we don't need to decide on any boundary conditions
myX = RandomInteger(2, n-1);
myY = RandomInteger(2, n-1);
myRow = Loc(mat[0, 1] == myX & mat[0, 2] == myY);
myRow = myRow[1];

// Find the 8 nearest neighbours to the chosen point
{rows, dist} = tbl << K nearest rows( 8, myRow ); 
Show( myRow, rows );

// Check it worked
myXvals = Column(dt, "x")[myRow];
myYvals = Column(dt, "y")[myRow];
dt << NewColumn("Distance", Numeric, Continuous, Formula(sqrt((:x - myXvals)^2 +(:y - myYvals)^2)));
dt << selectRows(VConcat(myRow, rows`));
gb = dt << Graph Builder(
      Size( 529, 453 ),
      Show Control Panel( 0 ),
      Variables( X( :x ), Y( :y ), Color( :Distance ) ),
      Elements( Points( X, Y, Legend( 5 ) ) )
     );

 

Re: Algoritmo del vicino più vicino: è necessario aiuto per l'ottimizzazione

Ho ottenuto gli stessi risultati in 11 secondi utilizzando

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

mentre anche il tuo codice dura più di 13 minuti

Re: Algoritmo del vicino più vicino: è necessario aiuto per l'ottimizzazione

Prendiamo il set di dati di esempio *) e facciamo qualche benchmark

- iniziamo con un esempio di come NON dovresti farlo...

*) i casi d'uso effettivi sono circa 500 x 500 matrici e centinaia di wafer.

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 vicino più vicino: è necessario aiuto per l'ottimizzazione

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