[Ocaml-lib-devel] Re: Array interface

[Alan P. <ap...@re...>]

In article <200...@ec...>, Eric C. Cooper wrote:
> On Fri, Jun 20, 2003 at 05:29:26PM -0500, Brian Hurt wrote:
>> On Fri, 20 Jun 2003, Eric C. Cooper wrote:
>> > I'm probably missing some essential context, but what is wrong with
>> > the simple approach of using a mutable 'a array that gets replaced
>> > with a bigger one when you try to set an element beyond its current
>> > length?
>> 
>> Because then you are allocating a new array- and copying all the elements 
>> of the old array- every time you add a new element to the end of the 
>> array.  So if you add n elements to an empty array, you end up allocating 
>> n arrays, and copying n*(n-1)/2 elements.  At which point you might as 
>> well be using lists and @.
> 
> If you double the array each time you need to grow it, you will
> create only O(log n) arrays, and copy only O(n log n) elements.  Do
> any of the other approaches have better worst-case performance?

What is under discussion is what to put in the "empty" slots of the
newly doubled array, ocaml having no "null" or "undef" value to stuff
in them.