Domanda Copiare array di vector

[fennek]

Se mi posso permette un consiglio che ti risolve anche il problema della deep copy, e aumenta le prestazioni: non fare array innestati, fallo di profondità uno.

Per esempio, partiamo dalla tua tabella, di dimensione X (3), Y (9), Z(10).
Fai che table sia un array di dimensione 270 (X*Y*Z).

Per accedere all'elemento k, j, n, dovrai accedere table[k * Y * Z + j * Z + n]

Le performance aumentano alla lettura perché hai un solo array di 270 elementi contigui in memoria, invece che 27 da 10. Inoltre, sarai sicuro che tutto l'array sia in cache (L1/L2/L3), invece che solo alcuni degli array. E spostarsi dentro l'array diventa solo uno shift del puntatore di massimo 270 * size del contenuto, invece che saltare avanti e indietro in praticamente tutta la memoria.

Comunque, se ti interessa l'argomento, internet parla tanto di multidimensional array vs flat array ;-)

E, incidentalmente, risolve il tuo problema

 

[DispatchCode]

Se mi posso permette un consiglio che ti risolve anche il problema della deep copy, e aumenta le prestazioni: non fare array innestati, fallo di profondità uno.

Per esempio, partiamo dalla tua tabella, di dimensione X (3), Y (9), Z(10).
Fai che table sia un array di dimensione 270 (X*Y*Z).

Per accedere all'elemento k, j, n, dovrai accedere table[k * Y * Z + j * Z + n]

Le performance aumentano alla lettura perché hai un solo array di 270 elementi contigui in memoria, invece che 27 da 10. Inoltre, sarai sicuro che tutto l'array sia in cache (L1/L2/L3), invece che solo alcuni degli array. E spostarsi dentro l'array diventa solo uno shift del puntatore di massimo 270 * size del contenuto, invece che saltare avanti e indietro in praticamente tutta la memoria.

Comunque, se ti interessa l'argomento, internet parla tanto di multidimensional array vs flat array ;-)

E, incidentalmente, risolve il tuo problema

A tal proposito, riporto:

• https://levelup.gitconnected.com/c-...tiplication-are-we-doing-it-right-21a9f1cbf53
• https://eli.thegreenplace.net/2015/memory-layout-of-multi-dimensional-arrays (qui parla di row major vs column major order)

 

[fennek]

In realtà gli array multidimensionali sono syntactic sugar per quello che hai fatto tu: int array[3 * 9 * 10] e int array[3][9][10] hanno lo stesso layout in memoria. In entrambi i casi hai un blocco contiguo di $$\(3 \times 9 \times 10 = 270$$\) interi.

Oooops, devo smettere di pensare che le mie conoscenze di C possano applicarsi al C++.

Grazie per avermelo fatto notare, vado a nascondermi in un angolino a fustigarmi

 

[St3ve]

Oooops, devo smettere di pensare che le mie conoscenze di C possano applicarsi al C++.

Grazie per avermelo fatto notare, vado a nascondermi in un angolino a fustigarmi

Infatti funziona così anche in C
Però in Java avresti ragione tu.

Comunque vabbé, alla fine siamo qui per discutere. È servito a dare l'occasione a DispatchCode di postare articoli.

 

[Super Squirrel]

Ciao, dovrei creare una copia di un array multidimensionale di vector di questo tipo:

vector<int> a[3][5][10]

L'unica strada passa per tre for innestati o si può fare di meglio?

 

[theprogrammer99]

Se hai un altro vector b dello stesso tipo

b = a;

 

[St3ve]

std::vector<int> original[3][5][10], copy[3][5][10];                 
// do something                                                       
std::copy(&original[0][0][0], &original[2][4][9] + 1, &copy[0][0][0]);

Plausibilmente c'è un modo migliore per fare quello che vuoi fare, perché un array tridimensionale di vettori non è una cosa tanto normale.

 

[JunkCoder]

Sono pienamente daccordo con le risposte sopra, usare il costruttore di copia è la soluzione alla domanda, però come St3ve, ho il dubbio che la domanda non sia quella giusta per risolvere il tuo problema: dalla dichiarazione della variabile sembra che la tua intenzione sia di fare una cosa simile a int a[3][5][10] in C (copiabile con memcpy e sizeof). Usando std::vector il risultato è diverso: ogni vettore così dichiarato ha lunghezza variabile e invece di avere spazio per 150 numeri interi avrai 150 vettori ognuno dei quali può contenere un numero indefinito di numeri interi finché c'è spazio in RAM.

 

[Super Squirrel]

Se hai un altro vector b dello stesso tipo

b = a;

Il problema è che a non è un vector.

std::vector<int> original[3][5][10], copy[3][5][10];                
// do something                                                      
std::copy(&original[0][0][0], &original[2][4][9] + 1, &copy[0][0][0]);

Grazie, non conoscevo la funzione copy(). Presumo che senza scomodare gli iteratori dovrebbe essere simile a qualcosa del genere:

...

template <typename T>
void copia(const T *source, T *destination, const unsigned int dim)
{
    for(unsigned int i = 0; i < dim; ++i)
    {
        destination[i] = source[i];
    }
}

int main()
{
    vector<int> a[3][5][10];
    ...
    vector<int> b[3][5][10];
    copia(**a, **b, sizeof(a) / sizeof(***a));
    ...
}

Plausibilmente c'è un modo migliore per fare quello che vuoi fare, perché un array tridimensionale di vettori non è una cosa tanto normale.

Sto implementando delle strategie avanzate per la risoluzione ragionata dei sudoku, e nel caso specifico l'oggetto da me utilizzato è

vector<unsigned int> table[3][9][10];

dove il 3 sta per righe, colonne e riquadri, il 9 sta per il numero di righe, colonne o riquadri , il 10 per i numeri da 1 a 9; il vector invece contiene gli indici delle caselle che rispettano alcune condizioni.
E' vero, potrei anche utilizzare vector di vector di... ma sinceramente se un contenitore possiede una dimensione nota a compile-time preferisco utilizzare degli array.

Sono pienamente daccordo con le risposte sopra, usare il costruttore di copia è la soluzione alla domanda, però come St3ve, ho il dubbio che la domanda non sia quella giusta per risolvere il tuo problema: dalla dichiarazione della variabile sembra che la tua intenzione sia di fare una cosa simile a int a[3][5][10] in C (copiabile con memcpy e sizeof). Usando std::vector il risultato è diverso: ogni vettore così dichiarato ha lunghezza variabile e invece di avere spazio per 150 numeri interi avrai 150 vettori ognuno dei quali può contenere un numero indefinito di numeri interi finché c'è spazio in RAM.

Con quanto scritto in precedenza spero di aver risposto anche al tuo messaggio.

 

[DispatchCode]

dove il 3 sta per righe, colonne e riquadri, il 9 sta per il numero di righe, colonne o riquadri , il 10 per i numeri da 1 a 9; il vector invece contiene gli indici delle caselle che rispettano alcune condizioni.
E' vero, potrei anche utilizzare vector di vector di... ma sinceramente se un contenitore possiede una dimensione nota a compile-time preferisco utilizzare degli array.

In realtà no, ti è sufficiente una matrice 9x9. Tutti i quadrati/box sono grandi 3x3, quindi non è un problema fare i conti nei singoli box.

Per dire, se devi verificare la posizione (riga, colonna) 4,0 il box inizia a 4-4%3, 0-0%3 = 3,0 che sono riga e colonna di partenza. Da qui ti basta fare tipo r+3 e c+0, dove r e c vanno da 0 a 2 (dimensione di un box), e indicizzano ovviamente direttamente la matrice.

Sono da smartphone, non mi sono messo a formattare bene e farti esempi per questo motivo, ma spero sia chiaro.

 

[Super Squirrel]

In realtà no, ti è sufficiente una matrice 9x9. Tutti i quadrati/box sono grandi 3x3, quindi non è un problema fare i conti nei singoli box.

Per dire, se devi verificare la posizione (riga, colonna) 4,0 il box inizia a...

Ma anche io per la griglia principale utilizzo un array bidimensionale 9x9, questa tabella

vector<unsigned int> table[3][9][10];

ha infatti un altro scopo!

Volendo posso provare a spiegarmi meglio:
- consideriamo il vector contenuto in table[k][j][n];
- il primo indice indica il tipo di gruppo che stiamo considerando (k=0 indica una riga, k=1 una colonna e k=2 un riquadro);
- j invece rappresenta l'indice principale, ossia l'indice del gruppo considerato (per esempio j=5 indica la sesta riga, colonna o riquadro (in base al valore di k));
- n indica il numero da 1 a 9 considerato;
- infine il vector contenuto in table[k][j][n] conterrà gli indici secondari delle caselle vuote del gruppo di tipo k e indice j che presentano fra i loro candidati il numero n.

Per esempio table[2][3][7]={0,2,8} ci dice che nel quarto riquadro il numero 7 manca, e può andare nella prima, terza o ultima casella del suddetto riquadro.

E questo tipo di informazioni così schematizzate mi tornano molto utili in varie strategie risolutive.

 

[St3ve]

Se mi posso permette un consiglio che ti risolve anche il problema della deep copy, e aumenta le prestazioni: non fare array innestati, fallo di profondità uno.

Per esempio, partiamo dalla tua tabella, di dimensione X (3), Y (9), Z(10).
Fai che table sia un array di dimensione 270 (X*Y*Z).

Per accedere all'elemento k, j, n, dovrai accedere table[k * Y * Z + j * Z + n]

In realtà gli array multidimensionali sono syntactic sugar per quello che hai fatto tu: int array[3 * 9 * 10] e int array[3][9][10] hanno lo stesso layout in memoria. In entrambi i casi hai un blocco contiguo di $$\(3 \times 9 \times 10 = 270$$\) interi. Quello che si può fare, come spiegato dai link di DispatchCode, è scambiare l'ordine degli indici in modo tale che quando scorri i vari elementi hai un pattern di accesso lineare e senza salti. Però è un'ottimizzazione che dipende da come è strutturato il resto del codice.

Il problema della deep copy non si risolve perché std::vector contiene un puntatore coni dati del vettore. I campi normali (e.g., size e capacity) li può copiare così come sono, ma se copiasse anche il puntatore non potrebbe modificare il dato di un vettore senza cambiare anche l'altro. Deve anche allocare una nuova area di memoria sui cui e copiare all'interno di quella dell'altro array.

Un modo per velocizzare il tutto sarebbe quello di usare interi a 128 bit (o una struct equivalente) al posto di std::vector e guardare l'indice dei bit per stabilire se un indice appartiene o no all'insieme, ma sono considerazioni che si fanno in fase finale. In questo modo non deve fare deep copy e l'array è veramente contiguo in memoria (i.e., non si ritrova con un array di puntatori, come adesso). Io mi immagino che stia ancora sviluppando la sua idea e premature optimizations is the root of evil, quindi ci penserà più avanti sempre se la sua idea avrà successo. Per adesso qualsiasi cosa gli risulta comoda va benissimo.

 

[Super Squirrel]

A tal proposito, riporto:

• https://levelup.gitconnected.com/c-...tiplication-are-we-doing-it-right-21a9f1cbf53
• https://eli.thegreenplace.net/2015/memory-layout-of-multi-dimensional-arrays (qui parla di row major vs column major order)

Per il momento ho letto solo il primo articolo e devo dire che l'ho trovato molto interessante!
L'argomento affrontato però non mi sembra abbia molto a che fare con la questione "multidimensional array vs flat array", in quanto il succo dell'articolo dovrebbe essere che per massimizzare le prestazioni bisogna adottare algoritmi che tengano conto e "assecondino" per quanto possibile il row major order. O sbaglio?
Nell'articolo si fa l'esempio del prodotto matriciale, ma se io sostituisco gli array bidimensionali con array flat non mi aspetto che cambi qualcosa.

Se mi posso permette un consiglio che ti risolve anche il problema della deep copy, e aumenta le prestazioni: non fare array innestati, fallo di profondità uno.

Per la copia non dovrei comunque ricorrere a std::copy() come suggerito da @St3ve o ad una funzione come quella da me postata in precedenza:

template <typename T>
void copia(const T *source, T *destination, const unsigned int dim)
{
    for(unsigned int i = 0; i < dim; ++i)
    {
        destination[i] = source[i];
    }
}

?

Le performance aumentano alla lettura perché hai un solo array di 270 elementi contigui in memoria, invece che 27 da 10. Inoltre, sarai sicuro che tutto l'array sia in cache (L1/L2/L3), invece che solo alcuni degli array. E spostarsi dentro l'array diventa solo uno shift del puntatore di massimo 270 * size del contenuto, invece che saltare avanti e indietro in praticamente tutta la memoria.

Tralasciando la questione relativa a L1/L2/L3 che non conosco , mi chiedevo: ma un array statico multidimensionale non è comunque contiguo in memoria?
Inoltre restando nell'ambito degli array statici come quelli da me utilizzati, l'istruzione table_3D[k][j][n] non è del tutto equivalente a table_flat[k * Y * Z + j * Z + n] ? Nel senso che dietro le quinte, nel caso di array multidimensionali, non viene effettuato lo stesso suddetto calcolo basato sull'aritmetica dei puntatori?

 

[fennek]

Infatti funziona così anche in C
Però in Java avresti ragione tu.

Comunque vabbé, alla fine siamo qui per discutere. È servito a dare l'occasione a DispatchCode di postare articoli.

Davvero? Devo rileggermi il K&R, non pensavo di essere così arrugginito