LUA / Matrices y arrays multidimensionales

Bienvenidos sean a este post, en el caso de hoy primero hablaremos sobre matrices de la cual tenemos dos formas de representarlas, la primera es usar un array de arrays que no es otra cosa que una tabla en donde cada elemento es otra tabla, por ejemplo podes crear una matriz de ceros con dimensiones N y M con el siguiente codigo:

mt = {}
for i = 1, N do
	mt[i] = {}
	for j = 1, M do
		mt[i][j] = 0
	end
end

Como las tablas son objetos en Lua tenes que crear cada linea explicitamente para crear una matriz, por un lado este es ciertamente mas detallado que simplemente declarar una matriz como hacemos en C o en Pascal, y por otro lado nos da mas flexibilidad. Otro ejemplo puede ser crear una matriz triangular cambiando el siguiente bucle:

for j = 1, M do

Por este otro:

for j = 1, i do

Con este codigo la matriz triangular usa solo la mitad de la memoria comparado con el anterior.

La segunda manera de representar una matriz en Lua es componiendo los dos indices en una sola una, si los indices son enteros puedes multiplicar el primero por una constante adecuada y luego agregar el segundo indice, con el siguiente codigo hara lo mismo que hicimos anteriormente:

mt = {}
for i = 1, N do
	for j = 1, M do
		mt[(i-1) * M + J) = 0
	end
end

En el caso de que los indices sean cadenas podemos crear un indice simple concatenando los dos indices con un caracter en el medio para separarlos, por ejemplo podemos crear una matriz con dos indices de tipo cadena s y t con el siguiente codigo:

m[s .. ":" .. t]

Informando que ambos s y t no contienen comas, dicho de otra manera pares como («a:», «b») y («a», «:b») colapsaran en un indice comun como es «a::b», ante la duda podes usar un caracter de control como ‘\0’ para separar los indices, a menudo las aplicaciones usan matrices dispersas las cuales son matrices en donde la mayoria de los elementos son 0 o nil, un ejemplo practico es a la hora de representar un grafico por su matriz de adyacencia, la cual tiene un valor x en la posicion m,n cuando los nodos m y n estan conectados con costo x, cuando estos nodos no estan conectados el valor en la posicion m,n es nil.

Para representar un grafico con 10000 nodos donde cada nodo tiene aproximadamente 5 vecinos, vas a necesitar una matriz con cien millones de entradas (una matriz cuadrada con 10000 filas y 10000 columnas) pero aproximadamente solo 50000 de ellos no seran nil.

Nota: 5 columnas no nil por cada linea, correspondiente a los 5 vecinos por cada nodo.

Muchos libros sobre estructura de datos discuten como implementar estas matrices dispersas sin desperdiciar 400 MB de memoria pero estas tecnicas no son necesarias cuando se programa en Lua porque los arrays son representadas por tablas y estas son naturalmente dispersas, con la primera representacion (tablas de tablas) necesitaras solamente de diez mil tablas cada una con aproximadamente cinco elementos dando como resultado un gran total de cincuenta mil entradas, y no importa cual sea la representacion solo necesitas espacio para los elementos no nil.

No podemos usar el operador de longitud sobre las matrices dispersas debido a los hoyos (valores nil) entre las entradas activas, esto no es una gran perdida porque incluso si lo usaramos no deberiamos usarlo, para la mayoria de las operaciones seria bastante ineficiente atravesar todas estas entradas vacias, el siguiente ejemplo sera para multiplicar una linea por una constante:

function mult(a, indicelinea, k)
	local linea = a[indicelinea]
	for i, v in pairs(linea) do
		linea[i] = v * k
	end
end

Sin embargo ten cuidado porque esas claves tienen un orden no intrinseco en la tabla, asi que la iteracion con pairs no asegura que visitemos las columnas en un orden ascendente, para algunas tareas (como las que vimos originalmente) no son un problema pero para otras tareas si pueden serlo y una solucion alternativa para esto son listas enlazadas, lo cual veremos en el proximo post.

En resumen, hoy hemos hablado sobre matrices y array multidimensionales, tambien conocidos como matrices dispersas, hemos sus ventajas y desventajas a la hora de trabajarlas, como se usan en LUA, como por medio de tablas podemos tener una mejor oportunidad, espero les haya sido util sigueme en Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.