Domanda Matrici con template

[Yiazmat]

Sto cercando di sviluppare una classe template per le matrici, ma non riesco a definire gli operatori, in particolare l'operatore del prodotto tra matrici solo nel caso di matrice di m righe e di n colonne moltiplicata per un'altra matrice di n righe e p colonne.
Il problema è che nel template non specifico solo il tipo generico, ma anche le variabili contenenti le dimensioni, per cui gli operatori non possono prendere come argomenti altre specializzazioni della stessa classe senza un altro template, per cui non so come fare.
(Ho ipotizzato che senza dimensioni template, e quindi con allocazioni dinamiche, sarebbe uscito il tutto più lento di com'è adesso, per cui se devo per forza cambiare ed allocare dinamicamente, va bene)

 

[St3ve]

Devi fare una cosa di questo tipo:

template <typename T, size_t N, size_t M>
class Matrix {

    // something something...

    template <size_t P>
    Matrix<T, N, P> multiply(Matrix<T, M, P> right) {
        Matrix<T, N, P> ret = Matrix<T, N, P>(); // empty matrix

        for (size_t row = 0; row < N; row++) {
            for (size_t col = 0; col < P; col++) {
                for (size_t k = 0; k < M; k++) {
                    // pseudocode:
                    // ret[row][col] += myself[row][k] * right[k][col];
                }
            }
        }

        return ret;
    }

};

template <typename T, size_t N, size_t M, size_t P>
Matrix<T, N, P> matrix_multiply(Matrix<T, N, M> left, Matrix<T, M, P> right) {
    Matrix<T, N, P> ret = Matrix<T, N, P>(); // empty matrix

    for (size_t row = 0; row < N; row++) {
        for (size_t col = 0; col < P; col++) {
            for (size_t k = 0; k < M; k++) {
                // pseudocode:
                // ret[row][col] += left[row][k] * right[k][col];
            }
        }
    }

    return ret;
}

La moltiplicazione come prodotto interno alla classe ha poco senso a dire il vero, sarebbe meglio definirla solo su matrici quadrate e modificare lo stato interno: se devi prendere due matrici e generarne una terza, trovo più sensato usare la funzione. Però vabbe... il modo in cui procedere penso che si sia capito.

Ho ipotizzato che senza dimensioni template, e quindi con allocazioni dinamiche, sarebbe uscito il tutto più lento di com'è adesso

Non necessariamente. Lo stack solitamente è limitato, quindi se le tue matrici sono molto grandi potrebbero non starci e, in questo caso, sei costretto a metterle nello heap. Se questa allocazione la fai in un unico blocco di memoria mi aspetto che le performance siano identiche.

Nota che nel codice io ti ho messo l'algoritmo naive (quello che faresti con carta e penna) per la moltiplicazione di matrici, ma realisticamente vuoi utilizzare roba tipo Strassen. Non è difficile implementarlo ed è anche abbastanza didattico, in quanto è un'applicazione non banale dello schema divide et impera.

 

[Yiazmat]

Anzitutto grazie per la risposta e per l'esempio.
In effetti ha senso procedere con funzioni normali al posto di operatori su matrici non quadrate, non ci avevo pensato.
Sì, lo stack è limitato, però dovrebbe essere più veloce delle allocazioni su heap se non sbaglio, per cui, se devo moltiplicare due matrici 4x4, dovrei allocare 2 gruppi da 16 float nello heap.
Comunque sia, proverò a seguire entrambi i metodi per poi testarne la velocità (suppongo che usare duration di std::chrono sia sufficiente per questo, vero?).
Non conoscevo altri metodi per effettuare il calcolo, gli do uno sguardo, grazie per l'osservazione e per la risposta

 

[St3ve]

Sì, lo stack è limitato, però dovrebbe essere più veloce delle allocazioni su heap se non sbaglio

In un caso devi solo decrementare il valore in un registro, mentre nell'altro caso devi fare delle operazioni più complesse. La differenza in performance c'è, ma è irrisoria visto che sono un pugno di nanosecondi che perdi solo in fase di costruzione. Però sono d'accordo con te, non ci avevo riflettuto più di tanto quando ti avevo risposto. Personalmente ficcherei tutto dentro un std::array<T, N*M> e se l'user vuole allocare una matrice bella grande ci pensa lui a chiamare la new. Rimane più versatile.

E sì, std::chrono va benissimo se vuoi fare benchmarking.

 

[Yiazmat]

Personalmente ficcherei tutto dentro un std::array<T, N*M> e se l'user vuole allocare una matrice bella grande ci pensa lui a chiamare la new

Mmmh non so, non ho mai lavorato con std::array (ho sempre usato solo vector), ho notato che conoscere perfettamente la reference della STL è difficile se non impossibile.

 

[St3ve]

Nel tuo caso la scelta è tra gli array semplici (eventualmente bidimensionali) oppure std::array, che è sostanzialmente un wrapper ai raw arrays. Se usi std::vector vai ad allocare spazio nello heap e hai una struttura ridimensionabile. Nel tuo caso è conveniente solo se vuoi rendere la matrice ridimensionabile: in questo caso la dimensione della matrice la devi passare nel costruttore e non tra i template arguments.

 

[Yiazmat]

Sisi, mi sono messo a leggere la reference ed infatti è un piccolo wrapper degli array C.

Personalmente ficcherei tutto dentro un std::array<T, N*M> e se l'user vuole allocare una matrice bella grande ci pensa lui a chiamare la new.

Non riesco a capire che intendi, dovrebbe essere la stessa cosa, astrarre con il template le dimensioni per lo std::array oppure per l'array C.

 

[St3ve]

Non riesco a capire che intendi, dovrebbe essere la stessa cosa, astrarre con il template le dimensioni per lo std::array oppure per l'array C.

Intendo che io scriverei letteralmente std::array<T, N*M> matrix; dove prima avevo messo il commento // something something...

Uno dei vantaggi di usare std::array sui raw arrays (quelli del C per intenderci) è che i primi ti offrono il copy e il move constructor. Quindi per la tua classe Matrix puoi usare quelli di default funziona tutto senza che tu faccia niente. In ogni caso puoi fare come preferisci, direi che hai abbastanza informazioni per scrivere una classe funzionante. Procedi pure nel modo che ti è più congeniale.
Se poi ti blocchi da qualche parte o se vuoi qualche consiglio su qualcosa che non ti è chiara, se ne può discutere.

 

[Yiazmat]

Ah, capito, ma quindi in ogni caso conviene fare due funzioni, un operatore per le matrici quadrate ed una funzione (o anche metodo statico?) per il prodotto generico, no?

 

[St3ve]

Ah, capito, ma quindi in ogni caso conviene fare due funzioni, un operatore per le matrici quadrate ed una funzione (o anche metodo statico?) per il prodotto generico, no?

Io ti consiglio di usare implementare i metodi operator* e operator*= per per fare il prodotto per scalare. Il prodotto righe per colonne lo lasci generico su qualsiasi matrice NxM e MxP, implementato in una funzione separata.

 

[Yiazmat]

Ah già, avevo dimenticato il prodotto per scalare, mi conviene evitare overload e seguire quello che hai detto tu

-----------------------------------------------------------------------------------------

Stavo pensando un'altra cosa: è possibile aggiungere un overload dell'operatore[] in modo da poter trattare l'intera classe come se fosse solo una array a due dimensioni stile C? So come fare l'overload dell'operatore, ma solo ad una dimensione, a due non so proprio

Una cosa tipo

matrix<int, 4, 4> m;
m[0][0] = 5;

 

[St3ve]

L'operatore è solo uno, però gli puoi far restituire un std::array o una reference.