Discussion :

[darkontes]

bonsoir,
je continue dans mon jeu de la vie en camllight a avoir quelques soucis techniques car je maitrise encore tres mal les subtilités du langage

voila ou j'en suis
a savoir je considere qu'une cellule vivante contient un 1 et une morte un 0
et que la matrice est de dimensions n*p

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
(* donc la c'est la fonction qui permet de calculer le nombre de voisins a une case *)
let nb_voisins grille n p i j =
 let x = ref (-(grille.(i).(j))) in
    for k=(i-1) to (i+1) do 
     for t=(j-1) to (j+1) do
      x:=!x+(grille.((k+n) mod n).((t+p) mod p))
     done
    done;
!x;;
 
 
(*ici je cree une grille comprenant dans chaque cellule le nombre de cellule vivantes voisines*)
 
 
let grille_tremplin grille n p =
 let grille_aux = make_matrix n p 0 in
  for i=0 to (n-1) do 
   for j=0 to (p-1) do
    grille_aux.(i).(j)<-(nb_voisins grille n p i j)
   done
  done;
grille_aux;;
 
 
(*et la c'est ici que ca se gate je veux une fonction qui renvoie la grille apres une premiere evolution*)
 
let au_pas grille n p = 
 let grille_aux = grille in
  for i=0 to (n-1) do
   for j=0 to (p-1) do
    if ((grille_tremplin grille_aux n p).(i).(j)=2) then grille.(i).(j)<-grille.(i).(j)
    else if ((grille_tremplin grille_aux n p).(i).(j)=3) then grille.(i).(j)<-1
    else grille.(i).(j)<-0
   done
  done;
grille;;

je crois savoir d'ou vient le probleme mais ne sais pas le resoudre : je voudrais en fait creer une copie de la grille d'origine pour eviter justement ce qui se produit i.e. que la grille soit modifiée cellule par cellule et non pas d'un coup comme je le voudrais
enfin bon j'ai essayé mais je ne vois pas trop a part creer ce double hors de la fonction, mais ca c'est pas terrible ^^
donc je ne suis pas contre un autre petit coup de pouce =D

[Cacophrene]

Bonjour,

En fait, tu sembles avoir besoin de deux matrices parce que tu effectues des effets de bord. En d'autres termes, tu modifies l'état des cellules au fur et à mesure de l'analyse, ce qui pose problème pour les cellules suivantes. Deux solutions :

• Utiliser deux matrices, une pour l'état n et une pour l'état n + 1 de l'univers. Ça résout ton problème mais ça double la mémoire requise.
• Utiliser une méthode fonctionnelle, c.-à-d. utiliser Array.map (en Caml-light c'est map_vect).

Une piste :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
let voisinage cell =
  (* Code qui renvoie le nombre de cellules vivantes contiguës. *)

let etat_suivant cell =
  if voisinage cell ... then ... else ...
  (* Code qui détermine l'état suivant en fonction du voisinage. *)

(* Fonction qui applique etat_suivant à toutes les cellules. *)
let generation_suivante grille = Array.map (Array.map etat_suivant) grille

Remarque importante : en fait, si tu explores cette manière de procéder, tu verras que c'est un peu plus compliqué, car la fonction de voisinage a besoin des coordonnées (i, j) de la cellule pour fonctionner. Il y a une solution à ce problème, mais en Caml-light il faudra l'écrire soi-même (sauf erreur de ma part, on ne trouve la fonction que dans OCaml). Je détaillerai plus tard si ça t'intéresse.

Cordialement,
Cacophrène

[gasche]

En pratique la première méthode est beaucoup plus efficace, si on se contente de construire seulement deux tableaux (un pour les indices pairs, un pour les indices impairs) : le nombre d'allocations est constant.

Avec la deuxième méthode, d'une part tu doubles aussi la quantité de mémoire nécessaire (puisque qu'Array.map copie bien la même quantité de mémoire en interne), d'autre part tu rends le nombre d'allocations linéaires, et la quantité de mémoire sera aussi plus grande en pratique (puisqu'il faudra attendre le GC pour collecter les tableaux intermédiaires). Bref, ce sera nettement moins efficace.

[darkontes]

bon je vais d'abord utiliser la creation d'une deuxieme matrice car je vois bien comment faire et parce que mon devoir est pour vendredi et que comme je suis en prepa bah a coté il y a pas mal de travail. par contre l'autre methode m'interesse beaucoup donc je regarderais ca ce week end!

en attendant j'ai compris ce qu'etait un effet de bord

edit:
j'ai fait ca et ca a l'air a priori de fonctionner ^^

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
let au_pas grille n p = 
 let grille_aux =  make_matrix n p 0 in
  for i=0 to (n-1) do
   for j=0 to (p-1) do
    if ((grille_tremplin grille n p).(i).(j)=2) then grille_aux.(i).(j)<-grille.(i).(j)
    else if ((grille_tremplin grille n p).(i).(j)=3) then grille_aux.(i).(j)<-1
    else grille_aux.(i).(j)<-0
   done
  done;
grille_aux;;

[Cacophrene]

Bonsoir,

Avec la deuxième méthode, d'une part tu doubles aussi la quantité de mémoire nécessaire (puisque qu'Array.map copie bien la même quantité de mémoire en interne), d'autre part tu rends le nombre d'allocations linéaires, et la quantité de mémoire sera aussi plus grande en pratique (puisqu'il faudra attendre le GC pour collecter les tableaux intermédiaires). Bref, ce sera nettement moins efficace.

Tien on va inverser un peu les rôles : pour une fois c'est pas moi qui vais parler d'efficacité. Donc, oui c'est moins efficace, mais ce sera surtout visible pour de grands univers. J'ai utilisé les deux méthodes sur de petits univers (moins de 1000 par 1000) et les performances sont principalement limitées par le temps d'affichage des générations successives (avec Graphics comme avec LablGTK, et probablement aussi avec LablGL, la bibliothèque de dessin importe peu). Ça relativise la perte de performance de ce côté-ci. Et puis, ne pas oublier non plus que ça reste une implémentation naïve. Pour de grands univers, si on ne veut pas nécessairement afficher toutes les générations, il y a le puissant algorithme HashLife. Avec lui, on peut faire évoluer des univers de plusieurs milliards de cellules, avec un tout autre objectif, probablement très éloigné de l'exo de prépa.

Enfin, il y a l'intérêt pédagogique. Ça permet de montrer une version fonctionnelle de quelque chose d'assez commun et que l'on trouve presque toujours implémenté sous forme impérative. En Caml-light ce n'est pas super parce que Array.mapi n'existe pas, à ma connaissance, mais quand même. Ça permet même de dire que le « tout impératif » vs le « tout fonctionnel » est un mauvais débat !

Cordialement,
Cacophrène

[adtunum]

En fait il y a aussi une troisième méthode possible.
Et c'est justement cette troisième méthode qu'utilise Darkontes dans le code qu'il présente au début de ce fils de discussion.

On va l'appeler la méthode "tremplin" puisque la fonction de Darkontes qui implémente cette méthode contient ce nom.

Personnellement je serais plutôt d'avis d'inciter Darkontes à utililser la méthode tremplin, puisque c'est l'idée qu'il a eut. Et puis aussi c'est pas une mauvaise idée puisque ça contourne le problème de l'effet de bord de manière simple et efficace.

Pour ce qui est de la performance il peut très bien créer les deux matrices lors de l'initialisation avant d'entrer dans la boucle d'exécution du programme, puis utiliser tout le temps les même, ainsi le ramasse miette n'aura pas trop de travail.

Dans ton code le plus gros problème que je vois est dans cette portion de code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
let au_pas grille n p = 
 let grille_aux = grille in
  for i=0 to (n-1) do
   for j=0 to (p-1) do
    if ((grille_tremplin grille_aux n p).(i).(j)=2) then grille.(i).(j)<-grille.(i).(j)
    else if ((grille_tremplin grille_aux n p).(i).(j)=3) then grille.(i).(j)<-1
    else grille.(i).(j)<-0
   done
  done;
grille;;

tu applèles deux fois la fonction grille_tremplin à chaque itération, ce qui ne va pas. Tu devrais créer (ou plutot remplir) ta grille tremplin avant la double boucle for, ce qui donnerait quelque chose comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
let au_pas grille n p =
  let grille_tremplin = get_grille_tremplin grille n p in
  for i = 0 to (n-1) do
    for j = 0 to (p-1) do
      if grille_tremplin.(i).(j) = 2 then grille.(i).(j) <- grille.(i).(j)
      else if grille_tremplin.(i).(j) = 3 then grille.(i).(j) <- 1
      else grille.(i).(j) <- 0
    done
  done
;;

en ayant renommé la fonction "grille_tremplin" en "get_grille_tremplin".

[darkontes]

je prends note

je vais essayer (apres le ds de math ^^) de coder quelques autres programmes connus (enfin je n'en connais que deux autres : tours de Hanoï et triangle de vonKoch ) je vais faire attention aux remarques sur ce topic et sur le topic syntaxe ^^

d'ailleurs je dis pareil que sur le topic syntaxe =D

bon week end tout le monde