Re: [Caml-list] Vec: a functional implementation of extensible arrays

["Luca de Alfaro" <luca@dealfaro.org>]

[-- Attachment #1: Type: text/plain, Size: 3105 bytes --]

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
>

[-- Attachment #2: Type: text/html, Size: 4125 bytes --]