Ricerca di array multidimensionali vs ricerca di array flat con il calcolo

Question

Durante simulazioni Monte-Carlo (MC) su un latice di dimensioni $(L_1,L_2,\ldots,L_D)$, tutte le variabili del sito sono spesso archiviate come file$D$matrice dimensionale array. Per cercare un sito varibale, è sufficiente il file$D$dim. coord coord.

Ad esempio, su un reticolo 2 D, può essere creato un array 2 D in cui ogni elemento è una variabile del sito (la dimensione o la natura della variabile del sito stessa è irrilevante). Per cercare una variabile in coord={x,y}uno degli usi,Extract[array,coord]

Spesso la simulazione viene eseguita in sweep. Ogni sweep comprende$N=L_1L_2\ldots L_D$ ricerche casuali sull'array.

Si tratta di molte ricerche, soprattutto quando una simulazione può avere un numero elevato di sweep.

Poiché la memoria viene infine archiviata come un array piatto sequenziale, potrebbe essere meglio eseguire le ricerche su un array piatto.

flatArray=Flatten@array

Ora una ricerca è più semplice

flatArray[position]

Come prima $N$ posizioni casuali vengono generate per scansione.

1. È corretto? Le ricerche di array flat sono più veloci di quelle annidate? (per il caso di prova, prendi$D=3$ su a $48\times 48\times48$ reticolo)

Tuttavia, per la matrice appiattita, la struttura reticolare viene persa. Per eseguire calcoli che richiedono quella struttura, è necessaria la coordinata del sito nel reticolo. Anche se questo può essere calcolato ogni volta, si potrebbe anche fare una ricerca.

allCords=Flatten[Array[{##}&,{L1,L2,...,LD}],D-1]
toCoord[pos_]:=allCoords[[pos]]

1. È corretto presumere che il calcolo del coord sia più lento della ricerca del coord? Tieni presente che il calcolo è per un generale$D$.

2. Con questo requisito di aver bisogno anche del coord reticolo (tramite calcolo o ricerca), la risposta a 1. è sempre la stessa?

Supponiamo in quanto sopra che la memoria sia economica ma dispendiosa in termini di tempo.

Answer 1

Per prima cosa lasciatemi dire che potrebbe valere la pena usarlo al Partposto di Extract. Ma questo potrebbe richiedere il refactoring del codice e potrebbe portare a battute d'arresto in altri luoghi. Se i tuoi indici casuali si presentano come indici tripli, allora Extractè una buona scelta. Ma se puoi generare direttamente gli indici lineari, allora Partpotrebbe essere una scelta migliore:

n = 48;
m = 1000000;
A = RandomReal[{-1, 1}, {n, n, n}];
a = Flatten[A];

r1 = Extract[A, RandomInteger[{1, n}, {m, 3}]]; // RepeatedTiming // First
r2 = Part[a, RandomInteger[{1, n^3}, {m}]]; // RepeatedTiming // First

0.027

0.011

Potrebbe anche essere utile saltare la generazione degli indici utilizzando RandomChoice:

r3 = RandomChoice[a, m]; // RepeatedTiming // First

0.0092

Tuttavia, questo renderebbe impossibile accedere alle coordinate del reticolo, quindi probabilmente non è quello che stai cercando.

In 1: gli array compressi di Mathematica sono davvero elenchi semplici con la ricerca annidata implementata esattamente come suggerisci. Quindi fondamentalmente non dovrebbe esserci alcuna differenza tra una chiamata di memoria piatta con Partcui si calcola l'indice lineare dalle coordinate a mano o se si esegue una chiamata di memoria annidata (e lasciare che Mathematica faccia il calcolo dell'indice lineare dalle coordinate). Ovviamente, in pratica, possono comunque esserci delle lievi differenze nelle prestazioni (ad esempio, Mathematica esegue anche alcuni controlli di sicurezza che richiedono più tempo o esegue un caching intelligente che potrebbe velocizzare un po 'le cose). In genere, quando eseguo Compileil codice e uso Compile`GetElementinvece diPart per le chiamate di memoria, l'uso dell'indicizzazione lineare o annidata fa poca differenza.

At 2 .: Come già saprai, le ricerche in memoria tendono ad essere più dispendiose in termini di tempo rispetto ai calcoli in interi e float macchina (doppi), a causa dei ritardi di memoria e della larghezza di banda limitata. (Lo sviluppo della memoria non ha tenuto traccia dello sviluppo delle CPU negli ultimi due anni.) Quindi , a volte , vale la pena ricalcolare qualcosa con i dati che sono già presenti invece di dover attendere il risultato di una chiamata di memoria . In generale, è sufficiente provare diverse implementazioni alternative per trovare quella che funziona meglio sulla classe di problemi che si desidera risolvere.

At 3 .: Se vuoi davvero seguire quella strada, ti suggerirei di usare Quotiente Modcalcolare le coordinate reticolari da indici lineari. (Si può anche usare IntegerDigits(con MixedRadix, se le dimensioni dell'array non sono tutte uguali), ma sembra essere meno performante.) La risposta completa dipende molto da quanto sono grandi le tabelle di ricerca (ad esempio, se porterebbero a frequenti cache mancate).

Come osservazione finale, lasciatemi dire che Mathematica è un linguaggio multiuso e di alto livello. Non è pensato e non è in grado di produrre codice ad alte prestazioni possibilmente ottimizzato. Ma Mathematica compensa accelerando parecchio la prototipazione. Quindi, se devi risolvere un problema legato alla memoria e se devi farlo il più velocemente possibile, a un certo punto dovresti considerare di portare il tuo algoritmo su linguaggi più vicini alla macchina, ad esempio C, C ++ o FORTRAN.