[Top][All Lists]

[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 13:00:55 +0800

On 11 June 2012 12:37, David Kastrup <address@hidden> wrote:
> What is a vlist?

vlist is a data type introduced around guile 2.0.  You will find it
documented in the Guile Reference under Compound Data Types.

They are growable and provide vector-like access performances and
memory locality.

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

With these concerns your only options are really vlist or implementing
growable vector.

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

I see, that is rather contorted :-)

reply via email to

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