Tutoriel Lua: Les tables - Les tampons pour chaînes de caractères.

Les tables: Les tampons pour chaînes de caractères.

Si vous voulez construire une chaîne de caractères au coup par coup, en lisant un fichier texte ligne par ligne, votre code ressemblera très certainement à ce qui suit.

	ATTENTION: Ce code est désastreux!!
	 
	local buff = ""
	for line in io.lines() do
	  buff = buff .. line .. "\n"
	end

Malgré son air innocent, ce code écrit en LUA peut causer une perte de performance énorme, si vous traitez un gros fichier.
Il faut en effet environ une minute, pour lire un fichier de 350 Ko.

C'est pourquoi LUA fournit la fonction io.read(), ("*all"), qui utilise un algorithme de collecte spécial, le garbage-collector, qui lira le fichier entier, en 0,02 seconde.

Quand LUA s'aperçoit que le programme utilise trop de mémoire, il libère alors les emplacements qui ne sont plus utilisés.
Habituellement cet algorithme a une bonne performance, contrairement à la boucle utilisée ci-dessus qui elle, utilise un très mauvais algorithme.

Explication:

Pour comprendre ce qui se passe, vous allez supposer que vous êtes dans le milieu de la lecture de la boucle.

La variable buff est alors une chaîne de caractères de 50 Ko constituée d'une suite de lignes de 20 octets.

Lorsque LUA concatène buff .. line .."\ n", il crée une nouvelle chaîne de 50 020 octets, puisqu'il ajoute les 20 octets de la nouvelle ligne aux 50 Ko de buff ...

Autrement dit, pour chaque nouvelle ligne, LUA déplace 50 Ko de mémoire (et plus au fur et à mesure)... Après la lecture de 100 lignes nouvelles de seulement 2 Ko ( 100 fois 20 octets), LUA aura pris plus de 5 Mo de mémoire. (100 fois 50 Ko).

Et pour empirer les choses, l'affectation précédente buff = buff..line.."\n" devient après coup, une donnée inutile...qui vient gonfler la mémoire.

Or, après 2 cycles, vous aurez donc 100 Ko de données inutiles en mémoire (2 fois 50 Ko)...

C'est à ce moment là, que LUA décide de lancer son Garbage collector et de libérer de la mémoire, ces 100 Ko qui ne servent plus à rien.

Le problème est que cela se produit tous les 2 cycles et que LUA gèrera alors son "Garbage collector" 2000 fois avant de lire le fichier en entier.

Même avec tout ce travail, l'utilisation de la mémoire sera quand même d'environ 3 fois la taille du fichier.

Pour les petites chaînes, la boucle ci-dessus est parfaite et pour lire un fichier entier, il suffit d'utiliser l'option ("*all") avec la fonction io.read(), qui lira le fichier dans son ensemble.

ET POUR LES GROS FICHIERS?:

La seule solution pour les gros fichiers, consiste en la mise en place d'un algorithme plus efficace, comme celui qui va suivre.

La première boucle, utilisait une approche linéaire du problème, à savoir, la concaténation de petites "strings" une par une dans un accumulateur.

Le nouvel algorithme utilisera une approche binaire, à savoir, la concaténation de plusieurs petites "strings" entre elles et la concaténation des chaînes résultantes de grande taille en plus grande..

Le coeur de cet algorithme est une pile qui conserve les chaînes de grande taille déjà créées dans le fond de la pile, tandis que les petites chaînes rentreront par le haut.

L'idée générale de cet algorithme est similaire à celui bien connu de certains programmeurs, sous le nom de "la tour de Hanoï".

Le principe étant qu'une chaîne de caractères ne peut jamais s'asseoir sur une chaîne plus courte.

Chaque fois qu'une nouvelle chaîne est poussée sur une plus courte, alors ( et seulement alors ) l'algorithme concatène les deux.

Cet enchaînement va créer une chaîne plus grande, qui pourra éventuellement, être plus grande que sa voisine de l'étage précédent. Si cela arrive, elles seront rejointes. Cet enchaînement descendra la pile jusqu'à ce que la boucle atteigne une chaîne encore plus grande, ou le bas de la pile.

	function newStack()
	  return {""}   -- démarrage avec une chaîne vide
	end

	function addString(stack, s)
	  table.insert(stack, s)  -- push 's' dans la pile
	  for i = table.getn(stack)-1, 1, -1 do
		 if string.len(stack[i]) > string.len(stack[i+1]) then
			break
		 end
		 stack[i] = stack[i] .. table.remove(stack)
	  end
	end

Pour obtenir le contenu final de la mémoire tampon, il suffit de concaténer toutes les chaînes vers le bas.
La fonction table.concat() fait exactement cela, elle enchaîne toutes les chaînes de cette liste... Ce qui donne:

	local s = newStack()
	for line in io.lines() do
	  addString(s, line .. "\n")
	end
	s = toString(s)

Ce nouveau programme permet de réduire les temps originaux.
Pour lire un fichier de 350 Ko, le programme passera de 40 secondes à 0,5 seconde.

L'appel à io.read() ("*all") est encore plus rapide, et finit le travail en 0,02 seconde.
io.read() utilise exactement la structure de données que nous venons de présenter, mais écrite en C.

Plusieurs autres fonctions dans les bibliothèques LUA utilisent également cette application écrite en C.

L'une de ces fonctions est table.concat().
.concat(), collecte toutes les chaînes dans une table, puis les concaténe toutes à la fois.
La fonction .concat() accepte un second argument optionnel, qui est un séparateur.
L'utilisation de ce séparateur, dispense d'insérer un saut de ligne après chaque ligne. ( "\n" qui doit être séparé par une virgule )

	local t = {}
	for line in io.lines() do
	  table.insert(t, line)
	end
	s = table.concat(t, "\n") .. "\n"

L'itérateur io.lines() retourne chaque ligne sans saut de ligne.
.concat insère le séparateur entre les chaînes, mais pas après la dernière. Il vous faudra donc ajouter le retour à la ligne à la fin de cette dernière.
Cette dernière concaténation duplique la chaîne qui en résulte et qui peut être très grande. Mais, il n'existe aucune option pour faire en sorte que .concat insère ce séparateur supplémentaire.
Mais vous pouvez le tromper, par l'insertion d'une chaîne vide supplémentaire en t:

	table.insert(t, "")
	s = table.concat(t, "\n")

La nouvelle ligne supplémentaire que .concat va créer avant cette chaîne vide se trouve à la fin de la chaîne qui en résulte.