[Top][All Lists]

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

Re: Growable arrays?

From: Stefan Israelsson Tampe
Subject: Re: Growable arrays?
Date: Mon, 11 Jun 2012 17:24:45 +0200

Maybe this could be a first stub for a table structure that is uses both an
array and a hash-table. I do think that implementing this might need fine tuning in order
to have good defaults and so on. So in that sense one probably need to check out reference
implementations. But this is for discussion!

I Assumed growing here and have no shrinking!

I made it nonfunctional.

One note to the discussion. It is not just to combine a growable vector with a growable hash
in ordder to have a one tool for all cases. The reason is that one need to tackle the issue with sparse tables with integer keys. I tried to add that feature as well in some way.

Anyway it shows that you don't need a ton of code to get something pretty functional.

On Mon, Jun 11, 2012 at 4:19 PM, David Kastrup <address@hidden> wrote:
Daniel Hartwig <address@hidden> writes:

> On 11 June 2012 20:20, David Kastrup <address@hidden> wrote:
>>> P.S.: I still need to look at vlists.  They might already address this
>>>       issue, though I can't use them in Guile 1.8.
>> No, the "immutable" angle would make them unsuitable again.
> Note that vlists are only immutable in the sense that you can not
> modify the value of a slot already allocated.

Which makes it useless here.

>> 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).
> From this I gather that your use case only appends to the lattice, if
> so, vlist is suitable for that task.

Wrong.  My use case only _allocates_ at the end of the existing type
lattice, but the records are not read-only.

>> Cough, cough.  Standard vectors are not growable.  Which is the
>> original problem of this thread, never mind Lua.
> True, but a growable vector is a tiny step away from the standard
> vector.

A tiny step if you are modifying the C code.  A not so tiny step if you
are working with Scheme.

>> hashtables have additional indirection
>> through hash buckets and coalescing lists
> This is fairly standard for a hash table.  I would be quite surprised
> if the hash table part of a Lua table did not also use buckets.

But it is not standard for a growable vector that it only comes with
buckets and chains.

>> Except that this one isn't.
> Why not?
> You take a vector and a hash table, store your values in them, and
> grow either as needed.  This is not a complicated type.

Except that vectors don't grow.  Are you even reading what you are
replying to?

David Kastrup

Attachment: hasharray.scm
Description: Binary data

reply via email to

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