Qual è la corretta gerarchia di classi da utilizzare per le matrici?

6

Sto lavorando con particolari classi di matrici che ammettono operazioni veloci senza ricorrere a una densa algebra lineare. Per mantenere la gerarchia semplice, attualmente sto facendo la seguente (molto semplificata):

class Matrix:
    def mvm() # matrix-vector multiplication
    def is_square()
    def is_psd()
    def is_symm()
    def eigenvalue_bound()

class Diag(Matrix):
    # represents a diagonal matrix with main diagonal v
    # requires O(n) memory and time for all Matrix operations
    # where n is the size of v
    def __init__(self, v)

class Circulant(Matrix):
    # represents a circulant matrix with top row v
    # requires O(n lg n) memory and time for all Matrix operations
    # where n is the size of v
    def __init__(self, v)

class Kronecker(Matrix):
    # represents the Kronecker product of two matrices A and B
    # requires O(memory(A) + memory(B)) memory for sparse storage
    # instead of the dense version, of size O(memory(A) * memory(B))
    # Similarly, a Matrix operation taking op(A) and op(B) time
    # can be done in O(size(A) * op(B) + size(B) * op(A)).
    def __init__(self, A, B)

class Composition(Matrix):
    # represents the composition product of two matrices A and B, AB
    # requires O(memory(A) + memory(B)) memory
    # might save time if op(A) + op(B) < op(AB)
    def __init__(self, A, B)

Come puoi vedere, mi preoccupo di molte proprietà delle matrici: semideterminity positive, simmetria, informazioni sugli autovalori. Queste proprietà sono disponibili solo se la matrice soddisfa determinate proprietà matematiche e esse traducono non banalmente tra le matrici.

Ci sono altre matrici e proprietà che sto considerando, ma si spera che questo abbia successo: i metodi che vorrei chiamare su un'istanza di ognuno di questi sono strongmente dipendenti dal contesto in cui vengono create le matrici.

Ho adottato la "semplice" soluzione per far sì che la base contenga l'unione di tutte le proprietà che potrei desiderare, quindi eseguo vari controlli di integrità runtime se un metodo viene chiamato in un determinato contesto.

All'altra estremità dello spettro, questa potrebbe essere una soluzione per l'ereditarietà multipla e i mixin, ma ciò comporterebbe un numero combinatorio di sottoclassi da gestire! Qual è l'approccio migliore qui?

Per chiarimenti: queste matrici sono immutable . Per coerenza, attenersi a python . Un'altra caratteristica importante è che sotto diversi vincoli, la rappresentazione in memoria differisce tra ogni sottotipo. In altre parole, sto solo trattando queste matrici come operatori lineari.

    
posta VF1 30.01.2017 - 16:45
fonte

3 risposte

2

Dato che le tue matrici sono immutabili, è effettivamente possibile avere una classe base generale Matrix che definisce tutte le operazioni sulle matrici necessarie e alcuni sottotipi specifici di questa classe come forma di ottimizzazione , quando sai che hai bisogno di questo. Tuttavia, prima di farlo, ci penserei due volte se il tipo di complessità aggiuntiva che aggiungi al tuo programma vale davvero la pena, e se non stai creando un incubo di manutenzione, così facendo.

Ad esempio, un sottotipo Diag derivato da Matrix può eventualmente avere senso, dal momento che può essere implementato con una memoria e un'amplificazione molto migliori; comportamento temporale per alcune delle sue operazioni tipiche rispetto alle matrici arbitrarie. Immagino che possa portare benefici se stai avendo casi d'uso in cui ne hai bisogno di molti.

La necessità di un sottotipo SquareMatrix è tuttavia discutibile, dal momento che non porterà alcun risparmio significativo di memoria. Forse è vero quello che hai scritto in "varie implementazioni possono essere notevolmente semplificate se le matrici sono quadrate" , ma sono quelle caratteristiche o funzioni di cui hai veramente bisogno? Ad esempio, la moltiplicazione della matrice non rientra in questa categoria, lo sforzo di implementazione è essenzialmente lo stesso per le matrici quadrate e non quadrate.

Considerazioni simili dovrebbero essere fatte per sottotipi come "Circulant" o "Kronecker" o "Composition". Avere un sottotipo specifico per questi consente di implementare alcune operazioni come inversione della matrice o test per PSD in modo ottimizzato. Si noti, tuttavia, che altre operazioni come l'aggiunta della matrice standard o l'estrazione di voci singole perderanno l'efficienza. Pertanto, fornirei sottotipi specifici di questo tipo solo se hai un vero caso di utilizzo per i quali ha bisogno di per essere ottimizzato e dove sei sicuro che valga la pena.

Quindi, invece di pensare a come costruire il maggior numero possibile di sottotipi, ti consiglio di chiedersi come usare il minor numero possibile di sottotipi e di ottimizzare solo quando ti imbatti in prestazioni o memoria misurabili i problemi. L'ottimizzazione non è un fine a se stessa, è un mezzo per un fine e, se non hai una buona ragione per cui hai bisogno di queste ottimizzazioni, dovresti considerare di non ottimizzare affatto.

    
risposta data 30.01.2017 - 23:16
fonte
5

L'uso di una gerarchia di classi non è generalmente consigliabile in questi casi, poiché i sottotipi codificano specifici limiti di dati .

Se le tue matrici sono mutabili (ovvero gli elementi della matrice possono essere aggiornati), allora ti imbatti nel problema dell'ellisse circolare. Per esempio. data una matrice diagonale, potrei cambiare un elemento in modo che l'oggetto non rappresenti più una matrice diagonale. Tuttavia, una volta costruito, un oggetto non può cambiare il suo tipo.

Il prossimo problema è che i tuoi vincoli potrebbero non essere esclusivi. Questo dipende da quali vincoli esatti stai cercando di codificare. A meno che non si stia utilizzando un sistema di miscelazione, ciò comporta un'esplosione combinatoria di tipi. Se si utilizza un sistema di mixaggio flessibile, non è ancora possibile selezionare il tipo corretto per una matrice nel programma senza conoscere le proprietà dei dati di runtime.

Di conseguenza, l'unica soluzione ragionevole è avere un singolo % tipo diMatrix senza sottotipi particolari.

Come possiamo quindi trattare le operazioni che hanno senso solo quando la matrice soddisfa un particolare vincolo? Se fanno parte del tipo generale Matrix , possono causare eccezioni di runtime. Questo può essere reso più ovvio fornendo metodi che controllano il vincolo. Se il vincolo è soddisfatto, restituiscono un oggetto adattatore che fornisce l'operazione con restrizioni. Se il vincolo non viene soddisfatto, restituiscono null. In C ++, questo sarebbe usato come:

// instead of: matrix.try_operation_only_for_diagonals()

if (auto matrix_as_diagonal = matrix.as_diagonal()) {
    matrix_as_diagonal->operation_only_for_diagonals();
}

In Python:

matrix_as_diagonal = matrix.as_diagonal()
if matrix_as_diagonal is not None:
    matrix_as_diagonal.operation_only_for_diagonals()

L'oggetto che rappresenta questo vincolo ha solo un singolo campo membro: la matrice originale per la quale fornisce un comportamento aggiuntivo.

Se le tue matrici sono immutabili o cambiano raramente, puoi memorizzare nella cache i risultati dei controlli dei vincoli nell'oggetto Matrix . Se tutti i vincoli devono essere controllati durante la costruzione della matrice o pigramente dipende dalla vostra applicazione. Se è possibile dimostrare in modo statico che una matrice soddisferà determinati vincoli, è meglio che questi siano impostati nel costruttore. Come ciò può essere fatto elegantemente (cioè senza un'esplosione combinatoria di firme del costruttore) dipende dal tuo linguaggio di programmazione.

Come possiamo gestire le operazioni disponibili per tutte le matrici ma implementate in modo diverso quando viene soddisfatto un determinato vincolo? Con lo stesso meccanismo. Abbiamo bisogno di testare i vari vincoli in fase di esecuzione. Ma sarebbe fastidioso se i vincoli venissero controllati ancora e ancora per ogni esecuzione dell'operazione. In questi casi, puoi usare il modello di strategia. La prima volta che si esegue tale operazione, si seleziona una strategia di esecuzione appropriata e in seguito può essere utilizzata direttamente quando l'operazione viene eseguita nuovamente sulla stessa matrice.

    
risposta data 30.01.2017 - 19:02
fonte
1

La mia risposta arriva in ritardo, ma credo sia comunque importante condividere le mie opinioni con voi. Tecnicamente non è la mia intuizione, ma invece le conoscenze apprese da OpenCV.

TL; DR:

  • La risposta di Doc Brown favorisce una decisione no-go per impostazione predefinita, e ti spinge a pensare in modo critico se i potenziali benefici sono sfruttabili pratica o no.
  • La mia risposta spiega come le librerie esistenti gestiscono la stessa decisione. Ma il mio punto di vista è lo stesso: non andare .

Queste altre matrici sono espresse nel modo migliore (nel sistema di caratteri del linguaggio di programmazione) come Matrix Expressions . In altre parole, sono oggetti speciali che possono essere valutati per dare una matrice . Tuttavia, ogni oggetto speciale ha anche proprietà interrogabili, che possono essere utilizzate dalle implementazioni di operatori lineari per eseguire l'attività, senza dover ispezionare ogni (i, j) della matrice valutata.

L'espressione della matrice è una generalizzazione di una matrice. In termini di programmazione, un'espressione matrice è un'unione discriminata (tipo somma) di:

  • Espressione della matrice
    • Matrici completamente popolate
    • Qualunque delle matrici speciali: un elenco potenzialmente estensibile
    • Operatore unario applicato a un'espressione di matrice (figlio)
    • Operatore binario applicato a due (a sinistra, a destra) espressioni di matrice

Quanto segue è la motivazione del perché la valutazione dell'espressione su matrici speciali deve essere posticipata.

  • L'utente programmatore assegna il prodotto di A, B a C
    C = A * B
  • Il programmatore-utente assegna il prodotto di C, D a E
    E = C * D
  • Matrix A è tipico (denso, non avendo proprietà speciali)
  • Le matrici B e D sono speciali.
  • Al momento dell'assegnazione di (A * B) a C , poiché uno degli argomenti ('A') è tipico, sembra che sia necessaria una valutazione completa del prodotto della matrice.
  • Ma, una volta noto che C deve essere moltiplicato con D , che è speciale, ha già perso la possibilità di eseguire un'ottimizzazione, che è A * (B * D) .

Pertanto, se la valutazione delle espressioni di matrice non viene differita, molte opportunità di ottimizzazione sarebbero state perdonate a causa della decisione architettonica.

Mentre la moltiplicazione della matrice è associativa, potrebbero esserci altri operatori che non lo sono. Questo deve essere tenuto presente quando si implementano le espressioni di matrice.

La familiarità con la sommatoria di Einstein sarebbe utile in una discussione: link

Le proprietà della matrice (come la simmetria) sono completamente separate. Le proprietà si comportano come predicati. Un'espressione matrice può essere passata in un predicato per ottenere un risultato true/false .

Tuttavia, per gli utenti attenti alle prestazioni, ciascun predicato avrà diverse caratteristiche di rendimento:

  • Costante: is_symm ( MatExpr ) può essere restituito in O(1) time
  • Caso lineare: is_symm ( MatExpr ) può essere restituito in O(M+N) time
  • Caso completamente valutato: is_symm ( MatExpr ) può essere restituito in O(MN) time
  • Cacheability: il dato MatExpr risulta immutabile e fortunatamente la sua simmetria è già stata calcolata o memorizzata in cache in qualche modo, in modo che is_symm ( MatExpr ) possa restituire il risultato in O(1) tempo.

Gli algoritmi che devono decidere se utilizzare la proprietà di simmetria dovranno prima interrogare le caratteristiche delle prestazioni e poi decidere la strategia di valutazione.

Sembra complicato? Sì, quindi non andare . È doloroso.

Questo punto di vista è stato implementato in vari pacchetti di programmazione matriciale, quindi non sto presentando nulla di nuovo. Inoltre, l'implementazione è presumibilmente nelle mani di professionisti e dottori di ricerca. Non sono qualificato per dire nulla su come sono effettivamente progettati e implementati nelle librerie software.

    
risposta data 04.02.2017 - 00:16
fonte

Leggi altre domande sui tag