Confronto delle prestazioni dell'array di array rispetto agli array multidimensionali

Question

Quando stavo usando il C++ al college, mi è stato detto di usare matrici multidimensionali (con la presente MDA) quando possibile, poiché mostra una migliore localizzazione di memoria dato che è allocata in una grande porzione. Le matrici di array (AoA), d'altra parte, sono allocate in più blocchi più piccoli, eventualmente sparsi ovunque nella memoria fisica in cui vengono trovati i posti vacanti.

Quindi immagino che la prima domanda sia: è un mito, o è un consiglio che vale la pena seguire?

Supponendo che sia il secondo, la prossima domanda sarebbe cosa fare in un linguaggio come Java che non ha un vero MDA. Non è così difficile emulare la MDA con un 1DA, naturalmente. Essenzialmente, ciò che è lo zucchero sintattico per le lingue con MDA può essere implementato come supporto di libreria per le lingue senza MDA.

Vale la pena? Questo è un livello troppo basso di un problema di ottimizzazione per un linguaggio come Java? Dovremmo semplicemente abbandonare gli array e usare List s anche per i primitivi?

---

Un'altra domanda: in Java, non allocazione AoA contemporaneamente (new int[M][N]) eventualmente produrre un'allocazione di memoria diverso che farlo gerarchicamente (new int[M][]; for (... new int[N])?

Answer 1

Java e C# allocano la memoria in modo molto diverso da C++. In effetti, in .NET sicuramente tutti gli array di AoA saranno vicini tra loro se vengono allocati uno dopo l'altro perché la memoria contiene un solo blocco continuo senza alcuna frammentazione.

Ma è ancora vero per C++ e ha ancora senso se si desidera la massima velocità. Anche se non dovresti seguire questo consiglio ogni volta che vuoi un array multidimensionale, dovresti scrivere prima il codice gestibile e poi definirlo se è lento, l'ottimizzazione prematura è la radice di tutto il male in questo mondo.

Answer 2

Non vorrei perdere l'impegno di utilizzare un array 1D come array multidim in Java perché non esiste alcuna sintassi per aiutare. Naturalmente si potrebbero definire funzioni (metodi) per nascondere il lavoro per voi, ma si finisce semplicemente con una chiamata di funzione invece di seguire un puntatore quando si utilizza una matrice di matrici. Anche se il compilatore/interprete accelera questo per te, non penso che valga la pena. Inoltre, è possibile incorrere in complicazioni quando si tenta di utilizzare un codice che prevede array 2D (o N-Dim) che si aspettano da matrici di array. Sono sicuro che la maggior parte del codice generale verrà scritto per array come questo in Java. Inoltre si può riassegnare a buon mercato righe (o colonne se si decide di pensare in questo modo).

Se si sa che questo array multidim è un collo di bottiglia, è possibile ignorare ciò che ho detto e vedere se l'ottimizzazione manuale aiuta.

Answer 3

Ne vale la pena? Questo è un livello troppo basso di un problema di ottimizzazione per un linguaggio come Java?

In generale, non ne vale la pena. La migliore strategia per dimenticare questo problema nella prima versione della tua applicazione e implementarlo in modo diretto (cioè facile da gestire). Se la prima versione viene eseguita troppo lentamente per i requisiti, utilizzare uno strumento di profilatura per individuare i colli di bottiglia dell'applicazione. Se la profilazione suggerisce che gli array di array sono probabilmente il problema, fai qualche esperimento per cambiare le tue strutture dati in matrici e profili multidimensionali simulati, per vedere se fa una differenza significativa. [Sospetto che non farà molta differenza. Ma la cosa più importante è non perdere tempo a ottimizzare qualcosa inutilmente.]

Dovremmo semplicemente abbandonare gli array e utilizzare le liste anche per i primitivi?

Non andrei così lontano. Supponendo che avete a che fare con le matrici di una dimensione predeterminata:

• array di oggetti sarà un po 'più veloce di liste equivalenti di oggetti, e
• array di primitive sarà notevolmente più veloce e prendere molto meno spazio rispetto equivalente liste di wrapper primitivi.

D'altra parte, se l'applicazione deve "aumentare" gli array, l'utilizzo di un elenco semplifica il codice.

Answer 4

Dall'esperienza personale in Java, gli array multidimensionali sono molto più lenti di un array dimensionale se si carica una grande quantità di dati o si accede agli elementi nei dati che si trovano in posizioni diverse. Ho scritto un programma che ha scattato un'immagine di schermata in formato BMP e poi cercato lo screenshot per un'immagine più piccola. Caricare l'immagine dello screenshot (circa 3 mb) in una matrice multidimensionale (tridimensionale, [xPos] [yPos] [colore] (con colore = 0 come valore rosso e così via)) ha impiegato 14 secondi. Per caricarlo in un array monodimensionale sono necessari 1 secondo. Il guadagno per trovare l'immagine più piccola nell'immagine più grande era simile. Sono occorsi circa 28 secondi per trovare l'immagine più piccola nell'immagine più grande quando entrambe le immagini sono state memorizzate come array multidimensionali. Ci sono voluti circa un secondo per trovare l'immagine più piccola nell'immagine più grande quando entrambe le immagini sono state memorizzate come array monodimensionali. Detto questo, in primo luogo ho scritto il mio programma utilizzando un array dimensionale per motivi di leggibilità.