Discussion :

[khazna]

Bonsoir à tous,

J'ai un tout petit problème de compilation d'une de mes fonctions en CamlLight, erreur du genre "This expression has type int but is used with type unit"...

Cette erreur est causée par ce bout de code:

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
 
exception break_loop;;
 
let partitionner_a3 a g d =
    let pivot = a.(d) and i = ref g and j = ref (d-1) in
        try
            begin
            while true do
                while a.(!i) < pivot do i := !i + 1; done;
                while pivot < a.(!j) do j := !j - 1; if !j = g then raise break_loop done;
                if !i >= !j then raise break_loop;
                echange a !i !j;
            done;
            end
        with break_loop -> ();
        echange a !i d;
        !i;;

Causée par la dernière ligne.

Je pense que cela vient d'un mauvais usage des exceptions (que je n'ai jamais utilisé, mais que j'aimerais beaucoup employer ici).

Toute aide est la bienvenue!

Merci à vous.

[Ptival]

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
 
exception break_loop;;
 
let partitionner_a3 a g d =
  let pivot = a.(d) and i = ref g and j = ref (d - 1) in
  try
    begin
      while true do while a.(!i) < pivot do i := !i + 1; done;
      while pivot < a.(!j)
      do
        j := !j - 1;
        if !j = g then raise break_loop done;
        if !i >= !j then raise break_loop;
        echange a !i !j;
      done;
    end
  with break_loop ->
    ();
    echange a !i d;
    !i;;

J'ai réindenté le code, en mettant en valeur la façon dont c'est lu par Caml.

Le problème est que les deux dernières instructions sont parsées comme la suite du gestionnaire d'exceptions, plutôt que comme deux instructions à part. Une solution au problème consiste à rajouter un begin...end comme ceci :

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
 
exception break_loop;;
 
let partitionner_a3 a g d =
  let pivot = a.(d) and i = ref g and j = ref (d - 1) in
  begin
    try
      begin
        while true do while a.(!i) < pivot do i := !i + 1; done;
        while pivot < a.(!j)
        do
          j := !j - 1;
          if !j = g then raise break_loop done;
          if !i >= !j then raise break_loop;
          echange a !i !j;
        done;
      end
    with break_loop -> ()
  end;
  echange a !i d;
  !i;;

Je m'abstiendrai de commentaires quand à la qualité/correction du code.

[khazna]

Merci beaucoup, c'était bien ça .

Est-ce que tu pourrais me révéler ce que tu penses de ce code? En quoi il est moche et tout pourri ^^ ?
Je suis un gros débutant en Caml, et ce code est une traduction - certainement malheureuse - d'un code en C.

[Ptival]

Non en fait j'avais pas cherché à comprendre, ma remarque voulait juste dire que je ne m'étais pas attardé sur ces détails, juste sur la résolution de ton problème.

Je viens de jeter un oeil un peu plus réfléchi. Ca semble raisonnable, j'ai un peu de mal à voir ce qu'il se passe dans les cas limites. J'imagine que g et d signifient gauche et droite, et que le tout sert à implémenter un quick-sort ou un tri assez semblable.

Je te laisse le loisir de tester pour te convaincre que le code est correct.

[khazna]

Oui, c'est bien la fonction de partitionnement pour un tri rapide.
Qui marchait très bien en C alors j'espère bien qu'elle fonctionne en Caml ! (C'est testé et ça a l'air de fonctionner même sur les cas limites).

Pour voir comment ça marche, un dessin convient: on cherche dans la partie gauche un élément superieur au pivot, un élément avec qui permuter dans la partie droite. Les tests évitent le croisement des deux indexs de parcours et le cas où tous les éléments sont supérieurs (ou inférieurs inmplicitement) au pivot.
Et on répète tant que les indexs ne se sont pas croisés.

Me reste plus qu'à faire l'amélioration de la médiane de trois et du non traitement des petits tableaux, et hop.