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: -- (:)
From: Jon Harrop <jon@f...>
Subject: Re: [Caml-list] filter on map
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