Optimisation et gestion des listes sur Nspire
Posted: 17 Mar 2011, 14:20Bonjour à tous,
Je vous présente aujourd'hui les résultats d'une démarche expérimentale que j'ai réalisée sur des optimisations possibles de vos programmes utilisant intensément les listes (Comme Make3D pour ma part).
Déjà, tout le monde l'aura remarqué, la gestion des listes sur Nspire est horrible; rajouter un élément demande un temps quadratiquement proportionnel au nombre d'éléments déjà présents dans la liste. Pourtant cela n'est pas anodin.
Dans un premier temps j'ai alors réalisé un mini gestionnaire de mémoire virtuelle totalement en TI-Basic afin de voir si la gestion des listes foireuse était due à un mauvais code. Après plusieurs benchs, il s'est avéré que l'ajout d'éléments était beaucoup plus rapide (création d'un nouveau bloc, assignation de la valeur), mais la suppression, elle demandait un temps supplémentaire non négligeable. Si on compte création puis suppression, les benchs de ma mémoire virtuelle équivalaient à ceux des fonctions préconçues. Ce test est important pour comprendre la conclusion.
Quelques mois se sont écoulés, j'ai acquis de nouvelles connaissances algorithmiques, notamment sur la gestion de blocs dynamiques et listes chaînées. En effet si les listes implémentées étaient dynamiques l'accès à un Ieme élément serait beaucoup plus long. Etant donné que je n'ai pas réalisé de benchs convainquant sur l'accès des éléments, car de durée infime, cela ne prouvait rien. En effet, en structure dynamique, ajouter un élément en fin nécessite de parcourir toute la liste.
C'est donc là que j'ai pensé à un petit test avec la fonction augment(list, list).
Ajout en fin (durée : 15 secondes):
l:={}:for i, 1, 1000:l:=augment(l, {i}):Endfor:1
En tête (durée : 15 secondes):
l:={}:for i, 1, 1000:l:=augment({i}, l):Endfor:1
Fort est-il de constater que ce n'est pas une structure dynamique étant donné que la concaténation de deux listes ne dépend pas de la longueur de la 1ere.
La seule possibilité est donc l'inverse de la structure dynamique, c'est donc la structure statique où les éléments de la liste sont contigus dans la mémoire donnant un accès et des modifications rapides. Ainsi, on comprend la lenteur de la fonction augment(). A chaque appel de cette fonction, la Nspire va recréer un tableau de longueur X+Y en y recopiant chaque valeur de la liste X et de la liste Y.
La solution est donc, comme en C, de connaître la taille finale de la liste pour l'initialiser uniquement au début.
l:=newList(1000):for i, 1, 1000:l[i] = i:Endfor:1
prend 5 secondes contre 15 auparavant.
edit pour Bisam.
Je vous présente aujourd'hui les résultats d'une démarche expérimentale que j'ai réalisée sur des optimisations possibles de vos programmes utilisant intensément les listes (Comme Make3D pour ma part).
Déjà, tout le monde l'aura remarqué, la gestion des listes sur Nspire est horrible; rajouter un élément demande un temps quadratiquement proportionnel au nombre d'éléments déjà présents dans la liste. Pourtant cela n'est pas anodin.
Dans un premier temps j'ai alors réalisé un mini gestionnaire de mémoire virtuelle totalement en TI-Basic afin de voir si la gestion des listes foireuse était due à un mauvais code. Après plusieurs benchs, il s'est avéré que l'ajout d'éléments était beaucoup plus rapide (création d'un nouveau bloc, assignation de la valeur), mais la suppression, elle demandait un temps supplémentaire non négligeable. Si on compte création puis suppression, les benchs de ma mémoire virtuelle équivalaient à ceux des fonctions préconçues. Ce test est important pour comprendre la conclusion.
Quelques mois se sont écoulés, j'ai acquis de nouvelles connaissances algorithmiques, notamment sur la gestion de blocs dynamiques et listes chaînées. En effet si les listes implémentées étaient dynamiques l'accès à un Ieme élément serait beaucoup plus long. Etant donné que je n'ai pas réalisé de benchs convainquant sur l'accès des éléments, car de durée infime, cela ne prouvait rien. En effet, en structure dynamique, ajouter un élément en fin nécessite de parcourir toute la liste.
C'est donc là que j'ai pensé à un petit test avec la fonction augment(list, list).
Ajout en fin (durée : 15 secondes):
l:={}:for i, 1, 1000:l:=augment(l, {i}):Endfor:1
En tête (durée : 15 secondes):
l:={}:for i, 1, 1000:l:=augment({i}, l):Endfor:1
Fort est-il de constater que ce n'est pas une structure dynamique étant donné que la concaténation de deux listes ne dépend pas de la longueur de la 1ere.
La seule possibilité est donc l'inverse de la structure dynamique, c'est donc la structure statique où les éléments de la liste sont contigus dans la mémoire donnant un accès et des modifications rapides. Ainsi, on comprend la lenteur de la fonction augment(). A chaque appel de cette fonction, la Nspire va recréer un tableau de longueur X+Y en y recopiant chaque valeur de la liste X et de la liste Y.
La solution est donc, comme en C, de connaître la taille finale de la liste pour l'initialiser uniquement au début.
l:=newList(1000):for i, 1, 1000:l[i] = i:Endfor:1
prend 5 secondes contre 15 auparavant.
edit pour Bisam.
En effet, j'ai le même résultat sur TI 89 !
: 
