Browse thread
[Caml-list] Suggestion about balanced trees in stdlib
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2002-05-11 (17:18) |
From: | Stefano Zacchiroli <zack@c...> |
Subject: | Re: [Caml-list] Suggestion about balanced trees in stdlib |
On Sat, May 11, 2002 at 05:47:04PM +0200, Gerd Stolpmann wrote: > type 'a map = Empty | Node of 'a map * key * 'a * 'a map * int > > type set = Empty | Node of set * elt * set * int > > The difference is that every map node has 6 words, and every set node > consists of 5 words. My suggestion is to prefer the map representation, > and define set = unit map, wasting one word per node, and making sets > 20% larger. Ok, I agree that this is the "clean" way to the goal. Anyway I think that memory consumption is crucial for the standard library, this is why I'm proposing a dirty trick for the set/map matter. Usually I dislike tricks and prefer clean programming, but IMHO a standard library is somewhat a particular case. <WARNING_dirty_trick> Why not use a single source file that implement both set and map using some campl4 tricks like pa_ifdef module? You may have two different definitions of tree and a pool of accessor functions working on a tree and returning single components (hoping that the compiler inline this kind of functions). In the set case you doesn't need to use the value component of a tree so you can avoid to compile the relative accessor function (poor gain) and you can also compile a tree tuple without a value component. </WARNING_dirty_trick> [ Question: gurus, do you thinks this is a feasible solution or I'm missing something? ] I know, this is a really dirty trick. Also I don't know if is applicable because I have never looked at the implementations set.ml and map.ml but just as an idea it can work. Pros: - reduce memory consumption for Set - no code duplication Cons: - objects (.cm{a,o,x...}) duplication - really dirty! - last time I looked at it camlp4 pa_ifdef module doesn't permit multiple declaration using only one "if" construct so you incurs in situations like: ifdef FOO then let bar = ... ifdef FOO then let quux = ... ifdef FOO then let baz = ... Just a [dirty] idea. Cheers. -- Stefano Zacchiroli - undergraduate student of CS @ Univ. Bologna, Italy zack@cs.unibo.it | ICQ# 33538863 | http://www.cs.unibo.it/~zacchiro "I know you believe you understood what you think I said, but I am not sure you realize that what you heard is not what I meant!" -- G.Romney ------------------- 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