Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

CAML - Contourner une exception mémoire

Posté par
Bcracker
29-08-09 à 17:32

Bonjour,

  Suite à  l'Enigmo 126 - Triancey, Enigmo 126 : Triancey, je me demande comment contourner une exception mémoire sous CAML. En effet, pour y répondre j'ai fais un petit programme CAML Light et lorsque j'essaie de tester tous les coloriages de plus de 6 triangles parmi les 23, CAML répond par une exception mémoire. Je voudrais, par curiosité, savoir comment on peut contourner cette exception mémoire et tester tous les coloriages possibles.

Merci d'avance

Posté par
Bcracker
CAML - Contourner une exception mémoire 29-08-09 à 17:36

Bonjour,

  Suite à  l'Enigmo 126 - Triancey Enigmo 126 : Triancey, je me demande comment contourner une exception mémoire sous CAML. En effet, pour y répondre j'ai fais un petit programme CAML Light et lorsque j'essaie de tester tous les coloriages de plus de 6 triangles parmi les 23, CAML répond par une exception mémoire. Je voudrais, par curiosité, savoir comment on peut contourner cette exception mémoire et tester ainsi tous les coloriages possibles.

Merci d'avance

*** message déplacé ***

Posté par
Bcracker
re : CAML - Contourner une exception mémoire 29-08-09 à 17:42

A cause d'un petit problème technique j'ai dû poster en double, si un modérateur passait par là, merci

*** message déplacé ***

Posté par
pythamede
re : CAML - Contourner une exception mémoire 30-08-09 à 14:49

Je ne connais pas CAML, et je n'ai même pas essayé de résoudre Triancey...

Pourquoi répondre alors ? Juste une petite remarque !

On peut parfois contourner telle ou telle réaction d'un compilateur. Mais si "exception mémoire" signifie "je n'ai pas assez de mémoire" je ne vois pas comment on pourrait contourner ça,..., sinon en changeant d'algorithme. Je suppose donc que, sciemment ou non, tu épuises les ressources mémoire de ta machine et si c'est bien cela, augmenter la mémoire de ta machine ou réduire les exigences de ton algorithme (en en changeant si possible) me paraît la seule solution ! Parfois les logiciels de très haut niveau (est-ce le cas de CAML ?) font tellement de choses à la place (et à l'insu) de l'utilisateur, qu'il leur arrive de créer des tableaux gigantesques...

Cela dit, quelqu'un qui connaît bien CAML peut peut-être t'aider à condition que tu lui donnes ton code !

Posté par
Bcracker
re : CAML - Contourner une exception mémoire 30-08-09 à 16:32

Merci pythamede pour ta réponse

Citation :
je ne vois pas comment on pourrait contourner ça,...


Justement je cherche un moyen de tester tous les coloriages de plus de 6 éléments parmi 23 (voir plus) possibles, quitte à changer l'algorithme.

Citation :
Cela dit, quelqu'un qui connaît bien CAML peut peut-être t'aider à condition que tu lui donnes ton code !


Déjà posté pour l'Enigmo 126 - Triancey Enigmo 126 : Triancey, je le remet ici :

Citation :

(*couleur = bool vect | tableau des triangles coloriés
  associes =(int vect) vect | tableau des tableau des triangles associés au triangle i.*)
(*exemple*)

(*Représentation : On représente un triancey par un tableau de tableaux de 3 éléments correspondant au triangle commun au triangle i+1.
Par exemple triancey.(0) renvoie le tableau des indices des triangles commun au triangle 1.
Un coloriage sera représenté par un tableau de booléens tel que coloriage.(i) renvoie true si le triangle i+1 est colorié, false sinon
*)

let triancey = [|[|2; 10; 9|]; [|1; 3; 18|]; [|2; 4; 12|]; [|3; 5; 20|]; [|4; 6; 14|];
    [|5; 7; 22|]; [|6; 8; 16|]; [|7; 9; 23|]; [|1; 8; 17|]; [|1; 11; 17|];
    [|10; 12; 19|]; [|3; 11; 13|]; [|12; 14; 21|]; [|5; 13; 15|]; [|14; 16; 22|];
    [|7; 15; 23|]; [|9; 10; 24|]; [|2; 19; 24|]; [|11; 18; 20|]; [|4; 19; 21|];
    [|13; 20; 22|]; [|6; 15; 21|]; [|8; 16; 24|]; [|17; 23; 18|]|]
;;
(*Procédé : pour un entier n donné, on va colorier toute les partie de n triangle dans les N triangles totaux. De la, on voit si tout est colorié.*)

(*====================================================== Fonctions préliminaires - Combinatoire (inspiré ESIM 99) ======================================*)
let prem ens = match ens with
    | [] -> failwith "Erreur dans prem"
    | t :: q -> t;;
let sp ens = match ens with
    | [] -> failwith "Erreur dans sp"
    | t :: q -> q;;
let rec siem i ens = match ens with
    | [] -> failwith "Erreur"
    | t :: q -> if i = 1 then q else t :: (siem (i - 1) q);;
let rec ieme i ens = match ens with
    | [] -> failwith "Erreur dans ieme"
    | t :: q -> if i = 1 then t else ieme (i - 1) q;;
let rec ajout e lst_ens = match lst_ens with
    | [] -> []
    | t :: q -> (e :: t) :: (ajout e q);;
(* Determinations d'ensembles *)
let rec parties e =
  if e = [] then [[]]
  else let x = prem e and e_1 = sp e
    in let part = parties e_1
      in part @ (ajout x part);;

let rec combinaisons p e =
  if p > list_length e then []
  else if p = 0 then [[]]
  else let x = prem e and e_1 = sp e in
      combinaisons p e_1 @ (ajout x (combinaisons (p - 1) e_1))
;;
let construire_tableau p e =
  vect_of_list (combinaisons p e)
;;
combinaisons 3 [1;2;3;4];;

(*Quelques fonctions de calcul*)

let rec facto n = match n with
    | 1 -> 1
    | x -> x * facto (x - 1)
;;
facto 5;;
let comb (i: int) (n: int) =
  (facto n) / ((facto i) * (facto (n - i)))
;;
comb 3 10;;

(*====================================================== Fonctions de création des coloriages  ========================================================*)


let lister n = let l = ref [] in
for i = 1 to n do l:=i::!l done;
rev !l;;
                  (* _ Créer la liste des parties de i élément sur les n totaux*)
let partiesDeTriangles (i:int) (n:int) = construire_tableau i (lister n);;

partiesDeTriangles 2 6;;

(*Fonctions de coloriage*)

(*Colorie les parties sélectionnées*)
let coloriageParties (i: int) (j: int) (n: int) = (*colorie la jeme partie calculée parmi les parties a i éléments de l'ensemble total a n éléments*)
  let parties = partiesDeTriangles i n in let partiesj = parties.(j) in let v = ref (make_vect n false) in
        let rec aux (ll: int list) =
          match ll with
            | [] -> ()
            | [x] -> !v.(x - 1) <- true
            | t :: q -> !v.(t - 1) <- true; aux q
        in aux partiesj; !v
;;

(*====================================================== Fonctions de coloriage automatique  ========================================================*)

let couleur (i: int) (v: bool vect) = v.(i);;
let nombre_associes (i: int) (v: bool vect) (l: int vect vect) = (*Determine le nombre de triangles coloriés en contact avec le triangle i*)
  let ll = l.(i) in let k = ref 0 in
      for j = 0 to 2 do
        if couleur (ll.(j) - 1) v then incr k
      done;
      !k
;;

let coloriageAuto (v: bool vect) (l: (int vect) vect) = let n = vect_length v in let vv = (make_vect n false) in
      for i = 0 to n - 1 do if ((nombre_associes i v l) >= 2 || couleur i v) then vv.(i) <- true done; vv
;;
let coloriageComplet (coloriage: bool vect) (triancey: int vect vect) = let n = vect_length triancey in let vtest = ref coloriage in
      while !vtest <> (coloriageAuto !vtest triancey) do
        vtest := coloriageAuto !vtest triancey done; !vtest;;
let coloriageComplet2 (coloriage: bool vect) (triancey: int vect vect) = let v = ref (make_vect 24 false) in
    for i = 0 to (vect_length triancey) do v := coloriageComplet coloriage triancey done; !v;;


(*====================================================== Fonctions de test des coloriages  ========================================================*)

(*Teste si le coloriage pris en argument permet de couvrir tout le triancey*)

let test_final (v: bool vect) = let ans = ref true and n = vect_length v in
    for i = 0 to n - 1 do if v.(i) = false then ans := false done; !ans;;

(*====================================================== Fonctions de conversions  ========================================================*)

let int_of_bool (b: bool) = if b then 1 else 0;;

let imprimerColoriage (coloriage: bool vect) =
  let n = vect_length coloriage in
    for i = 0 to n - 1 do print_int (int_of_bool coloriage.(i)) done;;

let valeurColoriage (coloriage: bool vect) = (*Determine le nombre de triangle coloriés dans un coloriage*)
  let n = vect_length coloriage and entier = ref 0 in
    for i = 0 to n - 1 do entier := !entier + (int_of_bool coloriage.(i)) done; !entier;;

(*ConstruireColoriage : convertir un code "binaire" en coloriage 1 = colorié, 0= non colorié*)
let construireColoriage (code: string) = let n = string_length code in let v = make_vect n false in
      for i = 0 to n - 1 do if (int_of_string (sub_string code i 1)) = 1 then v.(i) <- true done;
      v
;;


(*====================================================== Fonctions de recherche et vérification  ========================================================*)

let test = construireColoriage "001010010100000100001001";; (*Une solution au problème*)
coloriageComplet test triancey;;
coloriageComplet2 test triancey;;

(*======================================== Fonction de recherche par parties | Exhaustif, mais ne marche par pour toutes les valeurs (exn memoire)=======*)
exception stop of int;;
let trouveCombinaisonEtAffiche max = (*ne marche pas pour toutes le valeurs de max (exception memoire)*)
  try for i = 0 to 134595 do
      let c = coloriageParties max i 24 in if valeurColoriage (coloriageComplet c triancey) = 24 then raise (stop i) done;
  with
  | stop i -> print_string "Partie "; print_int i;
;;

trouveCombinaisonEtAffiche 6;;
comb 3 24;;
(*======================================== Fonction de recherche au Hasard| non exhaustif, mais ne fait pas d'exn memoire ==============================*)

(*Génère un coloriage de max triangle au hasard*)
#open "random";;
let coloriageAuPif (max: int) (n: int) = (*On créer un coloriage aléatoire que l'on teste*)
  let t = [|true; false|] in
    let v = make_vect n false in
      while valeurColoriage v <> max do
        for i = 0 to (n - 1) do if (valeurColoriage v < max) then v.(i) <- t.(int 2) done;
      done;
      (*De la, on procede au coloriage automatique*)
v
;;
init 0;;
coloriageAuPif 6 24;;
(*On teste m coloriage générés aléatoirement *)
exception stop of bool vect;;
let recherche max n m =
  try
    for i = 0 to m - 1 do
      let c = coloriageAuPif max n in let cc = coloriageComplet c triancey in
          if valeurColoriage cc = 24 then raise (stop c); done;
  with
  | stop c -> print_string "Le coloriage "; imprimerColoriage c; print_string " convient !";
        print_string "Rien trouvé"
;;

recherche 7 24 1000;;
let coloriageTest = coloriageAuPif 7 24;;
let solution = construireColoriage "001010010100000100001001";; (*Une solution au problème, en 7 coups*)
coloriageComplet solution triancey;;

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !