English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Re: Caml-list] Sets and home-made ordered types
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2009-09-17 (09:08)
From: CUOQ Pascal <Pascal.CUOQ@c...>
Subject: Re: Sets and home-made ordered types
> So what, one pointer more for each association 
> in the Map? That would be rather acceptable (but still not ideal, sorry 
> I'm very demanding).

You were already paying the price of "one pointer more"
many times over and were not even thinking about it. One
more will not make any difference.

You have to realize that each node already carries a height,
two pointers to subtrees, and take into account the one-word
overhead for the block header. We're not doubling the size of
each tree node here, we're increasing it from 5 to 6 words.

PS: You make up for the overhead by having dynamic structures
that are just the right size, and by taking advantage of sharing,
of course.