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 D44C3BC69 for ; Fri, 20 Jul 2007 18:45:11 +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 l6KGjAr0028985 for ; Fri, 20 Jul 2007 18:45:11 +0200 Received: from [172.25.129.161] [38.96.172.125] by janestcapital.com with ESMTP (SMTPD-9.10) id A6A503B4; Fri, 20 Jul 2007 12:45:25 -0400 Message-ID: <46A0E690.2060805@janestcapital.com> Date: Fri, 20 Jul 2007 12:45:04 -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: Luca de Alfaro Cc: Jon Harrop , caml-list@yquem.inria.fr Subject: Re: [Caml-list] Vec: a functional implementation of extensible arrays References: <28fa90930707181032q7681340pc30fb47434aff5fc@mail.gmail.com> <28fa90930707190959g66cb2e6wc7a446af2a6dfb72@mail.gmail.com> <6f9f8f4a0707200035l4351c6b6g585b4edd2c51faa6@mail.gmail.com> <200707200914.18557.jon@ffconsultancy.com> <28fa90930707200842q742d5f77y29885d0c7ebcc74c@mail.gmail.com> In-Reply-To: <28fa90930707200842q742d5f77y29885d0c7ebcc74c@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 46A0E696.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; arrays:01 node:01 sub-array:01 subranges:01 citeseer:01 red-black:01 psu:98 iterators:01 wrote:01 wrote:01 extensible:01 caml-list:01 append:02 functional:02 slightly:03 Luca de Alfaro wrote: > > > This is almost easy. I would need to add a bit to each node to keep > track of whether it's balanced... > The penalty would be that the balancing function would need to do > slightly more work to find out what has to be balanced. > So perhaps it's not a good idea for append, insert, but it could make > sense for concat (?), and especially for filter and sub... > But I am hesitant. If one does concat, or one does sub to extract a > sub-array, I wrote the code already so that sharing is maximized. What > is the percentage of cases in which you get a Vec, but then don't do > any get/set on it, and only iterate? > Especially since you already have iterators on subranges? Do you > think it's worth it? Anyone has advice? I don't think that with laziness you can avoid enough work to make inserts O(1). On the other hand, sub and filter can be done in O(M + log N) easily enough, see: http://citeseer.ist.psu.edu/236207.html The paper is about red-black trees, but it's applicable to all rotation-balanced trees. Brian