filter on map

filter on map

[Christophe Raffalli]

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,
-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI

Re: [Caml-list] filter on map

[Jon Harrop]

On Thursday 07 June 2007 09:27:52 Christophe Raffalli wrote:
> 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 ...

If you can cull branches of search tree whilst filtering then you can make 
this <O(n) by pulling your function inside "Map". Even if you can't, I think 
you can still make it O(n) instead of O(n log n) by adding a Map.of_seq 
function that builds a map from an association list in O(n).

I would recommend putting the Set.union function into Map and writing this in 
terms of that.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

Re: [Caml-list] filter on map

[Brian Hurt]

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