Re: Implementing vector (resizable array) with n-ary tree

On Apr 25, 3:01 pm, "SucMucPaProlij" <b...@xxxxxxx> wrote:

<spookyoldt...@xxxxxxxxx> wrote in message
[...]
My problem with standard vector is that it does not satisfy #3. My
application cannot predict in advance how many elements will be
needed. So it will be repeatedly resizing the vector. What if there
are only a few elements left, the vector is using half of the
available memory, and then suddenly it runs out of space internally
and therefore doubles its size!? That's a lot of memory wasted on
account of a few additional elements.

you can make the vector increase in smaller steps

That's a possibility. I could use smaller steps, while making sure
that (amortized) resize still takes constant time. The downside is
that, although constant, it may be a significantly larger constant
time.

and you can make it shrink.

Unfortuantely, in my application, there is no good time to shrink it
without a strong chance it will need to grow again.

There's an additional problem which your suggestion does not address.
(I didn't mention this problem in my original post, but it's
important). When we do the expensive resize, we must temporarily have
two arrays allocated while we copy elements from the old array to the
new one. When the original array is more than half of the available
memory, the new one cannot also fit. I expect this would cause some
unnecessary paging.

wrong. it takes 4 constant-time lookups to reach an element only if all vectors
(at all levels) have the same size.

All vectors at all levels of the tree do have the same size (except
for the ones that have not yet been initialized, of course). It would
be 4 constant-time lookups.

do you plan to add new elements only at the end of your structure or at any
arbitrary position?

Only at the end of the structure.

I don't understand what you want to improve with your implementation. Why can't
you just use vector?

1. As I mentioned in my original post, I would like not to waste an
amount of memory that is, presumably, a linear function of the size of
the vector.

2. I would like to avoid ever having two (potentially very large)
arrays allocated at the same time, such as when the resize operation
copies elements from the old array to the new one.

3. All other things being equal, I would like not only to keep the
resize operation constant time, but to make that constant time as low
as reasonably possible.

.

Relevant Pages

  • Re: Is it possible to delete an element from a sorted array with O(1) time?
    ... Is it possible to delete an element from a sorted array with Otime? ... integers in constant time" as asking whether there are sequences that can ... "it is possible to add requirements such that deletion of an arbitrary ... more natural) interpretation. ...
    (comp.programming)
  • Re: Is it possible to delete an element from a sorted array with O(1) time?
    ... Is it possible to delete an element from a sorted array with Otime? ... And the answer is then not unqualified "no" but "it is possible to add requirements such that deletion of an arbitrary element is not possible in constant time". ... As I see it the technical issues are clearcut, and the earlier fallacious reasoning very clearly exposed. ...
    (comp.programming)
  • Re: Is it possible to delete an element from a sorted array with O(1) time?
    ... Is it possible to delete an element from a sorted array with O ... you might want to look up cursor gap structures somewhere. ... to implement a data structure with constant time random access by index ...
    (comp.programming)
  • Re: Is it possible to delete an element from a sorted array with O(1) time?
    ... Is it possible to delete an element from a sorted array with O ... to implement a data structure with constant time random access by index ... that screws up constant time random access by index since the ...
    (comp.programming)
  • Re: Minimal keywords needed for constructing a full CL system
    ... my immediate reaction on reading this was that memory access can't be ... laws of physics and you'd also need constant time bignum operations). ... you've got a finite amount of memory and hence a finite array-total-size-limit ... simply by doing a linear search and pessimizing the lookup of all items to be ...
    (comp.lang.lisp)