Re: [Caml-list] Three way comparaisons

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

    Bonjour,

> J'ai lu vite mais dans les deux cas le nombre d'appels a` compare me
> semble identique. Si les clefs sont compliquées (des chaînes par ex)
> c'est là l'essentiel.

On peut omettre dans un premier temps la nature de la clef

let rec member x = function
  | Empty -> false
  | Node (a, y, b) ->
	if x < y then member x a
        else if x > y then member x b
        else true

Il y a très approximativement 3/2 log n comparaisons par recherche
contre log n + 1 pour la version d'Andersson

Cela reste vrai si l'on mémorise auparavant le résultat de la
comparaison de clefs pour se ramener à une compairaison d'entiers

> Comme déjà dit c'est pas facile de relier un match ou même un if à un
> quelconque coût final. Ça va dépendre de l'allignement de l'addresse
> du code cible, de l'état des caches de la prédiction des sauts, voire
> de la phase de la lune...

Tout le monde se plaint de l'absence de prévisibilité des performances
des processeurs actuels. Matteo Frigo dans sa thèse conclut que la
seule solution reste en somme que le compilateur essaie différentes
possibilités et choisisse celle qui convient le mieux après test. 
Peut-être est-ce possible également en Caml (d'un autre côté Caml est
déjà très rapide alors quelques gains de performance ne sont pas une
priorité absolue il me semble). 

        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