guile-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Growable arrays?


From: Daniel Hartwig
Subject: Re: Growable arrays?
Date: Mon, 11 Jun 2012 12:23:09 +0800

On 9 June 2012 20:32, David Kastrup <address@hidden> 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.
>

Hello

>From <http://www.lua.org/doc/jucs05.pdf> it is clear that these
numerical indices of the Lua table are indeed implemented as an array.
 IIRC the implementation in guile (see branch ‘lua’) is implemented as
a straight hash table, without this array optimization.

Have you considered the vlist data type?  You would have to invert
your indices because it grows at the front, like cons grows a list.
It is also immutable for values already placed in the list, but
nothing prevents you from editing the objects referenced by those
values.

> Now it would be possible when the type lattice gets extended to store
> the new entries in a hashtable and go from there.

Why not use a hash for everything?  Unless your initial lattice is
very large there would be relatively small loss in performance.

If you were going to maintain both a vector and hash you are already
talking about wrapping the accessors, at which point you may as well
use vlist or implement growable vector yourself. It is comparable
effort to what you describe here, and the performance should be better
– especially for the part that gets stored in the hash.

>  Or put them into a
> list, and reallocate on first access beyond the existing element.  That
> seems rather contorted.

You mean “put them into a /vector/”?  Any way, this is not contorted
at all IMO but a dozen or so lines of code to implement the wrapped
vector functions.  Yes, it would be preferable if there was such a
type already implemented in guile.

If you access the list in mostly sequential order (ice-9 q) is quite
useful.  It provides O(1) insertion to the tail of the list.
Implemented using cons so anything other than in-order accessing is
expensive.

Regards



reply via email to

[Prev in Thread] Current Thread [Next in Thread]