Come implementare una matrice enorme in C

Question

Sto scrivendo un programma per una simulazione numerica in C. Parte della simulazione sono nodi fissi nello spazio che hanno un valore float l'uno rispetto all'altro. È come un grafico diretto. Tuttavia, se due nodi sono troppo lontani, (più lontano di una lunghezza di taglio a) questo valore è 0.

Per rappresentare tutte queste "correlazioni" o valori float, ho provato a utilizzare un array 2D, ma dal Ho 100.000 e più nodi, che corrispondono a una memoria da 40 GB o giù di lì.

Ora, sto cercando di pensare a diverse soluzioni per quel problema. Non voglio salvare tutti questi valori sul disco fisso. Inoltre, non voglio calcolarli al volo. Un'idea era una sorta di matrice sparsa, come quella che si può usare in Matlab.

Avete altre idee, come conservare questi valori?

Sono nuovo di C, quindi per favore non aspettatevi troppa esperienza.

Grazie e cordiali saluti, Jan Oliver

Answer 1

Quanti nodi, in media, si trovano all'interno della distanza di cutoff per un determinato nodo determinano i requisiti di memoria e indicano se è necessario eseguire una pagina su disco. La soluzione che occupa meno memoria è probabilmente una tabella hash che mappa una coppia di nodi a una distanza. Poiché la distanza è uguale in ogni modo, è sufficiente inserirlo nella tabella hash una volta sola per la coppia: inserire i due numeri di nodo in ordine numerico e combinarli per formare una chiave hash. È possibile utilizzare le funzioni Posix hsearch/hcreate/hdestroy per la tabella hash, sebbene non siano l'ideale.

Answer 2

Un approccio a matrice sparsa suoni ideale per questo. Lo Wikipedia article on sparse matrices discute diversi approcci all'implementazione.

Answer 3

Se possibile, utilizzare matrici sparse. In Scipy, abbiamo il supporto per le matrici sparse, in modo da poter giocare in Python, anche se per essere sincero il supporto sparse ha ancora i bordi grezzi.

Se si ha accesso a MATLAB, sarà sicuramente ATM migliore.

Senza utilizzare la matrice sparsa, si potrebbe pensare di utilizzare matrici basate su memap in modo da non aver bisogno di 40 Gb di RAM, ma sarà comunque lento, e ha senso solo se si ha un basso grado di scarsità (diciamo che se il 10-20% della matrice 100000x100000 contiene elementi, allora gli array completi saranno effettivamente più veloci e forse occuperanno meno spazio rispetto alle matrici sparse).

Answer 4

Una matrice di adiacenza sparsa è un'idea, oppure è possibile utilizzare un elenco di adiacenza che consente di archiviare solo i bordi più vicini del valore limite.

Answer 5

Si potrebbe anche tenere un elenco per ogni nodo, che contiene gli altri nodi a cui questo nodo è correlato. Avresti quindi un numero complessivo di voci di elenco di 2 * k, dove k è il numero di valori diversi da zero nella matrice virtuale.

L'implementazione dell'intero sistema come combinazione di hash/set/mappe è ancora accettabile per quanto riguarda velocità/prestazioni rispetto a una matrice "reale" che consente l'accesso casuale.

modifica: questa soluzione è una possibile forma di implementazione di una matrice sparsa. (Vedi anche la nota di Jim Balter qui sotto. Grazie, Jim.)