[Caml-list] Three way comparaisons

[Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr>]

    Bonjour,

Dans une note d'Arno Andersson [signalée par Okasaki dans Oka98] est
présenté un algorithme de recherche dans un arbre en (log n + 1)
comparaisons :

au lieu de

let rec member x = function
  | Empty -> false
  | Node (a, y, b) ->
     match compare x y with
      | n when n < 0 -> member x a
      | n when n > 0 -> member x b
      | _ -> true

Arno propose un algorithme qui ne fait qu'une comparaison par noeud.
Il explique que "since most high-level languages do not supply three
way comparaisons the number of comparaisons used _de facto_ are
reduced by a factor of two"

Il ajoute en plus "However, so far the autor has never observed a
compiler which actually translate these two comparaisons into one
three-way comparaison"

- Qu'est exactement une comparaison à trois voies ? (est-ce une façon
d'exploiter que les processeurs en général lèvent des drapeaux de
signe ou de nullité pour leurs opérations ?)

- Le compilateur Caml effectue-t-il cette optimisation ?

- Le code proposé par Andersson sera-t-il vraiment plus efficace étant
donné que l'on est obligé de transmettre un paramètre de plus
(indépendamment du fait que l'arbre soit parcouru sur toute sa hauteur
dans la mesure où le truc peut toujours servir pour les insertions où
le parcours est toujours complet ?)

Code d'Andersson

(* y est le plus grand des minorants de x déjà rencontrés donc le
candidat idéal pour le test d'égalité *)

let rec member_some x y = function
  | Empty -> compare x y = 0
  | Node (a, z, b) ->
     compare x z with
       | n when n < 0 -> member_some x y a
       | _ -> member_some x z b

let rec member_none x = function
  | Empty -> false
  | Node (a, y, b) ->
      match compare x y with
        | n when n < 0 -> member_none x a
        | _ -> member_some x y b

let member x = function tree -> member_none x tree

        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners