Qual è il modo più veloce per rappresentare e moltiplicare le matrici booleane sparse?

Question

Quindi, sto usando matrici booleane la cui dimensione è in genere di un paio di dozzina o duecento, di solito sono piuttosto scarse (solo alcuni 2-4 non zeri nella maggior parte delle righe e delle colonne) e il mio runtime è fortemente dominato dal loro moltiplicazione.

Quale struttura si adatta meglio per accelerare la moltiplicazione in queste circostanze?

Attualmente sto memorizzando ciascuna matrice in un insieme di bit contigui (array di bit lunghi 64 bit) e moltiplicandoli con l'algoritmo standard, appena accelerato per la scarsità con l'operazione rapida di localizzazione del set successivo bit in una parola e con vettorizzazione tramite operazioni di maschera di bit.

Dovrei forse usare qualche rappresentazione sparsa?

Answer 1

Penso che abbia senso utilizzare una rappresentazione sparsa. Anche con qualcosa di semplice come un insieme di indici diversi da zero, penso che otterrai prestazioni migliori.

Ad esempio, per una matrice 100 × 100 con 300 elementi diversi da zero, utilizzando la rappresentazione di array 2D, la moltiplicazione richiede 100 × 100 × 100 = 1.000.000 di "operazioni". L'utilizzo di set di indici richiede solo 300 × 300 = 90.000 operazioni. (Ovviamente quelle operazioni non sono direttamente confrontabili.)

Answer 2

Un elenco di x's e di y. Per esempio:

[0,2,0,12,0,60,1,2,1,39 ... etc]

Il che significa che c'è un 1 a 0,2 a 1 a 0 , 12, ecc.

La parte interessante è che non è necessario un nuovo tipo di dati, ed è piuttosto semplice analizzare.

Per moltiplicare, dovresti cercare tutti gli indici corrispondenti/parzialmente corrispondenti.

Answer 3

Si potrebbe prendere in considerazione l'utilizzo di una rappresentazione quadrifoglio. Il quadrifoglio può codificare una matrice sparsa piuttosto bene, e si presta a un'implementazione di moltiplicazione ricorsiva piuttosto semplice (e efficiente in termini di cache). Rendi il caso base una matrice 8x8 in modo da poter implementare il multiplo come operazione (ottimizzata per l'assembly?) A 64 bit per 64 bit.