From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id B9214BC0A for ; Thu, 7 Jun 2007 15:16:20 +0200 (CEST) Received: from smtp.janestcapital.com (www.janestcapital.com [66.155.124.107]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l57DGJQ5006717 for ; Thu, 7 Jun 2007 15:16:20 +0200 Received: from [172.25.129.161] [38.96.172.125] by janestcapital.com with ESMTP (SMTPD-9.10) id A52F02C0; Thu, 07 Jun 2007 09:16:31 -0400 Message-ID: <46680522.3070501@janestcapital.com> Date: Thu, 07 Jun 2007 09:16:18 -0400 From: Brian Hurt User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Christophe Raffalli Cc: caml-list@inria.fr Subject: Re: [Caml-list] filter on map References: <4667C188.1060408@univ-savoie.fr> In-Reply-To: <4667C188.1060408@univ-savoie.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 46680523.002 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; christophe:01 raffalli:01 struct:01 cheers:01 citeseer:01 red-black:01 hen:98 psu:98 wrote:01 caml-list:01 binary:01 tree:02 module:03 module:03 let:03 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