Re: [Caml-list] filter on map

[Brian Hurt <bhurt@janestcapital.com>]

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:
http://citeseer.ist.psu.edu/236207.html

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?

Brian