From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id QAA08576; Wed, 7 Aug 2002 16:44:28 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA08310 for ; Wed, 7 Aug 2002 16:44:27 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g77EiQ529017 for ; Wed, 7 Aug 2002 16:44:26 +0200 (MET DST) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.5/jtpda-5.4) with ESMTP id g77EiQjR031039 for ; Wed, 7 Aug 2002 16:44:26 +0200 (CEST) Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id QAA17786 for ; Wed, 7 Aug 2002 16:42:34 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with SMTP id QAA18304 for ; Wed, 7 Aug 2002 16:41:35 +0200 Date: Wed, 7 Aug 2002 16:41:35 +0200 (DST) From: Diego Olivier Fernandez Pons To: caml-list@inria.fr Subject: [Caml-list] Three way comparaisons In-Reply-To: <20020807073600.GA31615@strontium.pps.jussieu.fr> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE X-Antivirus: scanned by sophie at shiva.jussieu.fr Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, Dans une note d'Arno Andersson [signal=E9e par Okasaki dans Oka98] est pr=E9sent=E9 un algorithme de recherche dans un arbre en (log n + 1) comparaisons : au lieu de let rec member x =3D 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 =E0 trois voies ? (est-ce une fa=E7on d'exploiter que les processeurs en g=E9n=E9ral l=E8vent des drapeaux de signe ou de nullit=E9 pour leurs op=E9rations ?) - Le compilateur Caml effectue-t-il cette optimisation ? - Le code propos=E9 par Andersson sera-t-il vraiment plus efficace =E9tant donn=E9 que l'on est oblig=E9 de transmettre un param=E8tre de plus (ind=E9pendamment du fait que l'arbre soit parcouru sur toute sa hauteur dans la mesure o=F9 le truc peut toujours servir pour les insertions o=F9 le parcours est toujours complet ?) Code d'Andersson (* y est le plus grand des minorants de x d=E9j=E0 rencontr=E9s donc le candidat id=E9al pour le test d'=E9galit=E9 *) let rec member_some x y =3D function | Empty -> compare x y =3D 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 =3D 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 =3D 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