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=1.0 required=5.0 tests=AWL,SPF_NEUTRAL 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 3A0F3BC69 for ; Fri, 20 Jul 2007 09:35:41 +0200 (CEST) Received: from an-out-0708.google.com (an-out-0708.google.com [209.85.132.250]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6K7ZesE026014 for ; Fri, 20 Jul 2007 09:35:40 +0200 Received: by an-out-0708.google.com with SMTP id b15so209605ana for ; Fri, 20 Jul 2007 00:35:40 -0700 (PDT) DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=hlD7QybHG2NMKmlGu+tv2YzOimgM02qyjIfcS5Q3jp8pvk7S8pa2y6My31I8F6SzbmV9WQD2j8pS7MkBh6wAFOJedWnN2fD9LAzThvEpWzybFZBOiNfqJZjDm9HWrYdTe+u43MLyi5kxk+cB8QV2Im/M4c0RUzNVNGex0jcX1kQ= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=U/nb+w0FDw70KSqG794EhGSJ5DlanA3Fadf5l7t7Kx1SftJqRl6KUWsowsRz1jT/nTCZAasD5TqexaG4PBiX0ZdqrqKwfgsn9W0UWsrR3vpTwCnHpTbllFE9yMBexhrJ7U8G0I7eQsXxbe3O2j86JNwFZZrzsQPqyk23drmgcl4= Received: by 10.100.124.5 with SMTP id w5mr100527anc.1184916939968; Fri, 20 Jul 2007 00:35:39 -0700 (PDT) Received: by 10.100.33.15 with HTTP; Fri, 20 Jul 2007 00:35:39 -0700 (PDT) Message-ID: <6f9f8f4a0707200035l4351c6b6g585b4edd2c51faa6@mail.gmail.com> Date: Fri, 20 Jul 2007 09:35:39 +0200 From: "Loup Vaillant" To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Vec: a functional implementation of extensible arrays In-Reply-To: <28fa90930707190959g66cb2e6wc7a446af2a6dfb72@mail.gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <28fa90930707181032q7681340pc30fb47434aff5fc@mail.gmail.com> <6f9f8f4a0707190045g609abca4kfa3bb39d93604081@mail.gmail.com> <28fa90930707190959g66cb2e6wc7a446af2a6dfb72@mail.gmail.com> X-j-chkmail-Score: MSGID : 46A065CC.000 on discorde : j-chkmail score : X : 0/20 1 0.000 -> 1 X-Miltered: at discorde with ID 46A065CC.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; arrays:01 logarithmic:01 inserting:01 okasaki's:01 iterator:01 subrange:01 iterators:01 syntactic:01 extensible:01 caml-list:01 imperative:01 lazy:02 lazy:02 data:02 bounds:02 2007/7/19, Luca de Alfaro : > > For get/set, the worst case and the average case are both logarithmic: it's > a balanced tree (if you are lucky, you can find your answer at the root! I did. :) > ;-). I am open to new ideas. In part, I wanted a simple data structure > (easier to extend, among other things). Also, I use Set, Map, etc, quite > often, and those are also balanced trees: I thought that if I can live with > those, I can probably live with Vec as well. So can I. Your current implementation is already very attractive, and looks very usable. For the new idea, have you thought of making (or specifying) syntactic sugar to use your array? About improving performance, here is my guess : there is no way to lower the bounds on get and set. However, the average cost of insert may already be O(1), provided you use your array the same way you would use an imperative version of it (more accurately, not inserting an element to an old version of your array). The same may be true for remove. Therefore, if I guess right, to take advantage of persistence AND have insert perform in O(1) average, you would have to use (and pay for) lazy evaluation. How, I don't know (yet). (Note that I have stolen this idea from Okasaki's book) > For an iterator, the worst case is as follows, where n is the size of the > Vec: > > if you iterate on the whole Vec, then O(n) > if you iterate over m elements (you can iterate on a subrange), then O(m + > log n). > That's why I have iterators: you can also iterate via a for loop, using get > to access the elements, but then the time becomes O(n log n) for the first > case, and O(m log n) for the second case. That is why I wondered if lazy evaluation was worth the trouble at all : most of the time, we iterate rather than insert or remove elements. I only regret the absence of filter. Is there a way to obtain a efficient filter? (Well, if my guess above is right, a naive implementation of filter would already be quite efficient...) Regards, Loup