Discussion :

[mimiif]

Salut à tous,


J'ai eu un problème et grace à vos réponses, je me tourne vers vous
voila mon exercice:
ecrire une fonction qui fait le tri croisant d'un tableau d'entiers.


merci

[gorgonite]

penses à regarder la librairie standard
http://caml.inria.fr/pub/docs/manual...ref/Array.html

Code :

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

1
2
3
4
5
6
7
8
9
10
11
gorgonite@GorgonMobile:~$ ledit | ocaml
        Objective Caml version 3.10.0
 
# let a = [|5;2;3;4;1|];;
val a : int array = [|5; 2; 3; 4; 1|]
# Array.sort;;
- : ('a -> 'a -> int) -> 'a array -> unit = <fun>
# Array.sort (fun x y -> if x=y then 0 else if x<y then -1 else 1) a;;
- : unit = ()
# a;;
- : int array = [|1; 2; 3; 4; 5|]

[james-mi]

mimiif,


Gorgonite t'a donné une solution appréciable à 2 égards au moins :

• son extrême concision - vive le fonctionnel
• elle permet de trier les listes de tout type, pas seulement les entiers, comm on peut s'en rendre compte en tapant
  

  Code :

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

  # let f x = Array.sort (fun x y -> if x=y then 0 else if x<y then -1 else 1) x;;

  qui renvoie :
  

  Code :

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

  1
  2
   
  val f : 'a array -> unit = <fun>

[gasche]

En fait, ce n'est pas tous les types. C'est "tout les types que le runtime sait plus ou moins ordonner à la hache". Ça veut dire que parfois, ça n'est pas ce que tu veux (par exemple si tu utilises ça sur des structures de données où l'égalité n'est pas l'égalité structurelle, comme certains arbres équilibrés, troubles incoming), et qu'il arrive même que ça ne marche pas du tout (sur les fonctions ou les valeurs paresseuses par exemple).

Ça reste du détail, mais les opérateurs de comparaison polymorphes tiennent plus du hack que de la méthode sérieuse, et il faut éviter de reposer dessus si possible. C'est pratique dans certain cas, mais en général apporter sa propre fonction de comparaison avant le tri est une bien meilleure idée.

Par ailleurs, on peut écrire ça bien plus concisément, avec la fonction "compare" :

# let f t = Array.sort compare t;;
val f : 'a array -> unit = <fun>

[alex_pi]

Ça reste du détail, mais les opérateurs de comparaison polymorphes tiennent plus du hack que de la méthode sérieuse, et il faut éviter de reposer dessus si possible.

Euh... Je pense qu'il faut en comprendre les limites (quand il y a des fermetures ou des structures cycliques) et que ça ne va pas quand on veux mettre une sémantique sur l'ordre, mais dans plein de cas, c'est quand même génial !!

[gorgonite]

il est clair que compare ou ma version (qui est la même en compréhensible ) ont le défaut de nécessiter explicitement de manipuler la fonction comparaison pour les types trop complexes


et c'est là que F# et IComparable sont appréciables... très appréciables quand tu veux faire une intersection de deux noeuds d'un CFG pour remonter au dominateur immédiat par exemple

[InOCamlWeTrust]

Je pense que ce que veut son prof, si c'est bien ça, c'est LA fonction qui trie les éléments d'un vecteur... et non utiliser celle de la librairie.

[gorgonite]

Je pense que ce que veut son prof, si c'est bien ça, c'est LA fonction qui trie les éléments d'un vecteur... et non utiliser celle de la librairie.

ben il n'a pas préciser...

je donnais juste un exemple, je pense qu'il comprend désormais mieux comment structurer de manière générique et modulaire une telle fonction


s'il veut, j'ai tout sorte de tri sur liste ou tableau codé en caml... style bulle, mergesort, quicksort et heapsort

[InOCamlWeTrust]

s'il veut, j'ai tout sorte de tri sur liste ou tableau codé en caml... style bulle, mergesort, quicksort et heapsort

C'est bon, je sais d'où tu les sors ceux-là ! Moi aussi je les ai...

Tu avais aussi pris la correction, ou juste les ennoncés ?

P.S. : t'as oublié le FlashSort et le ShellSort (le seul qui vaille vraiment la peine pour de petits vecteurs) !

[gorgonite]

C'est bon, je sais d'où tu les sors ceux-là ! Moi aussi je les ai...

Tu avais aussi pris la correction, ou juste les ennoncés ?

P.S. : t'as oublié le FlashSort et le ShellSort (le seul qui vaille vraiment la peine pour de petits vecteurs) !

ceux-là étaient en camllight... les miens sont en OCaml, suite à la tentative de concours de perfs sur tes algo de tris pour des listes de Unsigned Long Long
mais très clairement, je m'en suis inspiré pour certains