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 NAA25549; Thu, 8 Aug 2002 13:47:10 +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 NAA25663 for ; Thu, 8 Aug 2002 13:47:09 +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 g78Bl8n19117; Thu, 8 Aug 2002 13:47:08 +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 g78Bl8jR096330 ; Thu, 8 Aug 2002 13:47:08 +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 NAA28794 ; Thu, 8 Aug 2002 13:45:16 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with SMTP id NAA33346 ; Thu, 8 Aug 2002 13:44:16 +0200 Date: Thu, 8 Aug 2002 13:44:15 +0200 (DST) From: Diego Olivier Fernandez Pons To: Luc Maranget cc: caml-list@inria.fr Subject: Re: [Caml-list] Three way comparaisons In-Reply-To: <200208071522.RAA0000006153@beaune.inria.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, > J'ai lu vite mais dans les deux cas le nombre d'appels a` compare me > semble identique. Si les clefs sont compliqu=E9es (des cha=EEnes par ex) > c'est l=E0 l'essentiel. On peut omettre dans un premier temps la nature de la clef let rec member x =3D function | Empty -> false | Node (a, y, b) -> =09if x < y then member x a else if x > y then member x b else true Il y a tr=E8s approximativement 3/2 log n comparaisons par recherche contre log n + 1 pour la version d'Andersson Cela reste vrai si l'on m=E9morise auparavant le r=E9sultat de la comparaison de clefs pour se ramener =E0 une compairaison d'entiers > Comme d=E9j=E0 dit c'est pas facile de relier un match ou m=EAme un if = =E0 un > quelconque co=FBt final. =C7a va d=E9pendre de l'allignement de l'address= e > du code cible, de l'=E9tat des caches de la pr=E9diction des sauts, voire > de la phase de la lune... Tout le monde se plaint de l'absence de pr=E9visibilit=E9 des performances des processeurs actuels. Matteo Frigo dans sa th=E8se conclut que la seule solution reste en somme que le compilateur essaie diff=E9rentes possibilit=E9s et choisisse celle qui convient le mieux apr=E8s test.=20 Peut-=EAtre est-ce possible =E9galement en Caml (d'un autre c=F4t=E9 Caml e= st d=E9j=E0 tr=E8s rapide alors quelques gains de performance ne sont pas une priorit=E9 absolue il me semble).=20 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