Una matriz dispersa es una representación abstracta de una matriz ordinaria , en la que los datos no se presentan de forma continua, sino fragmentada; la mayoría de sus elementos toman el mismo valor (el valor por defecto, normalmente 0 o nulo). Además, almacenar una gran cantidad de ceros en una matriz es ineficiente tanto para almacenar como para procesar la matriz.
Una matriz dispersa puede acceder a elementos indefinidos. En este caso, la matriz devolverá algún valor predeterminado.
La implementación más simple de esta matriz asigna espacio para toda la matriz, pero cuando hay pocos valores no predeterminados, esta implementación es ineficiente. Las funciones para trabajar con matrices ordinarias no se aplican a esta matriz en los casos en que se conoce la escasez de antemano (por ejemplo, cuando se almacenan datos en bloques).
Una matriz dispersa generalmente se representa como una matriz asociativa :
Sparse_Array[{pos1 -> val1, pos2 -> val2,…}]o Sparse_Array[{pos1, pos2,…} -> {val1, val2,…}],donde cada posición pos i corresponde al valor val i . Este método se utiliza para ahorrar memoria (tanto la clave como el valor llevan información).
Aquí se usa una lista enlazada en lugar de una matriz regular porque, en primer lugar, una matriz regular requiere espacio para almacenar valores indefinidos. Por ejemplo, al declarar:
double arr[1000][1000];Se asignarán 8 MB de memoria a la vez (8 bytes por valor × 1,000,000 de valores), lo que es una pérdida de memoria injustificada. En el caso de una lista enlazada, los valores vacíos no se almacenan y el espacio para nuevos valores se asigna automáticamente cuando se agregan o eliminan elementos (en este caso, podemos hablar de asignación de memoria dinámica ).