guile-devel
[Top][All Lists]
Advanced

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

Re: Growable arrays?


From: David Kastrup
Subject: Re: Growable arrays?
Date: Mon, 11 Jun 2012 06:37:43 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.1.50 (gnu/linux)

Daniel Hartwig <address@hidden> writes:

> 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.

What is a vlist?

>> 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.

About double the memory impact (vector->1 cell, hash table->1 cell per
hash bucket+1 additional cons cell per element) and much slower copying.
And quite slower access.

>>  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/”?

No, since a vector can't be grown.  This would basically switch the data
structure between "write" and "read" mode, where "write mode" grows the
list of additions, and "read mode" accesses the vector.  Switching from
write to read entails creating a newly allocated vector and copying the
new additions from the list as well as the old vector into it.

> 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.

I don't access the list in mostly sequential order.  I described the use
case in the posting you replied to.  It is quite random access in
character.

-- 
David Kastrup




reply via email to

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