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 mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 1CBF2BBCA for ; Wed, 2 Apr 2008 17:34:37 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AlACANJE80eACH+RiGdsb2JhbACRTwEBAQ8mmko X-IronPort-AV: E=Sophos;i="4.25,594,1199660400"; d="scan'208";a="10985050" Received: from server-nat-2.cs.umd.edu (HELO bacon.cs.umd.edu) ([128.8.127.145]) by mail3-smtp-sop.national.inria.fr with ESMTP; 02 Apr 2008 17:34:36 +0200 Received: from [192.168.0.2] (c-69-243-62-58.hsd1.md.comcast.net [69.243.62.58]) (authenticated bits=0) by bacon.cs.umd.edu (8.13.1/8.12.5) with ESMTP id m32FYQba001964 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Wed, 2 Apr 2008 11:34:31 -0400 Message-ID: <47F3A77F.80508@cs.umd.edu> Date: Wed, 02 Apr 2008 11:34:23 -0400 From: Mike Furr User-Agent: Mozilla-Thunderbird 2.0.0.9 (X11/20080103) MIME-Version: 1.0 To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] More efficient implementation of intersection of sets? References: <20080401155524.F1CE08B34A@xprdmxin.myway.com> In-Reply-To: <20080401155524.F1CE08B34A@xprdmxin.myway.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-CSD-MailScanner-Information: Please email staff@cs.umd.edu for more information X-CSD-MailScanner: Found to be clean X-CSD-MailScanner-SpamCheck: not spam, SpamAssassin (not cached, score=-4.399, required 5, autolearn=not spam, ALL_TRUSTED -1.80, BAYES_00 -2.60) X-CSD-MailScanner-From: furr@cs.umd.edu X-Spam: no; 0.00; intersection:01 runtime:01 intersection:01 ocaml:01 inria's:01 -mike:01 citeseer:01 psu:98 wrote:01 recursively:01 caml-list:01 algorithm:01 algorithm:01 linear:02 functional:02 sasha mal wrote: > Currently, > > Set.inter x y > > splits y into two trees, one containing elements that are bigger and > the other containing elements that are smaller than the top of x, > then applies the procedure recursively. What is the exact runtime of > the algorithm? Is there a better one for the intersection for OCaml > sets? The general algorithm is linear in the size of both sets in the worst case, however it can be quite a bit faster in many circumstances. See the paper "Implementing Sets Efficiently in a Functional Language" by Stephen Adams[1] for a more detailed discussion. I haven't looked at INRIA's exact implementation very closely, so they may do some extra tricks not discussed there, but it certainly appears to use this general technique. -Mike [1] - http://citeseer.ist.psu.edu/162336.html