Récursivité - Page 1

Yop là
Glop glop,

J'suis confronté à un problème assez chiant mais pas extrêment handicapant.

J'avais fait, y a assez longtemps, une fonction qui supprime les doublons d'une liste.

auche, droite)->l EndIf EndFor:EndFor l->main/lout ENdPrgm

J'vous file le pseudo-code, me souviens pas exactement de tout
ndbl(l)
Prgm
TriCroi l
For x,1,dim(l)
l[x]->a
0->n
For y,x+1,dim(l)
l[y]->b
If a=b: n+1->n
If a!=b Then
© On coupe la liste en deux :
//SI j'ai {1,5,2,3,1} en argument
//J'aurais {1,1,2,3,5} après TriCroi (SortA)
//Puis je couperais en prenant {1 et ,2,3,5}
//Et je collerais les morceaux que je foutrais dans la liste.
//En gros : augmente(g

En bref, ça utilise TriCroi pour ne pas devoir relire depuis le début de la liste à chaque itération de for.
Le problème, c'est que vu que j'utilise TriCroi, je peux pas faire un Func:...:EndFunc. Du coup je suis obligé d'appliquer une récursivité en appelant la fonction et en lui donnant la liste en argument.
Le problème, c'est :
- Comment faire une récursivité en TiBASIC ?
- Comment savoir quand la liste n'a plus aucun argument en doublon ?

Le code c'est du de mémoire (et c'est l'idée très générale), j'essayerai de vous retrouver ça.

Merci d'votre aide et des infos éventuelles

regarde topics/125548-parcourir-un-arbre#2 pour un exemple de récursivité. c'est tout bête, tu n'as qu'à rappeler la fonction dans laquelle tu es.
Mais tu n'as pas besoin de récursivité dans ce cas. tu n'as qu'à parcourir tous les éléments de ta liste et quand un élément est égal au précédent, tu le supprimes. Tu sais qu'il n'y a plus de doublon quand tu es arrivé à la fin de ta liste

(note : for x,1,dim(l) c'est moche, c'est lent car l'expression est évaluée à chaque itération. Merci Zephyr pour m'avoir appris ça)

FireHunter (./1) :
J'avais fait, y a assez longtemps, une fonction qui supprime les doublons d'une liste.

Pourquoi tiens-tu absolument à utiliser TriCroi ?

sort(list)
dim(list)-1->a
1->b
Loop
if list[b]=list[b+1]
then augment(left(list,b),mid(list,b+2))->list
else
b+1->b
endif
LoopWhile b=/=a

C'est dans le cas où mid(list,x) retourne la liste à partir de l'élément x (me souviens plus bien).

Ca serait pas plus rapide ?

Folco (./4) :

FireHunter (./1) :
J'avais fait, y a assez longtemps, une fonction qui supprime les doublons d'une liste.

Pourquoi tiens-tu absolument à utiliser TriCroi ?

sort(list)
dim(list)-1->a
1->b
Loop
if list[b]=list[b+1]
then augment(left(list,b),mid(list,b+2))->list
else
b+1->b
endif
LoopWhile b=/=a

C'est dans le cas où mid(list,x) retourne la liste à partir de l'élément x (me souviens plus bien).

Ca serait pas plus rapide ?

Pas mal l'astuce du sort(list) avant de virer les doublons.
Normalement si TI a bien implementé le sorting des listes de façon a ce que ce soit rapide,
je dirais que ta technique n'a pas son pareil en TI basic.

Par contre je pense que créer une nouvelle liste est tout s.implement plus rapide a faire que de manipuler la liste entière a chaque itération.

sort(list)
local n, j, tri, i
dim(list)-1->n
2->i
list[1]->tri[1]
For j,1,n
 if list[j]=/=list[j+1] then 
  list[j+1]->tri[i]
  i+1->i
 endif
EndFor
return tri

ça se pourrait en effet.

J'avais pas pensé, mais à voir, parce que à chaque itération, tu vas faire :
- 2 manips de list si 'y a un doublon
- 4 manips s'il n'y a pas des doublons

J'ai codé l'inverse, donc à priori, avantage à ta méthode s'il y a plus de doublons que d'éléments uniques, sinon à la mienne.

Comme promis, voilà la source

nodble3(l)
Prgm
Local l,x,...©ETC ^^
SortA l
For x,1,dim(l)
l[x]->a
0->n
For y,x+1,dim(l)
l[y]->b
If a=b:n+1->n
If y<dim(l) Then
If l[y+1]!=a:Exit
EndIf
EndFor
augment(left(l,x),right(l,dim(l)-x-n))->l
EndFor
l->main/lout
EndPrgm

En gros :
{1,1,1,2,5,4,5,1,2}->l
SortA l
On obtient {1,1,1,1,2,2,4,5}
Ensuite, la première For
Je lis l[1], soit 1.
Deuxième For.
Je lis l[2], soit1
l[1]=[l2] donc n=1.
Fin de l'itération du deuxième for, la condition de sortie de deuxième for n'est pas remplie (car l[2]=l[1])
Ensuite, le for lis le l[3], donc 1
Pareil que précédemment. On a donc n=2
Nouvelle itération de deuxième boucle.
On a l[4]=2
l[4] != l[1] DONC n=2 et pas 3
Ensuite, vu que la condition de sortie est respectée, EXIT.
Ensuite je coupe la liste, et j'obtient
{1,2,5,4,5,1,2}->l

Et pareil pour chaque élement.

j'sais pas si c'est clair :s

augment(left(l,x),right(l,dim(l)-x-n))->l

Pas compris tout ton algo, mais un augment(left(),mid()) te ferait faire beaucoup moins d'opération, dégagerait le dim() etc...

Folco (./7) :
J'avais pas pensé, mais à voir, parce que à chaque itération, tu vas faire :
- 2 manips de list si 'y a un doublon
- 4 manips s'il n'y a pas des doublons

J'ai codé l'inverse, donc à priori, avantage à ta méthode s'il y a plus de doublons que d'éléments uniques, sinon à la mienne.

Je pense que ton compte n'est pas exact :

Folco (./4) :

....
augment(left(list,b),mid(list,b+2))->list
....

Voici le nombre de fois que tu manipules les listes s'il n'y a pas de doublon :
- if( list[ b]==list[b+1] : 2 acces aux éléments de liste
- left, mid, augment : 3 fonctions de manipulation de liste
- list : 2 appels du nom de la variable dans l'expression
- ->list : pour sauvegarder le résultat du calcul en memoire

Ca fait 8 manipulations de liste au total, s'il n'y a pas de doublon.

Sachant comment fonctionne le TIOS lorsqu'il évalue les expressions( à coup de recopie dans la pile de de vérification de la structure des données), autant laisser tomber les manipulations de listes.

si c'était moi je ferais

-calcul du nb d'éléments qu'on aura a la fin
-alloc de la liste finale avec seq() ou autre chose
-copie des éléments intéressants.

ainsi on a UNE alloc de liste, et des remplacements dans la liste existante.

je ne vois pas comment tu peux calculer le nombre d'éléments que tu auras à la fin sans calculer la liste sans les doublons

tu fais comment pour le calcul du nombre d'éléments qu'on aura à la fin ?
Tu parcours rapidement la liste pour compter le nombre d'éléments différent.
Ça revient donc à la même chose que de procéder comme je l'ai fait.

On essaie d'optimiser l'algorithme en minimisant le nombre de manipulation de listes.

J'essaie de modifier mon code en comptant le nombre d'éléments contigus différents pour les ajouter en une seule fois à la liste à retourner.
Je pense que c'est de ce coté là qu'on peut encore optimiser.

T'as raison, j'ai très mal compté dans mon code, mais ça reste dépendant du nombre de doublons. Ca serait donc à tester avec ce qu'il pense avoir comme proportion de doublons.

je suis sur qu'on peut compter le nb d'éléments uniques sans autre liste intermédiaire. en stockant les index des éléments cherchés.

Mais on n'attend que ton code.

et donc tu crées une autre liste. et tant qu'à stocker les index, autant stocker les éléments. et tu obtiens la liste que tu cherches

Voici une version optimisée du code qui compte le nombre d'éléments contigus différents et les sauvegarde en une seule fois.

Voilà Folco, on tire parti de nos 2 méthodes.

sort(list)
Prgm
local m, n, j, tri, i
list[1]->tri[1]
dim(list)-1->n
0->m
2->i
For j,1,n
 if list[j+1]=/=list[j] then 
  m+1->m
 else
  if(m==1) list[j+1]->tri[i]
  else augment(tri,mid(list,j-m,m))->tri
  i+m->i
  0->m
 endif
EndFor
return tri
EndPrgm

Code critque :

augment(tri,mid(list,j-m,m))->tri

le code critique fait 5 manipulations de listes.
lorsque m=2, on peut encore optimiser en sauvant élément par élément.
lorsque m>2, le nombre de manipulation de listes éléments par élément est > 5


En conclusion, voici une version satisfaisante :

sort(list)
Prgm
local m, n, j, tri, i
list[1]->tri[1]
dim(list)-1->n
0->m
2->i
For j,1,n
 if list[j+1]=/=list[j] then 
  m+1->m
 else
   if(m==1) list[j+1]->tri[i]
   else if(m==2) then
     list[j]->tri[i]
     list[j+1]->tri[i+1]
   else augment(tri,mid(list,j-m,m))->tri
   endif
   i+m->i
   0->m
 endif
EndFor
return tri
EndPrgm

dommage que ça ne marche pas, tu ne peux pas retourner de valeur avec un prgm
sinon faut quand même se méfier des optimisations de prog tibasic sur le papier, tu peux penser optimiser et obtenir un truc plus lent

Merci pour vos réponses, je n'fais que passer, j'ai de la Physique à bosser
Vais regarder tout ça.

Par contre, pour adapter ça en C, j'suis largué. En effet char ça sert aussi bien pour les listes que pour les châines de caractères, non ? Puisqu'une chaine de caractère c'est une liste de ses caractères... 'Fin bref, pour la manipulation des listes de chaines en C je suis un peu largué *part réviser*

Hum, si ton but est de faire ca en basic, alors je ne peux que te conseiller d'éviter au maximum les parcours de listes.
Dans ton cas, pour enlever les doublons il y a peut-être moyen de jouer avec la fonction seq.
Une approche possible :
- Trier la liste
- Faire un seq qui remplace tous les doublons par la valeur minimum-1 de la liste
- Trier à nouveau la liste
- Supprimer tous les éléments de gauche correspondant à la valeur minimum
Pour le seq, tu peux faire : seq( when( list[ i ] = list[ i-1 ], min(list)-1, list[ i-1 ] ), i, 2, dim(list) )
Reste à gérer les bornes ( la tu dois perdre un élément )
(Bon avec un pré-calcul du min et du dim bien sur !)

Après si ton but est de le faire en C, c'est pas ce genre d'approche qu'il faut avoir^^

Sincerement aze, tu sais ce qu'il faut faire pour changer des
Prgm .... Prgm en Func........EndFunc

Je pense pas qu'on va polémiqué sur ça, ce n'est pas le but du débat.


Et je parle peut-être théoriquement, mais j'ai un fait des essaies de librairies basic du genre VERTEL,
alors j'ai grosso-modo une idée de comment le TIOS évalue les expressions.

Après t'as plus qu'à tester lequel des codes est le plus rapide

bobti89, ça donne quoi concrètement en code Ti-Basic ton algorithme ?

Ca donne ca :

Prgm
  Local i, m, s, l1
  SortA l
  dim(l) -> s
  l[1]-1 -> m
  seq( when( l[i-1]=l[i], m, l[i] ), i, 2, s ) -> l1
  l[i] -> l1[s]
  SortA l1
  1 -> i
  While ls[i]=m
    i+1 -> i
  EndWhile
  right(l1,s-i+1)- > l
EndPrgm

( Programme qui trie et enlève les doublons de l )

Bon ensuite faudrait éviter la boucle de recherche du nombre de doublons. J'ai bien une idée mais pas sur qu'on gagne sauf s'il y a vraiment beaucoup de doublons

Et puis il y a peut-être d'autres méthodes, car la c'est quand même lourd et ca doit gagner que sur des listes d'une certaine taille^^

Un autre solution peut-etre serait de:
- Trier la liste,
- faire un gradient de la liste (faire une liste correspondant a (element i+1)-(element i),
- Creer un liste et copier le premier element puis ensuite tous les elements dont la valeur dans la liste de gradient est differente de 0.

En gros, ca donnerait ca:

Prgm
   local i,grad,siz,newl
   dim(l)>siz
   sortA l
   deltaList(l)>grad                                              % Function delatlist du menu Math>Liste
   {l[1]}>newl
   for i,2,siz
     if grad[i-1]>0
       augment(newl,{l[i]})>newl
   end
   newl>l
endprgm

dal, Tu sais quoi, la TI manque effectivement de fonctions de manipulation de listes comme :

- purgeList(list,purgeListItems) : supprime tout les items de purgeListItem dans list

tiens, c'est vrai.
ça doit pouvoir se coder en C.

Hum ma solution est vraiment trop lourde et inefficace^^
Voici une autre solution meilleure :

rm_d( list )
Func
  Local i, j, s, t
  1 -> j
  dim(list)-1 -> s
  list[s+1] -> t
  For i,1,s
    If list[i] != list[i+1] Then
      list[i] -> list[j]
      j+1 -> j
    EndIf
  EndFor
  t -> list[j]
  left(list, j)
EndFunc

Cette fonction enlève les doublons d'une liste triée.
L'avantage est qu'elle ne crée pas de nouvelle liste, elle travaille directement dessus.

C'est obligatoire de faire ça en TI-BASIC ?
./28 risque d'être un peu lente pour les grosses listes, étant donné que ni la gestion des variables, ni la boucle For, ni l'accès à un élément arbitraire de la liste (à cause de next_expression_index()) ne sont rapides en TI-BASIC.

bobti89, en effet la nouvelle solution est quasi idem à la première que j'ai proposé exception faite des 2 points suivants :
- l'astuce de stocker dans la meme liste
- la suppression des éléments en trop à la fin

Le seul inconvéniant de ton programme c'est toujours le fait que tu code sur TI- Basic.
Les manipultions de petites listes sont préférables aux grandes.
Dans ton cas tu décides de manipuler une liste de la puls grande taille possible à chaque itération.
Alors que moi je commence par manipuler une liste de 1 élément, dont la taille augmente de 1 élément à chaque itération.
De plus ma liste n'atteindra pas forcément la taille de la liste la plus grande, que toi tu manipule à chaque fois que tu ajoutes un nouvel élément.

La manipulation d'une liste existante de taille n(=100) entraine à chaque itération la copie de toute la liste à n éléments dans la pile.
Ensuite vu que tu rajoutes pas à la fin de la liste, il fait implicitement un left et right supplémentaire sur ta liste( à coup de 2 memcopy)
pour insérer l'élément au milieu.

Je pense donc qu'il serait plus rapide de créer une nouvelle liste, puisque la taille de la liste va en grandissant et qu'on ajoute le nouvel
élément toujours à la fin( donc 1 seul appel implicite supplémentaire à memcopy).


Bon je pense que la fonction :
- purgeList(list,purgeListItems) : supprime tout les items de purgeListItem dans list
en C va faire du bien au programmeur Ti-Basic.

Je vais voir, dans mes vieux projets, si je peux bidouiller un pour faire ça.