Optimisation et gestion des listes sur Nspire

[Levak]

Bonjour à 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.

[critor]

Bravo.

Mais effectivement je me doutais que les listes TI étaient de simples tableaux dynamiques.

[Levak]

Bravo.

Mais effectivement je me doutais que les listes TI étaient de simples tableaux dynamiques.

Non justement, ils sont statiques.

[Lionel Debroux]

La gestion des listes n'est pas mieux que sur les TI-68k, je vois...
Peut-être utilisent-ils toujours le même genre d'algorithmes pour next_expression_index, sans avoir pris en compte le fait que Samuel Stearley avait fait 3-4 fois plus rapide pour cette routine cruciale...

[Bisam]

A mon avis, le plus efficace est d'utiliser la fonction "seq".

l:=seq(i,i,1,10000)

prend environ 5 secondes, affichage compris, ce qui est donc 10 fois plus rapide que la solution que tu proposes lorsque l'on connaît à la fois la longueur et les valeurs. Malheureusement, c'est rarement le cas.

Sans l'affichage, en tapant

l:=seq(i,i,1,15000):1

cela prend moins d'une seconde... mais on ne peut pas aller bien au-delà pour les tests sans avoir un "Dépassement de ressources. Calcul impossible".



PS : Pourquoi utilises-tu "matlist(newmat(1,1000))" au lieu de "newlist(1000)" ?

[Levak]

A mon avis, le plus efficace est d'utiliser la fonction "seq".

cela prend moins d'une seconde... mais on ne peut pas aller bien au-delà pour les tests sans avoir un "Dépassement de ressources. Calcul impossible".

seq() va justement instancier un nouveau tableau de 1000 éléments et les remplir de manière itérative.
Cela appuis donc mon raisonnement.

En fait, pour Make3D je ne peux pas utiliser seq() car c'est un raisonnement de simulation de face, j'aménage moi-même ma liste avec des éléments à undef pour couper le trait du nuage de point. Or j'utilise augment(), d'où la lenteur...

PS : Pourquoi utilises-tu "matlist(newmat(1,1000))" au lieu de "newlist(1000)" ?

Je l'avais cherchée rapidement dans la bibliothèque sans succès... maintenant, si elle existe ...

[Loulou 54]

Il faudrait que je regarde si ça fait la même chose sur 68k, ce qui fort probable. J'utilisais souvent la méthode "lente" justement.

EDIT : En effet, j'ai le même résultat sur TI 89 !

10 secondes pile pour une liste de 100 pour la méthode "longue"
contre 4 secondes pile pour une liste de 100 pour l'autre méthode !
[test réalisé sur VTI, la calculatrice physique mettrait sûrement moins de temps]

Cette méthode nécessite cependant de connaître à l'avance le nombre d'éléments de la liste, ce qui n'est pas toujours le cas, mais sinon, c'est bon à savoir !! =)

[Lionel Debroux]

[test réalisé sur VTI, la calculatrice physique mettrait sûrement moins de temps]

A moins que tu utilises une machine particulièrement asthmatique de nos jours (type Pentium 100), non. Les vitesses de VTI et TIEmu sont plutà´t fidèles :

Mais 4 secondes, pour créer une liste de 100 éléments (des entiers, de plus), est déjà  de l'abus...

[Folco]

lea -100*4(sp),sp
4 micro-secondes

[Loulou 54]

[test réalisé sur VTI, la calculatrice physique mettrait sûrement moins de temps]

A moins que tu utilises une machine particulièrement asthmatique de nos jours (type Pentium 100), non. Les vitesses de VTI et TIEmu sont plutôt fidèles

Mais 4 secondes, pour créer une liste de 100 éléments (des entiers, de plus), est déjà de l'abus...

Ti Emu, je n'ai pas fait gaffe, mais avec VTI, j'ai plus que l'impression que tout est plus lent ! (pas énormément non plus bien sûr.)
Bon, sauf si on décoche "restrict to actuall speed"