Estructuras de Datos·Sesión 4 · Semana 2

Matrices y arreglos multidimensionales

miércoles 19 de agosto · 13:00–14:15 · hace 3 días

Guía del maestro.docx

GUÍA 19-08-26 Estructuras de Datos

CN122 · miércoles 19/08/2026 · 13:00-14:15 · Sesión 4

CÓMO SE GUARDA UNA MATRIZ

La memoria es lineal, así que una matriz bidimensional se aplana. C usa orden por renglones: primero todo el renglón 0, luego el 1, y así.

Para m[F][C], el elemento m[i][j] está en el desplazamiento i·C + j.
En orden por columnas —Fortran, MATLAB— sería j·F + i. Importa al interoperar entre lenguajes.

LOCALIDAD DE REFERENCIA

Recorrer por renglones es mucho más rápido que por columnas, aunque el número de operaciones sea idéntico. La razón es la caché: al leer m[i][j] el procesador trae toda una línea de caché, que contiene los siguientes elementos del renglón. Recorrer por columnas desperdicia cada línea traída.

Es la primera vez en el curso en que la disposición física de los datos, y no el algoritmo, determina el desempeño. No será la última.

DECLARACIÓN DINÁMICA

Arreglo de apuntadores: int **m = malloc(F * sizeof(int*)); y luego cada renglón por separado. Permite renglones de distinta longitud, pero pierde la contigüidad.
Bloque único: int *m = malloc(F * C * sizeof(int)); con acceso m[i*C + j]. Conserva la localidad y es lo que conviene para cálculo numérico.

MATRICES DISPERSAS

Si la mayoría de los elementos son cero, guardar F·C celdas desperdicia memoria. Se guardan solo los no nulos como tercias (renglón, columna, valor). Se ahorra espacio y se paga con acceso más lento: otra vez el intercambio entre tiempo y espacio.

PRÁCTICA

Suma y multiplicación de matrices; medir la diferencia de tiempo entre recorrido por renglones y por columnas con matrices de 1000×1000.

Mis notas311 palabras

# MATRICES: LA FILA ES CONTIGUA, NO LA COLUMNA
Un arreglo 2D en C se guarda por RENGLONES (row-major): primero todo el renglón 0, luego el 1, etc. En memoria es un bloque lineal, no una cuadrícula.
Dirección de a[i][j] = base + (i * COLUMNAS + j) * sizeof(tipo).
El compilador necesita saber el número de COLUMNAS para calcularla; por eso en un parámetro se puede omitir la primera dimensión pero no la segunda: void f(int m[][10], int filas).
# POR QUÉ IMPORTA EL ORDEN DEL RECORRIDO
Recorrer por renglones va leyendo posiciones contiguas y aprovecha la línea de caché; por columnas salta COLUMNAS*4 bytes cada vez y falla la caché en casi cada acceso.
El mismo algoritmo con los ciclos intercambiados puede tardar varias veces más SIN cambiar su complejidad: sigue siendo O(n·m). Es la diferencia entre la teoría y lo que mide el reloj.
# DECLARACIÓN ESTÁTICA Y DINÁMICA
- Estática: int m[3][4]; — bloque contiguo, tamaño fijo en compilación.
- Dinámica por arreglo de apuntadores: int **m = malloc(f*sizeof(int*)); y luego cada renglón por separado. Los renglones NO quedan contiguos.
- Dinámica contigua: int *m = malloc(f*c*sizeof(int)); y se indexa a mano con m[i*c+j]. Es más rápida y solo lleva un free.
# OJO CON LIBERAR
Con el arreglo de apuntadores hay que liberar CADA renglón y después el arreglo. Al revés se pierde la referencia y se filtra toda la matriz.
# MÁS DE DOS DIMENSIONES
La fórmula se generaliza: a[i][j][k] = base + ((i*D2 + j)*D3 + k)*tam. La última dimensión es la que varía más rápido en memoria.

(Notas reconstruidas del programa el 18-08. Contrastar con lo visto en clase y borrar esta línea al verificarlas.)
---
* TAREA PROPIA
1.- Medir con clock() el mismo recorrido por renglones y por columnas
2.- Investigar qué es una línea de caché y por qué son 64 bytes
3.- Implementar multiplicación de matrices con las dos formas dinámicas

.docx

Tareas propias de esta sesión

Nada anotado en esta sesión todavía.