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.5 required=5.0 tests=AWL,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 06726BD8A for ; Fri, 20 Jul 2007 09:55:24 +0200 (CEST) Received: from wr-out-0506.google.com (wr-out-0506.google.com [64.233.184.231]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6JGpMXa031477 for ; Thu, 19 Jul 2007 18:51:23 +0200 Received: by wr-out-0506.google.com with SMTP id i21so528621wra for ; Thu, 19 Jul 2007 09:51:22 -0700 (PDT) Received: by 10.142.76.4 with SMTP id y4mr219827wfa.1184863880949; Thu, 19 Jul 2007 09:51:20 -0700 (PDT) Received: by 10.142.72.4 with HTTP; Thu, 19 Jul 2007 09:51:20 -0700 (PDT) Message-ID: <28fa90930707190951y6e324750haf4067587fe1dcc7@mail.gmail.com> Date: Thu, 19 Jul 2007 09:51:20 -0700 From: "Luca de Alfaro" To: "Hugo Ferreira" Subject: Re: [Caml-list] Vec: a functional implementation of extensible arrays Cc: "Loup Vaillant" , caml-list@yquem.inria.fr In-Reply-To: <469F1E32.3040502@inescporto.pt> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_91344_15498134.1184863880917" References: <28fa90930707181032q7681340pc30fb47434aff5fc@mail.gmail.com> <6f9f8f4a0707190045g609abca4kfa3bb39d93604081@mail.gmail.com> <469F1E32.3040502@inescporto.pt> X-Miltered: at discorde with ID 469F968A.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; arrays:01 pointer:01 arrays:01 logarithmic:01 filliatre:01 backtracking:01 nodes:01 backtracking:01 lri:01 filliatr:01 publis:01 ocaml:01 iterating:01 bounded:01 worst-case:01 ------=_Part_91344_15498134.1184863880917 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Dear All, thanks for the pointer to the excellent paper. First, let me say that my Vec data structure was born to fill a need I had while working on a project= : while it has been useful to me, I certainly do not claim it is the best tha= t can be done, so I am very grateful for these suggestions! My Vec data structure is different from persistent arrays. It is likely to be less efficient for get/set use. However, it offers at logarithmic cost insertion/removal operations that ar= e not present in the standard persistent arrays. Consider a Vec a of size 10. - Vec.insert 3 d a inserts value d in position 3 of a, shifting elements 3..9 of a to positions 4..10. - Vec.remove 3 a removes the element in position 3 of a, shifting elements 4..9 to positions 3..8. Vec.pop is similar and returns the removed element as well. - Vec.concat works in log-time. These operations are necessary if you want to use a Vec as a FIFO, for example (you append elements at the end, and you get the first element via Vec.pop 0 a). In many algorithms, it is often handy to be able to remove/insert elements in the middle of a list. In summary, I don't think the Vec data structure is a replacement for array= s or persistent arrays in numerically-intensive work. But if you want a flexible data structure for the 90% of the code that is not peformance critical, they can be useful. Now the question is: can one get better get/set efficiency while retaining the ability to insert/remove elements? (I am sure that there is something better to be done...). Luca On 7/19/07, Hugo Ferreira wrote: > > Hello, > > For those of you interested in functional array consider Sylvain Conchon > and Jean-Christophe Filli=E2tre paper in [1]. The Union-Find (UF) uses > persistent arrays as its base data structure. I have made tests with the > UF using the code provided, an implementation of k-BUF data structure > (delayed backtracking) and altered version of the persistent array (fat > nodes + delayed backtracking). The tests I did show that this version of > persistent arrays is very efficient (especially for single threaded > backtracking). > > Maybe Luca could pit his implementation against that of the article and > report on how they fare? > > Regards, > Hugo Ferreira. > > [1] http://www.lri.fr/~filliatr/ftp/publis/puf-wml07.ps > > 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 > > > > _______________________________________________ > > 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 > > > > _______________________________________________ > 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_91344_15498134.1184863880917 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Dear All,

thanks for the pointer to the excellent paper.  Firs= t, let me say that my Vec data structure was born to fill a need I had whil= e working on a project: while it has been useful to me, I certainly do not = claim it is the best that can be done, so I am very grateful for these sugg= estions!=20

My Vec data structure is different from persistent arrays.  It= is likely to be less efficient for get/set use.
However, it offers at = logarithmic cost insertion/removal operations that are not present in the s= tandard persistent arrays. =20
Consider a Vec a of size 10.
  • Vec.insert 3 d a inserts value= d in position 3 of a, shifting elements 3..9 of a to positions 4..10.
    =
  • Vec.remove 3 a removes the element in position 3 of a, shifting el= ements 4..9 to positions 3..8. =20 Vec.pop is similar and returns the removed element as well.
  • Ve= c.concat works in log-time.
These operations are necessary if= you want to use a Vec as a FIFO, for example (you append elements at the e= nd, and you get the first element via=20 Vec.pop 0 a).  In many algorithms, it is often handy to be able to rem= ove/insert elements in the middle of a list.

In summary, I don'= t think the Vec data structure is a replacement for arrays or persistent ar= rays in numerically-intensive work.  But if you want a flexible data s= tructure for the 90% of the code that is not peformance critical, they can = be useful.=20
Now the question is: can one get better get/set efficiency while retain= ing the ability to insert/remove elements?  (I am sure that there is s= omething better to be done...).

Luca

On 7/19/07, Hugo Ferreira <hmf@inescporto.pt> wrote: Hello,

For those of you interested in functional array consider Sylv= ain Conchon
and Jean-Christophe Filli=E2tre paper in [1]. The Union-Find= (UF) uses
persistent arrays as its base data structure. I have made tes= ts with the
UF using the code provided, an implementation of k-BUF data structure(delayed backtracking) and altered version of the persistent array (fatnodes + delayed backtracking). The tests I did show that this version of
persistent arrays is very efficient (especially for single threaded
= backtracking).

Maybe Luca could pit his implementation against that = of the article and
report on how they fare?

Regards,
Hugo Ferr= eira.

[1] http://www.lri.fr/~filliatr/ftp/publis/puf-wml07.ps

Loup Vailla= nt wrote:
> 2007/7/18, Luca de Alfaro < luca@dealfaro.org>:
>> Dear All,
>>
>> I = would like to share with you an Ocaml implementation of extensible
>&= gt; arrays.
>>  The implementation is functional, based = on balanced trees (and on the
>> code
>> for Set and Map); I called the module Vec (fo= r vector - I like
>> short names).  You can find it at>> http://www.dea= lfaro.com/home/vec.html
>> Module Vec provides, in log-time:
>>
>>&= nbsp; Access and modification to arbitrary elements ( Vec.put n el v p= uts
>> element
>> el in position n of vector v, for insta= nce).
>> Concatenation
>> Insertion and removal of elements from a= rbitrary positions
>> (auto-enlarging
>> and auto-shrinki= ng 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 ca= n cause stack overflows.
>>
>> I have been using this dat= a structure for some months, and it has been
>> very
>> h= andy in a large number of occasions.  I hope it can be as useful = to you.
>>
>> I would appreciate all advice and feedback. &= nbsp;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 definiti= on, 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
>
> ___________________= ____________________________
> Caml-list mailing list. Subscription m= anagement:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Arc= hives: http://caml.inria.fr
> Be= ginner's list:=20 http://groups.yah= oo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
_______________________________________________
Caml-list mailing li= st. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/ca= ml-list
Archives: http://caml.inria.fr=
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: <= a href=3D"http://caml.inria.fr/bin/caml-bugs"> http://caml.inria.fr/bin/caml-bugs

------=_Part_91344_15498134.1184863880917--