Cómo implementar una matriz enorme en C

Estoy escribiendo un programa para una simulación numérica en C. Parte de la simulación son nodos espacialmente fijos que tienen algún valor flotante para cada otro nodo. Es como un gráfico dirigido. Sin embargo, si dos nodos están demasiado lejos, (más allá de una longitud de corte a) este valor es 0.Cómo implementar una matriz enorme en C

Para representar todas estas "correlaciones" o valores flotantes, traté de usar una matriz 2D, pero desde Tengo 100.000 y más nodos, que corresponderían a una memoria de 40GB más o menos.

Ahora, estoy tratando de pensar en diferentes soluciones para ese problema. No quiero guardar todos estos valores en el disco duro. Tampoco quiero calcularlos sobre la marcha. Una idea era algún tipo de matriz dispersa, como la que se puede usar en Matlab.

¿Tiene alguna otra idea, cómo almacenar estos valores?

Soy nuevo en C, así que no espere mucha experiencia.

Gracias y un saludo, Ene Oliver

Fuente

2011-02-09 janoliver

¿Qué pasa con algún tipo de hash/mapa donde está la clave (fila x col)? Solo tendría tantos elementos como entradas en la matriz con un valor distinto de cero. –

No es realmente una pregunta específica ... Sí, matrices dispersas. Busque algunos algoritmos ... Tal vez con algunos detalles sobre el porcentaje de nulll nodos en la matriz, o más información sobre la simulación, tal vez alguien podría sugerir otras soluciones que una representación grah. – pascal

... por ejemplo, ¿qué quieres hacer con esta matriz? – pascal

Cuantos nodos, en promedio, se encuentran dentro de la distancia de corte para un nodo dado determina su requerimiento de memoria y le indica si necesita realizar una búsqueda en el disco. La solución que toma menos memoria es probablemente una tabla hash que asigna un par de nodos a una distancia. Dado que la distancia es la misma en cada sentido, solo necesita ingresarla en la tabla hash una vez para el par: coloque los dos números de nodo en orden numérico y luego combínelos para formar una clave hash. Puede usar las funciones de Posix hsearch/hcreate/hdestroy para la tabla hash, aunque son menos que ideales.

Fuente

2011-02-09 08:30:13

es una buena idea. Un nodo está en promedio conectado al 0,2% de los otros nodos. Esto depende de los parámetros. – janoliver

Sin embargo, estoy un poco preocupado por el rendimiento del proceso de búsqueda. Eso es en realidad mucho más importante que, por ejemplo, la creación de la matriz/hashmap, ya que este último se hace solo una vez ... – janoliver

@janoliver ¿Entonces son 200 de los 100.000 nodos? En velocidad: la búsqueda hash es O (1) pero el tiempo constante puede ser grande, especialmente cuando tiene poca memoria. (¿Cuánto tiene?) Quizás lo mejor sería una matriz de nodos con cada nodo que contiene una lista de nodos cercanos ordenados por número de nodo; la búsqueda binaria tomaría alrededor de 9 comparaciones para 200 nodos. Es fácil de implementar y es posible que desee comenzar con esto y solo considerar otra cosa si es necesario. –

Un enfoque de matriz dispersa sonidos ideal para esto. El Wikipedia article on sparse matrices analiza varios enfoques para la implementación.

Fuente

2011-02-09 08:01:18

De hecho, debería utilizar matrices dispersas si es posible. En scipy, tenemos soporte para matrices dispersas, para que pueda jugar en python, aunque para ser honesto, el soporte escaso aún tiene asperezas.

Si tiene acceso a matlab, definitivamente será mejor cajero automático.

Sin usar matriz dispersa, podría pensar en utilizar matrices basadas en Memap para que no necesite 40 Gb de RAM, pero seguirá siendo lenta, y solo tendrá sentido si tiene un bajo grado de dispersión (supongamos que si el 10-20% de su matriz 100000x100000 tiene elementos, entonces las matrices completas en realidad serán más rápidas y tal vez incluso ocupen menos espacio que las matrices dispersas).

Fuente

2011-02-09 08:02:23

Una matriz de adyacencia escasa es una idea, o podría usar una lista de adyacencia, permitiéndole almacenar solo los bordes que están más cerca que su valor de corte.

Fuente

2011-02-09 08:03:54

Hola Jim, gracias por la idea. Después de echar un vistazo rápido a estas listas, parece que un valor flotante simple al que hacen referencia dos índices consume menos memoria que uno de estos elementos de la lista. – janoliver

También podría contener una lista para cada nodo, que contiene los otros nodos con los que está relacionado este nodo. Entonces tendría un número total de entradas de lista de 2 * k, donde k es la cantidad de valores distintos de cero en la matriz virtual.

Aún se espera que la implementación de todo el sistema como una combinación de hashes/sets/maps sea aceptable con respecto a la velocidad/rendimiento en comparación con una matriz "real" que permita el acceso aleatorio.

edit: Esta solución es una forma posible de una implementación de una matriz dispersa. (Ver también la nota de Jim Balter a continuación. Gracias, Jim.)

Fuente

2011-02-09 08:51:38 Flinsch

Seguramente 2 (k-1) porque un nodo no se enlazará a sí mismo? Ver mi comentario sobre la pregunta principal, estoy de acuerdo que esta es la manera de resolverlo. – SlappyTheFish

Tenga en cuenta que una lista en cada nodo donde cada entrada en la lista contiene un número de nodo y una distancia distinta de cero es una matriz de forma dispersa, donde cada lista de nodos es una fila (o columna). –

@SlappyTheFish Flinsch escribió "k es el número de valores distintos de cero en la matriz virtual": la diagonal es todos ceros en la matriz virtual, por lo que k ya excluye esas entradas. La lista en realidad incluye k entradas, donde cada entrada tiene dos valores, un número de nodo y una distancia. –

Cómo implementar una matriz enorme en C

Respuesta

Cuestiones relacionadas