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:
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
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.
Plusieurs autres fonctions dans les bibliothèques LUA utilisent également cette application écrite en C.
L'une de ces fonctions est table.concat().local t = {} for line in io.lines() do table.insert(t, line) end s = table.concat(t, "\n") .. "\n"
table.insert(t, "") s = table.concat(t, "\n")