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.1 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 7B1F3BC0A for ; Thu, 7 Jun 2007 10:27:56 +0200 (CEST) Received: from net.univ-savoie.fr (net.univ-savoie.fr [193.48.120.75]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l578RtAG005764 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=NO) for ; Thu, 7 Jun 2007 10:27:56 +0200 Received: from post.bourget.univ-savoie.fr (post.bourget.univ-savoie.fr [193.48.120.73]) by net.univ-savoie.fr (8.12.3/jtpda-5.4) with ESMTP id l578RmPN022441 for ; Thu, 7 Jun 2007 10:27:48 +0200 Received: from [193.48.123.45] (d45.lama.univ-savoie.fr [193.48.123.45]) by post.bourget.univ-savoie.fr (8.12.3/jtpda-5.4) with ESMTP id l578RnOF021467 ; Thu, 7 Jun 2007 10:27:49 +0200 Message-ID: <4667C188.1060408@univ-savoie.fr> Date: Thu, 07 Jun 2007 10:27:52 +0200 From: Christophe Raffalli User-Agent: Thunderbird 1.5.0.10 (X11/20070403) MIME-Version: 1.0 To: caml-list@inria.fr Subject: filter on map Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-Scanned-By: MIMEDefang 2.33 (www . roaringpenguin . com / mimedefang) X-Miltered: at concorde with ID 4667C18B.004 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; christophe:01 raffalli:01 christophe:01 raffalli:01 univ-savoie:01 struct:01 cheers:01 chablais:01 73376:01 univ-savoie:01 hen:98 lama:01 universite:02 cedex:02 module:03 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