Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
filter on map
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2007-06-07 (13:16)
From: Brian Hurt <bhurt@j...>
Subject: Re: [Caml-list] filter on map
Christophe Raffalli wrote:

> Dear list members
> I just write this piece of code because I wanted filter on map:
> module Map_Label = struct
>   module M =  Map.Make(Label)
>   include M
>   let filter f m =
>     M.fold (fun k v m ->
>       if f k then M.add k v m else m) m M.empty
> end
> But I am now wondering: this is O(n ln n), isn't there an O(n) 
> implementation (or just a faster
> implementation). This code insert the keys in increasing order which 
> is the worst case for balancing ? Just using a "random_fold" should 
> make things better ...
> What do you think ?
> Cheers,

Take a look at this paper:

It's about red-black trees but it's easy to generalize to all balanced 
binary trees.

Since you're generating the elements are already in order, you can build 
the resulting tree in O(N).

Does this help?