fait chier caml - Page 1

bon ben voila je dois faire un tri fusion sur des tableaux en caml mais ca merde....
jai recommence plein de fois jai mis la prcedure de fusion dans une procedure a part et quand elle est appelle dans la procedure de tri elle ne fait pas la meme chose que si je lappelle toute seule !!!!!!!!!!!!!! comprends po...

voila les fonctions (bon cest moche mais bon et puis ya plein de print_tab que jai fait pour comprendre ce qui foire...) :

let fusion tab tab1 tab2 i j k = let pt1 = ref i and pt2 = ref j in
for l = i to k
do if !pt1 >= j then ( tab.(l) <- tab2.(!pt2) ; pt2 := !pt2 + 1 )
else ( if !pt2 > k then ( tab.(l) <- tab1.(!pt1) ; pt1 := !pt1 + 1 )
else ( if tab1.(!pt1) < tab2.(!pt2) then (tab.(l) <- tab1.(!pt1) ; pt1 := !pt1 + 1 )
else ( tab.(l) <- tab2.(!pt2) ; pt2 := !pt2 + 1 )
)
)
done ;
print_tab tab ;;

let rec tri_fusion tab i j = if i <> j then ( let k = (i+j)/2 + 1 in
let tab1 = tri_fusion tab i ( k - 1) and tab2 = tri_fusion tab k j in
print_tab tab1 ;
print_tab tab2 ;
print_tab tab ;
fusion tab tab1 tab2 i k j ;
print_tab tab ) ;
tab ;;

let print_tab tab = for i = 0 to vect_length tab - 1 do print_int tab.(i) done ; print_newline () ;;

et maintenant ce que me sort caml pour tri_fusion [|1;0;2|] 0 2 ;; avec trace "tri_fusion" et trace "fusion" :

#tri_fusion <-- [|1; 0; 2|]
tri_fusion --> <fun>
tri_fusion* <-- 0
tri_fusion* --> <fun>
tri_fusion** <-- 2
tri_fusion <-- [|1; 0; 2|]
tri_fusion --> <fun>
tri_fusion* <-- 0
tri_fusion* --> <fun>
tri_fusion** <-- 1
tri_fusion <-- [|1; 0; 2|]
tri_fusion --> <fun>
tri_fusion* <-- 0
tri_fusion* --> <fun>
tri_fusion** <-- 0
tri_fusion** --> [|1; 0; 2|]
tri_fusion <-- [|1; 0; 2|]
tri_fusion --> <fun>
tri_fusion* <-- 1
tri_fusion* --> <fun>
tri_fusion** <-- 1
tri_fusion** --> [|1; 0; 2|]
102
102
102
fusion <-- [|1; 0; 2|]
fusion --> <fun>
fusion* <-- [|1; 0; 2|]
fusion* --> <fun>
fusion** <-- [|1; 0; 2|]
fusion** --> <fun>
fusion*** <-- 0
fusion*** --> <fun>
fusion**** <-- 1
fusion**** --> <fun>
fusion***** <-- 1
002
fusion***** --> ()
002 -> il me renvoit [|0;0;2|] alors que si je fais cette fusion seule (voir en bas) ca marche...
tri_fusion** --> [|0; 0; 2|]
tri_fusion <-- [|0; 0; 2|]
tri_fusion --> <fun>
tri_fusion* <-- 2
tri_fusion* --> <fun>
tri_fusion** <-- 2
tri_fusion** --> [|0; 0; 2|]
002
002
002
fusion <-- [|0; 0; 2|]
fusion --> <fun>
fusion* <-- [|0; 0; 2|]
fusion* --> <fun>
fusion** <-- [|0; 0; 2|]
fusion** --> <fun>
fusion*** <-- 0
fusion*** --> <fun>
fusion**** <-- 2
fusion**** --> <fun>
fusion***** <-- 2
002
fusion***** --> ()
002
tri_fusion** --> [|0; 0; 2|]
- : int vect = [|0; 0; 2|]


et pour fusion [|1;0;2|] [|1;0;2|] [|1;0;2|] 0 1 1;; :

#fusion [|1;0;2|] [|1;0;2|] [|1;0;2|] 0 1 1;;

fusion <-- [|1; 0; 2|]
fusion --> <fun>
fusion* <-- [|1; 0; 2|]
fusion* --> <fun>
fusion** <-- [|1; 0; 2|]
fusion** --> <fun>
fusion*** <-- 0
fusion*** --> <fun>
fusion**** <-- 1
fusion**** --> <fun>
fusion***** <-- 1
012
fusion***** --> ()
- : unit = ()
[edit]Edité par jpflori le 26-03-2002 à 21:59:13[/edit]

Putain, les tableau en CAML, c'est une abération. Tien je suis généreux : voila un beau tri fusion tou plein mais sur les liste, c'est le seul truc bien en CAML. C'est pas trop optimisé, mais c'était l'an dernier :

(* La fusion de deux listes triées *)
let rec fusion l1 l2 = match (l1, l2) with
|[], [] -> []
|_, [] -> l1
|[], _ -> l2
|a1::q1, a2::q2 -> if a1 < a2 then
a1::fusion q1 l2
else
a2::fusion l1 q2;;

(* Extrait le debut de la liste : E(n/2) éléments *)
let debut l = let rec deb l n = match l with
|[] -> []
|a::q -> match n with
|1 -> [a]
|_ -> a::deb q (n-1) in
deb l ((list_length l)/2);;

(* Extrait la fin de la liste : n-E(n/2) éléments *)
let fin l = let rec queue l n = match l with
|[] -> []
|a::q -> match n with
|1 -> q
|_ -> queue q (n-1) in
queue l ((list_length l)/2);;

(* Le tri fusion : fonction principale *)
let rec trif l = match l with
|[] -> []
|a::[] -> [a]
|_ -> fusion (trif (debut l)) (trif (fin l));;

Lance avec "trif liste;;"

oui merci mais moi je veux comprendre pk mon mien il marche po euh

La programmation impérative en caml c'est pas beau.
Mieux vaut employer seulement de la programmation fonctionnelle et récursive.

merci de me faire avancer telcher

dsl mais j'ai rien trouvé

au fait ca veut dire quoi programmation fonctionnelle ?

ben plein de fonctions. caml est fait pour.

Par exemple au lieu d'écrire

let print_tab tab = for i = 0 to vect_length tab - 1 do print_int tab.(i) done ; print_newline () ;;

tu écris

let print_tab tab = do_vect print_int tab; print_newline();;

[edit]Edité par telchar le 26-03-2002 à 22:27:57[/edit]

Bon, c'est simple, en regardant bien le prog, on voit bien c qui cloche : le tableau tab n'est PAS modifié par l'appel à fusion. Cela car ce n'est pas une référence, donc pas de modif. Si tu passe une référence, le prog reçoit en fait l'adresse de la var, donc il peut la modifier. Mais ce n'est pas obligé. J'ai modifié ta fonction :

let fusion tab1 tab2 i j k =
	let pt1 = ref i and pt2 = ref j in 
	let tab = make_vect (k+1) (tab1.(0)) in
	for l = i to k do
		if !pt1 >= j then
			(tab.(l) <- tab2.(!pt2);
			pt2 := !pt2 + 1)
		else
			(if !pt2 > k then
				(tab.(l) <- tab1.(!pt1);
				pt1 := !pt1 + 1)
			else
				(if tab1.(!pt1) < tab2.(!pt2) then
					(tab.(l) <- tab1.(!pt1);
					pt1 := !pt1 + 1)
				else
					(tab.(l) <- tab2.(!pt2);
					pt2 := !pt2 + 1))) 
	done; 
tab;; 

let rec tri_fusion tab i j =
	if i < j then 
		(let k = (i+j)/2 + 1 in 
		let tab1 = tri_fusion tab i (k - 1) and tab2 = tri_fusion tab k j in 
		let t = fusion tab1 tab2 i k j in
		t)
	else
		tab;;

tu ne passe pas tab dans les arguments, mais tu le récupère en retour de fonction. Et voila, ça marche. Mais j'insite, c'est mieux le récursif en CAML !
[edit]Edité par guilc le 26-03-2002 à 22:43:44[/edit]

Et n'oublie pas d'indenter ton prog, c'est vachement plus lisible. Parceque là, il m'a fallu beaucoup de temps pour voir ce que tu faisais : c'est dur de voir sur quoi portent les boucles et les if !

ok et pour lidentation cest quand je poste ca enleve les espaces desole

utilise [pre] alors...

ouais cest bon jetais un peu presse cest tout et ppuis cetait po tres important paskon la refait aujourdhui en colle de caml

Aaahhhh CAML, le langage de merde des classes prépas !

vous faites ca en prepa!!
il peuvent pas vous apprendre des trucs plus utile a la vie de toue les jours:
C
C++
asm
par exemple et c'est tellement plus lisible(je trouve)

Le CAML est bcp plus intéressant

C'est vrai que c'est assez interessant sous certains aspects : le fait que ce soit un langage interprété que tu peux utiliser dans une interface du style maple ça a du bon : ça permet de se concentrer sur l'algorithmique seulement, sant s'occuper de tout le rseste, ce qui fait que les autres langages sont assez chiants à utiliser pour tester une chtite fonction !

Par contre, langage de merde : pas de typage, c'est typé par l'interpréteur, et efficacité total moisie : du style une algo de huffman environ 20 fois plus lent qu'en C (j'ai programmé le meme algo dans les 2 langages pour comparer).

C'est comme du basic, quoi

guilc> Le CAML n'est pas un langage interpreté.

au contraire, il y a un typage est très strict. En principe caml est aussi rapide que du C, sous linux

Ced > Et s'il est pas interprété, c'est quoi peut-être ! Et meme si tu le compile (fichier *.zi et *.zo) tu n'obtient que du bytecode. C'est guère mieux ! Voila comment caml interprète les programmes dans l'interface, dixit P. Weis, son concepteur :
- Lecture de la phrase 1
- Typage et compilation de la phrase 1
- Exécution du code de la phrase 1
- Impression du résultat
- On recommence avec la phrase 2 et ainsi de suite.
Je rappelle qu'une phrase en caml n'est pas une procédure, c'est ce qui y a entre deux ';'.

telchar > Quand je dis que c'est pas typé, c'est que je peux pas imposer moi meme le type des variables, c'est l'interpréteur qui le décide, c'est très différent du C par ex.

Et j'ai essayé des tests de vitesse entre CAML et C sous linux, alors là laisse beton, CAML est environ 10 fois plus lent que le C ! meme si il est vrai, c'est plus rapide que sous windows.
[edit]Edité par guilc le 28-03-2002 à 17:42:09[/edit]

c koi le CAML ??

Mais si tu peux imposer le type des variables...

let (x:float list) = [];;

Dis telchar, tu crois pas que c'est quand même un peu la merde ? Et puis tu peux regarder des kilos de sources CAML, cette manière de typer les variables (d'ailleur c plutot des fonctions) n'est jamais utilisée !

telchar > Le CAML est un langage de merde qu'on t'apprend en prepa parceque les profs ont pas envie d'installer des compilos pascal (he oui, et théorie, on a le choix du langage enseigné !). C'est un langage fonctionnel de type ML, le seul langage ML gratuit d'ailleur. En fait, on étudie ça en prepa en france parceque c'est développé à l'INRIA, on est pas chauvin !

Cette manière n'est jamais utilisée justement parce que Caml type très très bien à notre place.

et pis ya pas qu'en prépa

à l'INRIA aussi

et à l'ens (avec le C)