¿La mejor manera de asignar memoria a una matriz bidimensional en C?

5 minutos de lectura

¿La mejor manera de asignar memoria a una matriz bidimensional
Jarvis

¿Cuál es la mejor manera de asignar memoria a un two-d array en C,desde ambas perspectivas: memory-management y speed ?

Además, cuál es mejor usar, un two-d array (y asignarle memoria) o un double pointer ? ¿Alguien puede explicar en detalle qué sucede dentro, por qué un método es mejor que el otro?

  • ¿Qué información tienes sobre el tamaño necesario? ¿Está arreglado o cambiará cuando se ejecute el programa?

    – Un interno no tiene nombre

    28 de noviembre de 2016 a las 14:54

  • La matriz de dos dimensiones será más rápida de asignar porque solo 1 asignación, también contigua. Pero si solicita demasiados contiguos, puede fallar.

    – Jean-François Fabre

    28 de noviembre de 2016 a las 14:54

Para obtener el mejor rendimiento y la mejor legibilidad, dichas matrices siempre deben asignarse como una porción contigua de memoria:

type (*array) [X][Y] = malloc( sizeof(type[X][Y]) );

Debes evitar esto:

// BAD METHOD, not a real array

type** lookup_table = malloc( X*sizeof(type*) );
for(size_t i=0; i<Y; i++)
{
  lookup_table[i] = malloc( Y*sizeof(type) );
}

El primero es más rápido por muchas razones. Se asigna en una porción contigua de memoria y no se segmenta en todo el montón. Las versiones segmentadas bloquean todas las formas de optimización de código y el uso eficiente de caché de datos en el chip, además, la asignación real también es mucho más lenta.

Sin embargo, la versión “mala” anterior tiene una ventaja, y es cuando desea que las dimensiones individuales tengan una longitud variable, como cuando se crea una tabla de búsqueda para cadenas. Entonces tienes que usar ese formulario. Pero si desea una matriz 2D real, nunca hay una razón para no usar la primera.


Tenga en cuenta que la primera versión generalmente se escribe como

type (*array) [Y] = malloc( sizeof(type[X][Y]) );

para permitir un uso más conveniente: array[i][j]en lugar de la menos legible (*array)[i][j].

  • Buena explicación y más uno de mí, pero ¿por qué? (*array)[Y] puede permitirle acceder/asignarlo mediante el uso de array[i][j] pero cuando lo creas usando (*array)[X][Y] tienes que usar (*array)[i][j] para la manipulación después?

    – Yahya

    31 de diciembre de 2017 a las 12:59


  • @Yahya con int (*array)[Y] , array es un puntero a una matriz de tamaño Y. Esto significa que tiene dos niveles para eliminar la referencia, por lo que array[row] da una matriz, y array[row][col] te da el int. Con int (*array)[X][Y], ahora hay 3 niveles: es un puntero a una matriz 2D de enteros. Entonces necesitas el primero (*array) estrella para permitir el acceso al doble índice.

    –Scott Staniewicz

    20 de febrero de 2018 a las 16:28

¿La mejor manera de asignar memoria a una matriz bidimensional
StoryTeller – Unslander Mónica

data_type (*mat)[size_2] = malloc(size_1 * size_2 * sizeof(data_type));

Eso asignará memoria contigua para una matriz de matrices (“matriz 2d”). Si no requieres ridículo1 cantidades de espacio, este es el camino a seguir. Disminuirá la fragmentación de la memoria, aumentará la compatibilidad con la memoria caché y evitará demasiada sobrecarga debido al uso de malloc.


1 Para alguna definición (específica de la aplicación) de ridículo

  • Aún mejor sería data_type (*mat)[size_2] = malloc( sizeof *mat * size_1 );. sizeof *mat es equivalente a sizeof (data_type[size_2]).

    – Juan Bode

    28 de noviembre de 2016 a las 15:24

  • @JohnBode, gracias. Yo estaba bajo la impresión (equivocada) sizeof no se comportará bien para los VLA

    – StoryTeller – Unslander Mónica

    28 de noviembre de 2016 a las 15:28

  • Con respecto a los VLA, la situación no está 100% clara. Sí, si lee el estándar literalmente, mi versión debería invocar UB si mat es un VLA. Sin embargo, algunos de nosotros somos de la opinión de que la norma está mal redactada en ese sentido. No hay razón por la que deberías tener que desreferenciar el puntero para obtener las dimensiones de un VLA. La implementación debe transportar algún tipo de metadatos para que funcionen los VLA; no hay razón para creer que no puede usar esos metadatos al evaluar sizeof.

    – Juan Bode

    28 de noviembre de 2016 a las 15:34


Dado un tamaño fijo, simplemente puede decir twoDimArray[100][100], que lo asignará en la pila. Sin embargo, al asignar en el montón (ya sea porque el tamaño es muy grande o porque el tamaño es dinámico) tiene más opciones.

Puede asignar una matriz de punteros y luego recorrer la asignación de memoria para cada fila. Esto es problemático para la localidad de caché, pero muy bueno si el tamaño es muy grande y su acceso es secuencial; permite una cantidad razonable de fragmentación sin un impacto masivo en el rendimiento, porque la matriz de matrices puede estar separada de las propias matrices, que pueden estar separadas entre sí. En un escenario de acceso lineal, usted principalmente no estar saltando entre regiones de memoria; más bien, accederá a través de una línea completa antes incluso de mudarse a una nueva región.

La segunda forma es linealizar el acceso y asignarlo todo a la vez; es decir, asigne suficiente memoria para sizex * sizey y luego indexarlo con (positiony * sizex) + positionx; es decir, cuente algunas filas y luego algunas columnas. Esto es excelente para el acceso aleatorio y mejora la localidad de caché porque la memoria es contigua, pero podría fallar si no hay suficiente memoria contigua disponible (y el beneficio de localidad de caché no es aplicable si necesita más memoria que caché).

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad