358069_it-IT

liliconcom

Nearest Neighbor Algorithm: Need Optimization Help

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 a matrici "vicine" a questo dado e calcolerà la mediana e la deviazione standard di alcuni parametri per quel vicinato.

 

Il problema qui è che mentre funziona, richiede molto tempo per essere eseguito durante l'analisi di set di dati con decine di migliaia di righe.

 

Sarei davvero grato se qualcuno potesse fornire indicazioni su come ottimizzare lo script per ridurre il tempo 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;

);

ScriptingOggetto: Algoritmo Nearest Neighbor: Need Optimization Help

Ho ottenuto gli stessi risultati in 11 secondi 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] );
);

mentre anche il tuo codice supera i 13 minuti

Oggetto: Algoritmo Nearest Neighbor: Need Optimization Help

Non ho eseguito alcun benchmarking, ma potrei aspettarmi che l'uso di 'KDTable ()' sarebbe utile per problemi più grandi e più 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 ) ) )
     );