c++ - grafos - Estructura de datos eficiente(complejidad de tiempo y espacio) para matriz densa y dispersa

matriz dispersa c++

Question

Tengo que leer un archivo en el que se almacena una matriz con autos ( 1 = BlueCar, 2 = RedCar, 0 = Empty ).

Necesito escribir un algoritmo para mover los coches de la matriz de esa manera:

• los azules se mueven hacia abajo ;
• los rojos se mueven hacia la derecha ;
• hay un turno en el que todos los azules se mueven y un turno para mover todos los rojos.

Antes de leer el archivo, no conozco el tamaño de la matriz y si es denso o escaso, así que tengo que implementar dos estructuras de datos (una para denso y otra para dispersa) y dos algoritmos.

Necesito alcanzar la mejor complejidad de tiempo y espacio posible .

Debido al tamaño de matriz desconocido, creo que debo almacenar los datos en el montón.

Si la matriz es densa , pienso usar algo como:

short int** M = new short int*[m];
short int*  M_data = new short int[m*n];

for(int i=0; i< m; ++i) 
{
    M[i] = M_data + i * n;
}

Con esta estructura puedo asignar un espacio contiguo de memoria y también es fácil acceder con M[i][j] .

Ahora el problema es la estructura a elegir para el caso disperso , y también tengo que considerar cómo puedo mover los autos a través del algoritmo de la manera más simple: por ejemplo, cuando evalúo un automóvil, necesito encontrarlo fácilmente si en el siguiente posición (hacia abajo o hacia la derecha) hay otro automóvil o si está vacío.

Inicialmente pensé en definir los objetos de BlueCar y RedCar que heredan del objeto Car general. En este objeto puedo guardar las coordenadas de la matriz y luego ponerlas en:

std::vector<BluCar> sparseBlu;
std::vector<RedCar> sparseRed;

De lo contrario, puedo hacer algo como:

vector< tuple< row, column, value >> sparseMatrix

Pero el problema de encontrar lo que está en la siguiente posición aún permanece.

Probablemente esta no sea la mejor manera de hacerlo, entonces, ¿cómo puedo implementar el caso disperso de una manera eficiente? (también usa una estructura única para dispersa)

Answer 1

¿Por qué no simplemente crear una asignación de memoria directamente sobre el archivo? (suponiendo que sus datos 0,1,2 se almacenan en bytes contiguos (o bits) en el archivo, y la posición de esos bytes también representa las coordenadas de los automóviles)

De esta forma, no necesita asignar memoria extra y leer todos los datos, y se puede acceder a los datos de manera sencilla y eficiente con M[i][j] .

Pasar las filas sería amigable con la caché L1.

En el caso de datos muy escasos, puede escanear los datos una vez y mantener una lista de las regiones / bloques vacíos en la memoria (solo es necesario almacenar los inicios y el tamaño), que luego puede omitir (y ajustar cuando sea necesario) en ejecuciones posteriores .

Con la asignación de memoria, solo las páginas a las que se accede con frecuencia se guardan en la memoria. Esto significa que una vez que haya escaneado las regiones vacías, la memoria solo se asignará a las regiones no vacías a las que se accede con frecuencia (todo esto se hará automágicamente por el núcleo; no es necesario que lo haga).

Otro beneficio es que está accediendo al caché de disco del sistema operativo directamente. Por lo tanto, no es necesario seguir copiando y moviendo datos entre el espacio del kernel y el espacio del usuario.

Para optimizar aún más el uso de espacio y memoria, los automóviles se pueden almacenar en 2 bits en el archivo.

Actualización :

Tendré que mover autos con openMP y MPI ... ¿Funcionará la asignación de memoria también con hilos concurrentes?

Podría usar multihebra, pero no estoy seguro si OpenMP sería la mejor solución aquí, porque si trabaja en diferentes partes de los datos al mismo tiempo, es posible que deba verificar algunas regiones superpuestas (es decir, un automóvil podría moverse desde un bloque). a otro).

O podría dejar que los hilos funcionen en las partes centrales de los bloques, y luego comenzar otros hilos para hacer los límites (con los autos rojos que serían un byte, con los autos azules una fila completa).

También necesitaría un mecanismo de bloqueo para ajustar la lista de regiones dispersas. Creo que la mejor manera sería lanzar hilos separados (dependiendo del tamaño de los datos, por supuesto).

Answer 2

En una tarea algo similar, simplemente hice uso de almacenamiento de filas comprimidas .

La fila y columna comprimidas (en la siguiente sección) Los formatos de almacenamiento son los más generales: no hacen suposiciones sobre la estructura de dispersión de la matriz, y no almacenan ningún elemento innecesario. Por otro lado, no son muy eficientes, necesitan un paso de direccionamiento indirecto para cada operación escalar en un producto de matriz vectorial o solución de preacondicionador.

Tendrá que ser un poco más específico sobre los requisitos de complejidad de tiempo y espacio. CSR requiere un paso de indexación adicional para operaciones simples, pero esa es una cantidad menor de sobrecarga si solo está haciendo operaciones simples de matriz.

También hay una implementación existente de C ++ disponible en línea también.