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=HTML_MESSAGE 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 A6B68BE29 for ; Fri, 20 Jul 2007 10:15:43 +0200 (CEST) Received: from el-out-1112.google.com (el-out-1112.google.com [209.85.162.178]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6JGxI6g000488 for ; Thu, 19 Jul 2007 18:59:19 +0200 Received: by el-out-1112.google.com with SMTP id o28so24976ele for ; Thu, 19 Jul 2007 09:59:16 -0700 (PDT) Received: by 10.142.157.15 with SMTP id f15mr213976wfe.1184864354817; Thu, 19 Jul 2007 09:59:14 -0700 (PDT) Received: by 10.142.72.4 with HTTP; Thu, 19 Jul 2007 09:59:14 -0700 (PDT) Message-ID: <28fa90930707190959g66cb2e6wc7a446af2a6dfb72@mail.gmail.com> Date: Thu, 19 Jul 2007 09:59:14 -0700 From: "Luca de Alfaro" To: "Loup Vaillant" Subject: Re: [Caml-list] Vec: a functional implementation of extensible arrays Cc: caml-list@yquem.inria.fr In-Reply-To: <6f9f8f4a0707190045g609abca4kfa3bb39d93604081@mail.gmail.com> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_91464_8084132.1184864354783" References: <28fa90930707181032q7681340pc30fb47434aff5fc@mail.gmail.com> <6f9f8f4a0707190045g609abca4kfa3bb39d93604081@mail.gmail.com> X-Miltered: at discorde with ID 469F9866.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; arrays:01 ocaml:01 arrays:01 iterating:01 bounded:01 worst-case:01 amortized:01 logarithmic:01 iterator:01 subrange:01 beginner's:01 ocaml:01 bug:01 iterating:01 bounded:01 ------=_Part_91464_8084132.1184864354783 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline On 7/19/07, Loup Vaillant wrote: > > 2007/7/18, Luca de Alfaro : > > Dear All, > > > > I would like to share with you an Ocaml implementation of extensible > arrays. > > The implementation is functional, based on balanced trees (and on the > code > > for Set and Map); I called the module Vec (for vector - I like > > short names). You can find it at > > http://www.dealfaro.com/home/vec.html > > Module Vec provides, in log-time: > > > > Access and modification to arbitrary elements ( Vec.put n el v puts > element > > el in position n of vector v, for instance). > > Concatenation > > Insertion and removal of elements from arbitrary positions > (auto-enlarging > > and auto-shrinking the vector). > > as well as: > > > > All kind of iterators and some visitor functions. > > Efficient translation to/from lists and arrays. > > An advantage of Vec over List, for very large data structures, is that > > iterating over a Vec of size n requires always stack depth bounded by > log n: > > with lists, non-tail-recursive functions can cause stack overflows. > > > > I have been using this data structure for some months, and it has been > very > > handy in a large number of occasions. I hope it can be as useful to > you. > > > > I would appreciate all advice and feedback. Also, is there a repository > > where I should upload it? Do you think it is worth it? > > > > All the best, > > > > Luca > > Very interesting. I always felt uneasy about the presence of > imperative arrays without a functional counterpart. I can't wait to > try it. > > Looking at your array type definition, I assume that the timings you > specified are worst-case? Is it possible to achieve better (but > amortized) bounds? Do you think it would be worth the trouble? > > I didn't see in your specs the complexity of your iterators. Does > these work in linear time, like those of the List and Array module? > > Regards, > Loup 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 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. 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. Luca _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > ------=_Part_91464_8084132.1184864354783 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline On 7/19/07, Loup Vaillant <loup.vaillant@gmail.com> wrote:
2007/7/18, Luca de Alfaro <luca@dealfaro.org>:
> Dear All,
>
> I would like to share with you an Ocaml implementation of extensible arrays.
>  The implementation is functional, based on balanced trees (and on the code
> for Set and Map); I called the module Vec (for vector - I like
> short names).  You can find it at
> http://www.dealfaro.com/home/vec.html
> Module Vec provides, in log-time:
>
>  Access and modification to arbitrary elements ( Vec.put n el v puts element
> el in position n of vector v, for instance).
> Concatenation
> Insertion and removal of elements from arbitrary positions (auto-enlarging
> and auto-shrinking the vector).
> as well as:
>
> All kind of iterators and some visitor functions.
> Efficient translation to/from lists and arrays.
> An advantage of Vec over List, for very large data structures, is that
> iterating over a Vec of size n requires always stack depth bounded by log n:
> with lists, non-tail-recursive functions can cause stack overflows.
>
> I have been using this data structure for some months, and it has been very
> handy in a large number of occasions.  I hope it can be as useful to you.
>
> I would appreciate all advice and feedback.  Also, is there a repository
> where I should upload it?  Do you think it is worth it?
>
> All the best,
>
> Luca

Very interesting. I always felt uneasy about the presence of
imperative arrays without a functional counterpart. I can't wait to
try it.

Looking at your array type definition, I assume that the timings you
specified are worst-case? Is it possible to achieve better (but
amortized) bounds? Do you think it would be worth the trouble?

I didn't see in your specs the complexity of your iterators. Does
these work in linear time, like those of the List and Array module?

Regards,
Loup

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 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.

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.

 Luca

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

------=_Part_91464_8084132.1184864354783--