differenza di velocità nel fare una tabella

Question

Stavo leggendo a useful post at WRI blog on improving speed of code, e ho bisogno di aiuto per capire questo.

confrontare questi costi

Timing[ 
tbl = Table[i + j, {i, 1, 1000}, {j, 1, 1000}];  
] 

{0.031, Null} 

e

Timing[ 
a = 1000; 
tbl = Table[i + j, {i, 1, a}, {j, 1, a}]; 
] 

{0.422, Null} 

Quindi è molto più veloce quando mettere il valore effettivo per il limite all'interno della tabella stessa vs esterno. La spiegazione per questo, che sono sicuro sia corretta, ma ho bisogno di aiuto nella comprensione, è che Table è compilato se il suo limite è numerico o no, questo perché i suoi Attributi sono HoldAll.

Ma la mia domanda è: come funzionerebbe il precedente, perché i limiti a Table devono, a un certo punto, diventare comunque numerici? Non riesco a scrivere

Clear[a] 
tbl = Table[i + j, {i, 1, a}, {j, 1, a}] 

Quanto sopra dà un errore.

Quindi, per me, la scrittura a=1000 fuori Table vs interno, dovrebbe aver fatto alcuna differenza, poiché senza a avere un valore numerico, Table[] non possono fare nulla. Quindi la sostituzione di a con il numero 1000 deve avvenire in un punto dal valutatore prima che lo Table[] possa fare qualcosa di utile, non sarebbe?

In altre parole, quello che Table dovrebbe vedere, alla fine, è {i, 1, 1000}, {j, 1, 1000} in entrambi i casi.

Quindi, il modo in cui ho pensato che questo sarebbe accaduto è questo:

1. Evaluator sostituisce a per 1000 negli argomenti della tavola
2. Evaluator chiama Table con il risultato, che è ora tutto numerica.
3. Tabella Compila e ora è più veloce.

Ma quello che sembra succedere è qualcos'altro. (a causa di HoldAll?)

1. La tabella prende i suoi argomenti, così com'è. Poiché ha HoldAll, quindi vede a e non 1000.
2. Non chiama Compile poiché i suoi argomenti non sono tutti i numeri.
3. Ora generare una tabella con il limite a, valutatore restituisce a a 1000
4. Tabella viene generato adesso tutti i limiti sono numerici, ma più lento ora poiché il codice non viene compilato.

La domanda è: cosa succede sopra? Qualcuno potrebbe spiegare i passi che sarebbero accaduti per spiegare questa differenza nei tempi?

Inoltre, come si potrebbe assicurare che la tabella è stata compilata in entrambi i casi nell'esempio precedente, anche se si utilizza una variabile per il limite?Non è sempre possibile codificare i numeri per i limiti del tavolo, ma a volte si deve usare una variabile per questi. Si dovrebbe usare esplicitamente il comando Compile? (Non uso direttamente lo Compile, poiché presumo che venga eseguito automaticamente quando necessario).

di modifica (1)

In risposta al post di Mike in basso a trovare alcuna differenza nei tempi quando si utilizza una chiamata.

ClearAll[tblFunc]; 
Timing[a = 1000; 
tblFunc[a_] := Table[i + j, {i, 1, a}, {j, 1, a}]; 
Developer`PackedArrayQ[tblFunc[a]] 
] 

dà

{0.031, True} 

Ma questo è perché a è ora il numero 1000 all'interno della funzione, una volta che è chiamato. Poiché M passa le cose per VALUE.

Se si forza la chiamata ad essere per riferimento, in modo che a è lasciato non valutata, allora otteniamo

ClearAll[tblFunc]; 
Timing[a = 1000; 
tblFunc[a_] := Table[i + j, {i, 1, a}, {j, 1, a}]; 
Developer`PackedArrayQ[tblFunc[Unevaluated@a]] 
] 

ora vediamo il risultato atteso, dal momento che ora a è ancora simbolica all'interno della funzione, siamo torna al punto di partenza, e ora è lento, dal momento che non è imballato. E poiché non è impacchettato, Compile non viene utilizzato.

{0.437, False} 

modifica (2) Grazie a tutti per le risposte, penso che ho imparato da loro assegnare.

Ecco un riepilogo esecutivo, solo per essere sicuro di avere tutto ok.

modifica (3)

Ecco i link che ho particolarmente legati alla suggerimenti da utilizzare per rendere il codice di Mathematica corre più veloce.

1. http://library.wolfram.com/howtos/faster/
2. http://blog.wolfram.com/2011/12/07/10-tips-for-writing-fast-mathematica-code/
3. https://stackoverflow.com/questions/4721171/performance-tuning-in-mathematica
4. Using Array and Table Functions in Mathematica. Which is best when

Answer 1

Quindi questo è quello che penso sta accadendo. Il motivo per cui viene visualizzato il rallentamento tra un limite numerico e un limite simbolico su Table è dovuto al fatto che si esegue un doppio indice. Ogni sotto-tabella (ad esempio, passando sopra tutti gli indici j per un indice fisso i) viene costruita separatamente e quando il limite è simbolico, vi è un ulteriore passaggio nel determinare quel limite prima di costruire ciascun sottotabella. Puoi vedere questo esaminando, ad es.

Trace[a = 3; 
     tbl = Table[i + j, {i, 1, a}, {j, 1, a}]; 
    ] 

David dà un buon esempio per il motivo per cui si vorrebbe fare questo controllo per ogni lista sub. Sul perché Mathematica non riesco a capire quando questo controllo non è necessario Non ho idea.Se si dispone di un solo indice per riassumere sopra non v'è alcuna differenza di velocità tra la versione simbolica e numerica

Timing[tbl = Table[i + j, {j, 1, 1000}];] 
{0.0012, Null} 

Timing[a = 1000; 
     tbl = Table[i + j, {j, 1, a}]; 
     ] 
{0.0013, Null} 

Per rispondere alla tua follow-up per quanto riguarda la velocità; rendendo tbl una funzione è più veloce sia per i limiti numerici che simbolici.

Timing[a = 1000; 
     tblFunc[a_] := Table[i + j, {i, 1, a}, {j, 1, a}]; 
     tblFunc[a]; 
     ] 

{0.045171, Null} 

vs.

Timing[tbl = Table[i + j, {i, 1, 1000}, {j, 1, 1000}];] 
{0.066864, Null} 

Timing[a = 1000; 
     tbl = Table[i + j, {i, 1, a}, {j, 1, a}]; 
     ] 
{0.632128, Null} 

Si guadagna ancora di più velocità, se si ha intenzione di riutilizzare la costruzione tbl.

Answer 2

Le cose principali da monitorare, come altri hanno menzionato, sono il riempimento e la lunghezza dell'elenco. Io in realtà non vedo le differenze che Timo riporta:

ClearAll[tblFunc]; 
Timing[a = 1000; 
tblFunc[a_] := Table[i + j, {i, 1, a}, {j, 1, a}]; 
Developer`PackedArrayQ[tblFunc[a]]] 

{0.077706, True} 

vs 

ClearAll[tbl]; 
Timing[ 
tbl = Table[i + j, {i, 1, 1000}, {j, 1, 1000}]; 
Developer`PackedArrayQ[tbl]] 

{0.076661, True} 

ClearAll[tbl]; 
Timing[a = 1000; 
tbl = Table[i + j, {i, 1, a}, {j, 1, a}]; 
Developer`PackedArrayQ[tbl]] 

{1.02879, False} 

Quindi per me l'unica differenza è che se l'elenco è pieno. Che si tratti di una funzione non fa differenza per i tempi sul mio set up. E come previsto quando si spegne autocompilation i tempi sono gli stessi per tutto quanto sopra, perché non si verifica alcun imballaggio:

SetSystemOptions["CompileOptions" -> {"TableCompileLength" -> Infinity}]; 

{1.05084, False} 

vs 

{1.00348, False} 

{1.01537, False} 

ripristinare la lunghezza della tabella di autocompilazione:

SetSystemOptions["CompileOptions" -> {"TableCompileLength" -> 250}] 

Answer 3

Questo è un po 'OT, ma per velocità qui si potrebbe desiderare di evitare l'utilizzo dell'elaborazione articolo per articolo implicita nell'uso di Table. Piuttosto, usa Esterno. Ecco cosa vedo sul mio sistema:

Timing[Outer[Plus, Range[5000], Range[5000]];] 
{0.066763,Null} 

    Timing[Table[i + j, {i, 1, 5000}, {j, 1, 5000}];] 
{0.555197,Null} 

Una differenza drammatica.