From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <jon@ffconsultancy.com>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled 
	version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39])
	by yquem.inria.fr (Postfix) with ESMTP id 5AB1DBC0A
	for <caml-list@yquem.inria.fr>; Thu,  7 Jun 2007 11:17:39 +0200 (CEST)
Received: from pih-relay06.plus.net (pih-relay06.plus.net [212.159.14.133])
	by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l579HcJS021745
	(version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO)
	for <caml-list@yquem.inria.fr>; Thu, 7 Jun 2007 11:17:39 +0200
Received: from [80.229.56.224] (helo=beast.local)
	 by pih-relay06.plus.net with esmtp (Exim) id 1HwE7e-0002o1-0R
	for caml-list@yquem.inria.fr; Thu, 07 Jun 2007 10:17:38 +0100
From: Jon Harrop <jon@ffconsultancy.com>
Organization: Flying Frog Consultancy Ltd.
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] filter on map
Date: Thu, 7 Jun 2007 10:11:18 +0100
User-Agent: KMail/1.9.7
References: <4667C188.1060408@univ-savoie.fr>
In-Reply-To: <4667C188.1060408@univ-savoie.fr>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <200706071011.18674.jon@ffconsultancy.com>
X-Miltered: at concorde with ID 4667CD32.002 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; christophe:01 raffalli:01 seq:01 ocaml:01 ocaml:01 frog:98 wrote:01 caml-list:01 tree:02 branches:06 fold:06 function:08 function:08 wondering:09 keys:11 

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