Previous Up Next

2.5.3  L’affectation par référence dans une variable désignant un élément d’une liste ou d’une matrice : =<

On peut utiliser l’opérateur infixé =< pour stocker par référence le deuxième argument dans une variable (désignant un élément d’une liste ou d’une matrice) donnée comme premier argument.
Voir aussi 9.4.16 et 9.4.15. On tape :

a:=[1,2,3,4,5]

Pour changer la valeur de a[1] il est préférable de le faire par référence c’est à dire sans faire de recopie, on tape :

a[1]=<5

Dans un programme, il est préférable d’utiliser l’opérateur infixé =< pour changer un élément d’une liste ou d’une matrice contenue dans une variable . Pour initialiser la liste :
si on connait la dimension N de la liste, on peut initialiser la liste par :
L:=makelist(0,1,N);.
On peut aussi vouloir initialiser la liste L par la liste vide et dans ce cas il faut mettre L:=[0$0] et ne pas mettre L:=[]. La différence est subtile : [0$0] est une liste qui est crée lors de chaque exécution du programme alors que après la compilation du programme, L:=[] fait pointer L sur la liste [] et cette liste sera modifiée par les différents L[k]=<
Exemple : 3 programmes simples qui renvoient la liste [0,1,2..n] et 1 programme qui n’est pas correct On tape :

fonction refere0(n)
  local k,L;
  L:=[];
  pour k de 0 jusque n faire
    L:=append(L,k);
  fpour;
  retourne L;
ffonction:;
fonction refere1(n)
  local k,L;
  L:=[];
  pour k de 0 jusque n faire
  L[k]=<k;
  fpour;
retourne L;
ffonction:;
fonction refere2(n)
  local k,L;
  L:=[0$0];
  pour k de 0 jusque n faire
    L[k]=<k;
  fpour;
retourne L;
ffonction:;
fonction refere3(n)
  local k,L;
  L:=makelist(0,0,n);
  pour k de 0 jusque n faire
    L[k]=<k;
  fpour;
retourne L;
ffonction:;

Comparons les temps d’exécution des programmes refere0 et refere3.
On tape :
time(refere0(1000))
On obtient :
[0.065,0.059091699]
On tape :
time(refere3(1000))
On obtient :
[0.0065,0.0057686072]]
Le programme refere3 est correct et rapide : lorsque n est très grand refere0(n) est très lent car pour chaque affectation L:=append(L,k); il y a une recopie de append(L,k) dans L.
Testons ces programme :
On tape :
refere2(10)
ou
refere3(10)
On obtient :
[0,1,2,3,4,5,6,7,8,9,10] On tape :
refere2(3)
ou
refere3(3)
On obtient :
[0,1,2,3] Mais le programme refere1 n’est pas correct:
On tape :
refere1(10)
On obtient :
[0,1,2,3,4,5,6,7,8,9,10] Mais si on tape :
refere1(3)
On obtient :
[0,1,2,3,4,5,6,7,8,9,10] En effet si on tape :
refere1
On obtient le texte source :

(n)-> 
{ local k,L; 
  L:=[0,1,2,3,4,5,6,7,8,9,10];  
  pour k de 0 jusque n faire array_sto(k,L[k]) 
   fpour;;  
  return(L);  
}

On voit que le texte source a été modifié puisque après l’exécution de refere1(10) L a été modifié en :
L:=[0,1,2,3,4,5,6,7,8,9,10];.
Dans refere2, on a mis L:=[0$0], cela signifie qu’une copie de la a liste vide est créée dans L à chaque exécution.
Dans refere1, on a mis L:=[], cela signifie que la liste vide est crèèe lorsque refere1 a été interprété et L pointe vers cette liste vide (i.e. L a la même adresse que la liste vide). Donc L[k]=< k va modifier L donc aussi cette liste vide (qui ne sera donc plus vide !).
Le programme refere1 est donc modifié.
Dans refere3, on a mis L:=makelist(0,0,n); dans ce cas la liste composée de n zéros est créée dans L à chaque exécution. Autre exemple
On cherche pour tout n∈ ℕ, la liste des nombres entiers k vérifiant 0<k<2n et dont la somme des chiffres, dans l’écriture en base 2, est égale à p ou qui s’écrivent en base 2 avec des 0 et p 1.
On sait que convert(k,base,2) renvoie la liste de 0 et de 1 de l’écriture en base 2 de k en commençant par le chiffre des unités. On a, par exemple :
convert(2,base,2)=[0,1].
On connait la longueur de la liste résultat qui est comb(n,p) puisque il peut y avoir n chiffres et que parmi ces n chiffres il doit y avoir p 1. On peut donc initialiser la liste par :
L:=makelist(0,1,comb(n,p));.
On peut aussi vouloir initialiser la liste L par la liste vide et dans ce cas il faut mettre L:=[0$0] et ne pas mettre L:=[]. La différence est subtile : [0$0] est une liste qui est crée lors de chaque exécution du programme alors que après la compilation du programme, L:=[] fait pointer L sur la liste [] et cette liste sera modifiée par les différents L[k]=<j en LR et restera modifiée en fin d’exécution ce qui fait que si on effectue une autre exécution du programmeL est initialisée par LR car elle pointe sur la liste LR.
On tape :

truc(p,n):={
 local j,k,L;
 L:=makelist(0,1,comb(n,p));
 k:=0;
 for (j:=2^p-1;j<=2^n-2^(n-1-p);j++){
  if (sum(convert(j,base,2))==p){
    L[k]=<j;
    k:=k+1;
  };
 }
 return L;
}:;

Puis : J:=truc(10,17):;J[0];J[10] renvoie : Done,1023,2046
convert(1023,base,2) renvoie [1,1,1,1,1,1,1,1,1,1]
convert(2046,base,2) renvoie [0,1,1,1,1,1,1,1,1,1,1]
Comme la liste J a pour longueur comb(17,10)=19448 si on met dans le programme L[k]:=j; au lieu de L[k]=<j;, Xcas effectue 19448 recopie de cette liste ce qui allonge l’execution du programme....


Previous Up Next