Re: Growable arrays?

[Krister Svanlund <krister.svanlund@gmail.com>]

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

On Sat, Jun 9, 2012 at 2:32 PM, David Kastrup <dak@gnu.org> wrote:

>
> Hi,
>
> the main data structure of Lua is a "table", an associative array, and a
> table t has a continguous numerically addressed part from 1..#t, with
> all other indices going through a hashing mechanism.  One principal
> distinguishing feature, like with a Scheme hashtable, is the ability to
> grow on-demand.
>
> Scheme/Guile vectors are fixed size.  Now I have a situation where I
> have a basic type lattice with records stored in vectors, and this type
> lattice may be extended dynamically (which typically happens at the
> start of a whole file, for potentially multi-file runs).  Scheme does
> not offer a suitable data structure for that.  It is a bit of a nuisance
> that one can grow a hashtable efficiently and on-demand, but not so an
> array.
>
> Now it would be possible when the type lattice gets extended to store
> the new entries in a hashtable and go from there.  Or put them into a
> list, and reallocate on first access beyond the existing element.  That
> seems rather contorted.  And since there is, if I remember, a project to
> run Lua on top of Guile, having a fundamental and reasonably efficient
> data structure corresponding to a Lua table, or at least the contiguous
> part of a Lua table, would seem like a reasonably useful idea.  After
> all, there already _is_ such a mechanism underlying hash tables so it
> seems somewhat peculiar not to have it available for vectors as well.
>
> Suggestions?
>
> --
> David Kastrup
>
>
>
I don't know how much you know about data structures, and I must confess
I'm not very educated on Guile or Luas implementations. Based on what you
are writing I would assume that the scheme hashtables aren't growable in
the same way as a vector has to be growable. The number of elements in a
hashtable isn't limited by it's "size". They are often implemented as each
position (where the hashtables size is the number of positions) being a
linked list giving the hashtable (in theory) limitless actual size. Growing
a vector/array involves having to allocate new continuous memory and
copying all the elements there, so for example in C++ (i think) the
std:vector is increased by half it's current size each time meaning that
the more expensive the copying gets the more elements you can insert into
the vector before it has to resize.

I would assume it wouldn't be that difficult to implement a pretty
efficient growable vector for scheme.

// Krister Svanlund

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