Bienvenidos sean a este post, vamos a suponer que estamos armando un cadena poco a poco, un ejemplo practico seria leer de un archivo linea por linea y tu tipico codigo seria:

Anuncios
local buff = ""
for linea in io.lines() do
	buff = buff .. linea .. "\n"
end

A pesar de su aspecto inocente este codigo puede generar gravisimos problemas de performance para archivos grandes, por ejemplo le tomaria alrededor de un minuto leer un archivo de 350 KB, y porque eso? Para entenderlo un poco mejor asumamos que estamos en el medio del bucle de lectura, cada linea tiene 20 bytes y ya hemos leido alrededor de 2500 lineas asi que buff es una cadena con 50 KB cuando Lua concatena a buff:

buff .. linea .. “\n”

Este crea una cadena con 50020 bytes y copia 50000 bytes de buff dentro de esta nueva cadena y asi por cada linea nueva, el lenguaje mueve 50 KB de memoria y creciendo, despues de leer cien lineas nuevas (alrededor de 2KB) se habran movido mas de 5 MB de memoria, siendo mas especificos este algoritmo es cuadratico ocasionando que Lua al finalizar de leer los 350 KB habra movido alrededor de 50 GB de memoria. 🤯

Anuncios

Pero este problema no es solamente de Lua, otros lenguajes donde las cadenas son valores inmutables poseen una conducta similar, siendo Java el mas infame de ellos.

Antes de continuar aclaremos un par de cosas: la situacion comentada anteriormente no es de las mas habituales, el codigo anterior para cadenas pequeñas funciona perfectamente y para leer un archivo entero Lua provee una opcion:

io.read("*all") 

La cual lee el archivo de una vez, sin embargo en algun momento podemos tener que enfrentar una situacion similar a la anterior, en el caso de Java tenemos a StringBuffer para mejorar este problema, en Lua podemos usar una tabla como un buffer de cadenas, la clave para este concepto es la funcion table.concat la devuelve la concatenacion de todas la cadenas de una lista informada, tomemos el ejemplo anterior y modifiquemoslo para usar concat:

local t = {}
for linea in io.lines()
	t[#t + 1] = linea .. "\n"
end
local s = table.concat(t)

Con este simple algoritmo nos toma aproximadamente 0,5 segundos leer el archivo a diferencia del minuto con el codigo anterior porque en este caso al maximo de la tabla le incrementaremos en uno y agregaremos la linea, una vez cargada la tabla procedemos a concatenarlo y listo.

Nota: Como dijimos antes una mejor opcion es utilizar io.read("*all") para los casos donde se debe leer todo un archivo.
Anuncios

Pero inclusive este codigo puede ser mejorado, la funcion concat acepta un segundo argumento opcional el cual es un separador para ser insertado entre las cadenas, con este separador no es necesario agregar al modificador de nueva linea (\n) por cada linea:

local t = {}
for linea in io.lines()
	t[#t + 1] = linea
end
s = table.concat(t, "\n") .. "\n"

Si bien concat agrega el separador entre las cadenas pero aun asi tenemos que agregar la nueva linea, esta ultima concatenacion duplica la cadena resultante la cual puede ser un poco larga, como no hay ninguna opcion para hacer a concat insertar este separador extra nosotros podemos engañarlo insertando una cadena vacia extra a t:

t[#t + 1] = ""
s = table.concat(t, "\n")

Esta ultima nueva linea que agregamos gracias al caracter vacio resulta en el caracter de nueva linea vacio que queriamos del ejemplo anterior, en otro tema tanto concat como io.read(“*all”) internamente utilizan el mismo algoritmo para concatenar pequeñas cadenas, otras funciones de las librerias estandar tambien usan este algoritmo para crear cadenas largas, echemos un visto a como trabajan.

Anuncios

Nuestro bucle original toma un enfoque lineal al problema concatenando pequeñas cadenas una por una dentro de un acumulador, este nuevo algoritmo evita esto usando un enfoque binario en su lugar porque concatena muchas pequeñas cadenas entre ellas y ocasionalmente concatena las cadenas grandes resultantes dentro de unas mas grandes, el corazon del algoritmo es una pila que mantiene las cadenas largas ya creadas en el fondo, mientras las cadenas chicas entran por la parte superior, la principal invariante de esta pila es similar a la popular torre de Hanoi (por lo menos entre los programadores), una cadena en una pila nunca puede ubicarse sobre una cadena mas corta, solo cuando una nueva cadena es empujado sobre una mas corta y luego (solo luego) el algoritmo concateno a ambos, esta concatenacion crea una cadena mas grande la cual podria ser mas grande que su vecino en el piso previo, si esto ocurre ellos estan unidos tambien, estas concatenaciones va a la parte inferior de la pila hasta que el bucle alcanza una cadena mas grande o la parte inferior de la pila, veamos un ejemplo:

function agregarCadena(pila, c)
	pila[#pila + 1] = c
	for i = #pila-1, l, -1 do
		if #pila[i] > #pila[i + 1] then
			break
		end
		pila[i] = pila[i] .. pila[i + 1]
		pila[i + 1] = nil
	end
end

Esta funcion recibe dos argumentos, nuestro primer paso sera agregar el valor de c en pila en la posicion mas superior, luego usaremos un bucle for que comenzara desde el puesto superior de la pila y luego ira restando de a un paso (-1), en el bloque tendremos un condicional donde si el indice i de la pila es mayor que el indice i + 1 de pila interrumpe el bucle con un break, de lo contrario concatenara en pila el valor de pila con el superior y a esta posicion superior le asignaremos el valor nil, para conseguir los contenidos finales de este buffer solamente concatenamos todas las cadenas hacia el fondo.

Anuncios

En resumen, hoy hemos visto como trabajan los buffers de cadena, hemos visto su estructura, varios ejemplos, algunos inconvenientes al usarlo y como solucionarlos, 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.

Tambien podes donar

Es para mantenimiento del sitio, gracias!

$1.00