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