Mark H Weaver m...@netris.org writes:
David Kastrup d...@gnu.org writes:
Scheme/Guile vectors are fixed size. [...] It is a bit of a nuisance
that one can grow a hashtable efficiently and on-demand, but not so an
array.
Although Scheme vectors should remain fixed-size for reasons I have
On 14 June 2012 22:47, David Kastrup d...@gnu.org wrote:
Mark H Weaver m...@netris.org writes:
David Kastrup d...@gnu.org writes:
Scheme/Guile vectors are fixed size. [...] It is a bit of a nuisance
that one can grow a hashtable efficiently and on-demand, but not so an
array.
Although
Daniel Hartwig mand...@gmail.com writes:
On 14 June 2012 22:47, David Kastrup d...@gnu.org wrote:
Mark H Weaver m...@netris.org writes:
David Kastrup d...@gnu.org writes:
Scheme/Guile vectors are fixed size. [...] It is a bit of a nuisance
that one can grow a hashtable efficiently and
On 14 June 2012 23:34, David Kastrup d...@gnu.org wrote:
Daniel Hartwig mand...@gmail.com writes:
The
guile core provides already a solid set of fundamental types which are
very easy to compose to produce *exactly* the type required for any
particular situation.
Except when they don't.
Daniel Hartwig mand...@gmail.com writes:
On 14 June 2012 23:34, David Kastrup d...@gnu.org wrote:
Huh? When resizing a hash table by doubling, you need to recoalesce
each bucket to two buckets, one of which is the original. Doubling
the size of the underlying vector is a reasonable start
On 15 June 2012 01:15, David Kastrup d...@gnu.org wrote:
Daniel Hartwig mand...@gmail.com writes:
What is this half-in-place algorithm that makes this efficient? If
the table is to remain balanced, all items should be rehashed and
reallocated to a new bucket and there is no correlation
Daniel Hartwig mand...@gmail.com writes:
On 15 June 2012 01:15, David Kastrup d...@gnu.org wrote:
Daniel Hartwig mand...@gmail.com writes:
What is this half-in-place algorithm that makes this efficient? If
the table is to remain balanced, all items should be rehashed and
reallocated to a
Message: 2
Date: Thu, 14 Jun 2012 10:33:36 -0400
From: Mark H Weaver m...@netris.org
Although Scheme vectors should remain fixed-size for reasons I have
given elsewhere in this thread, Guile also includes a more complex
'array' type that includes features such as arbitrary rank (i.e.
Daniel Llorens daniel.llor...@bluewin.ch writes:
I do not think this is a good idea. Guile arrays are just views of a
vector. Are you proposing to have a separate array implementation? The
resize operation clashes with the notion of shared views, and it only
makes sense for arrays of rank 1.
Mark H Weaver m...@netris.org writes:
Hi David,
David Kastrup d...@gnu.org writes:
I don't think I need yet another data structure deficient in some
respects. We have vectors that can't grow, hashtables that can grow but
only index through a hash function, vlists that can grow but have
Hi David,
David Kastrup d...@gnu.org writes:
Mark H Weaver m...@netris.org writes:
Simpler data structures can usually be implemented with less memory,
shorter code sequences with fewer conditional branches and less space in
the instruction cache, which in turn means they can be implemented
Mark H Weaver m...@netris.org writes:
Hi David,
David Kastrup d...@gnu.org writes:
Mark H Weaver m...@netris.org writes:
Simpler data structures can usually be implemented with less memory,
shorter code sequences with fewer conditional branches and less space in
the instruction cache,
David Kastrup d...@gnu.org writes:
Mark H Weaver m...@netris.org writes:
C++, like Scheme, already supports fixed-size vectors in the core
language, so it would be redundant to include them in a library.
A vector with run-time determined size? Which variant of C++ offers
that?
Um, this is
Mark H Weaver m...@netris.org writes:
David Kastrup d...@gnu.org writes:
Mark H Weaver m...@netris.org writes:
C++, like Scheme, already supports fixed-size vectors in the core
language, so it would be redundant to include them in a library.
A vector with run-time determined size? Which
Daniel Hartwig mand...@gmail.com writes:
On 11 June 2012 12:37, David Kastrup d...@gnu.org 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
() David Kastrup d...@gnu.org
() Sat, 09 Jun 2012 14:32:28 +0200
Suggestions?
Guile-SDL implements (in C) collections of enums using both a C array
(static, used also for init) and a Scheme hash table for backing store:
http://git.savannah.gnu.org/cgit/guile-sdl.git/tree/src/sdlenums.c#n66
On 11 June 2012 15:25, David Kastrup d...@gnu.org wrote:
Yes, but then it will actually be quite rare that the structure is
extended while it is read rather often. It would probably do fine to
just do the extension lazily by exception, but then wrapping a catch
around every access is likely
Hi David,
You raise an interesting issue. But first, a nitpick :)
On Sat 09 Jun 2012 14:32, David Kastrup d...@gnu.org writes:
Scheme hashtable
To be very pedantic, there are no hashtables in R5RS Scheme. SRFI-69
and R6RS specify them (in different ways), but do not mandate that they
grow.
On 11 June 2012 17:01, Daniel Hartwig mand...@gmail.com wrote:
For reference, attached is a growable vector I use in several
projects, adapted to support the length operation similar to Lua (i.e.
first unset numerical index). There is no catching of exceptions
here, every access to the data
Andy Wingo wi...@pobox.com writes:
You raise an interesting issue. But first, a nitpick :)
On Sat 09 Jun 2012 14:32, David Kastrup d...@gnu.org writes:
Scheme hashtable
To be very pedantic, there are no hashtables in R5RS Scheme. SRFI-69
and R6RS specify them (in different ways), but do
Hi,
On Mon 11 Jun 2012 11:55, David Kastrup d...@gnu.org writes:
Tables are a superset of what I need here. I need the growable vector
aspect, not the hash part aspect. Guile 1.8 only offers subsets:
growable does not come together with vector.
Why not just make your own growable vectors,
On 11 June 2012 18:38, David Kastrup d...@gnu.org wrote:
Well, considering the cost of dynvector-grow!, doing the growth in a
loop rather then just the determination of the new size seems a bit
expensive:
Only if you are repeatedly setting values at indices far beyond the
current capacity.
Andy Wingo wi...@pobox.com writes:
Hi,
On Mon 11 Jun 2012 11:55, David Kastrup d...@gnu.org writes:
Tables are a superset of what I need here. I need the growable vector
aspect, not the hash part aspect. Guile 1.8 only offers subsets:
growable does not come together with vector.
Why
Hi David,
David Kastrup d...@gnu.org skribis:
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
David Kastrup d...@gnu.org writes:
Andy Wingo wi...@pobox.com writes:
Hi,
On Mon 11 Jun 2012 11:55, David Kastrup d...@gnu.org writes:
Tables are a superset of what I need here. I need the growable vector
aspect, not the hash part aspect. Guile 1.8 only offers subsets:
growable does
Hello,
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.
Ah, too bad. This needs to run under 1.8 as well.
If you need to
On 11 June 2012 20:00, David Kastrup d...@gnu.org wrote:
I guess to summarize: if you want an abstraction like tables, you would
build it out of vectors and hash tables. But vectors and hash tables
themselves are the lower-level building blocks.
Not low-level enough: they are already
David Kastrup d...@gnu.org writes:
David Kastrup d...@gnu.org writes:
Andy Wingo wi...@pobox.com writes:
Hi,
On Mon 11 Jun 2012 11:55, David Kastrup d...@gnu.org writes:
Tables are a superset of what I need here. I need the growable vector
aspect, not the hash part aspect. Guile 1.8
Noah Lavine noah.b.lav...@gmail.com writes:
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.
Ah, too bad. This needs to run
Daniel Hartwig mand...@gmail.com writes:
On 11 June 2012 20:00, David Kastrup d...@gnu.org wrote:
I guess to summarize: if you want an abstraction like tables, you would
build it out of vectors and hash tables. But vectors and hash tables
themselves are the lower-level building blocks.
Not
On 11 June 2012 20:20, David Kastrup d...@gnu.org 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
Daniel Hartwig mand...@gmail.com writes:
On 11 June 2012 20:20, David Kastrup d...@gnu.org 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
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
On Mon 11 Jun 2012 16:19, David Kastrup d...@gnu.org writes:
Are you even reading what you are replying to?
Please be civil. People are trying to help you.
Thanks,
Andy
--
http://wingolog.org/
Andy Wingo wi...@pobox.com writes:
On Mon 11 Jun 2012 16:19, David Kastrup d...@gnu.org writes:
Are you even reading what you are replying to?
Please be civil. People are trying to help you.
More like telling me off. Of course, I am perfectly able to implement
my own moderately efficient
Hi David,
David Kastrup d...@gnu.org writes:
I don't think I need yet another data structure deficient in some
respects. We have vectors that can't grow, hashtables that can grow but
only index through a hash function, vlists that can grow but have
immutable content...
[...]
Why not just
On 9 June 2012 20:32, David Kastrup d...@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
Daniel Hartwig mand...@gmail.com writes:
On 9 June 2012 20:32, David Kastrup d...@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
On 11 June 2012 12:37, David Kastrup d...@gnu.org 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
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 Sat, Jun 9, 2012 at 2:32 PM, David Kastrup d...@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
Krister Svanlund krister.svanl...@gmail.com writes:
On Sat, Jun 9, 2012 at 2:32 PM, David Kastrup d...@gnu.org wrote:
One principal distinguishing feature, like with a Scheme
hashtable, is the ability to grow on-demand.
Scheme/Guile vectors are fixed size.
It is a
42 matches
Mail list logo
