From: Roland Orre <orre@nada.kth.se>
Cc: Greg Troxel <gdt@ir.bbn.com>
Subject: Re: Resizing hash tables in Guile
Date: 12 Feb 2003 21:17:46 +0100 [thread overview]
Message-ID: <1045081065.1033.451.camel@localhost> (raw)
In-Reply-To: <xy71y2d2xo7.fsf@nada.kth.se>
On Wed, 2003-02-12 at 18:53, Mikael Djurfeldt wrote:
> I've been thinking that maybe we should continue the move and let the
> resizing tables entirely replace the fixed size ones. It seems a
> little silly to have to explain to Guile users that there are two
> (sorry, eight) different kinds of hash tables... Also, I think the
> opacity of the resizing table objects is an advantage rather than a
> disadvantage. If they are opaque, we can any time modify the
> underlying implementation (the well-known data abstraction argument).
>
> What do you say?
I think that this is a a good idea, but I would like the optional size
argument to still be there as an initial guess about the number of
items to expect to avoid resizing and to optimize performance when
we have advance information about how many items to expect.
Of course this additional level of abstraction is nice as it also gives
a future option to use trees if the user e.g gives an optional
comparision operator.
By the way, Joris van der Hoeven mentioned that this type of resizing
hash tables are faster than trees, which have a time complexity
of O(log n)+reshuffling time if they are balanced. Do you have any
numbers showing how much faster and if possible if there are any
conditions? The reshuffling time will grow at least O(n) when the
size of our linear tables increases if I have understood right.
Best regards
Roland Orre
_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel
next prev parent reply other threads:[~2003-02-12 20:17 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <Pine.GSO.3.96.1030208160743.22945E-100000@anh>
[not found] ` <87lm0o7951.fsf@alice.rotty.yi.org>
[not found] ` <rmiu1fcnrhj.fsf@fnord.ir.bbn.com>
[not found] ` <1044889242.1033.310.camel@localhost>
[not found] ` <xy77kc8krhr.fsf@nada.kth.se>
[not found] ` <xy74r7ckqmy.fsf@nada.kth.se>
2003-02-11 13:59 ` Resizing hash tables in Guile Mikael Djurfeldt
2003-02-11 17:34 ` Roland Orre
[not found] ` <ljy94lhgkb.fsf@burns.dt.e-technik.uni-dortmund.de>
2003-02-12 17:47 ` Mikael Djurfeldt
2003-02-12 20:44 ` Rob Browning
2003-02-12 16:10 ` Marius Vollmer
2003-02-12 17:53 ` Mikael Djurfeldt
2003-02-12 20:17 ` Roland Orre [this message]
2003-02-13 9:35 ` Mikael Djurfeldt
2003-02-13 13:55 ` Harvey J. Stein
2003-02-13 14:24 ` Joris van der Hoeven
2003-02-13 18:30 ` Harvey J. Stein
2003-02-13 20:02 ` Paul Jarc
2003-02-13 9:52 ` Joris van der Hoeven
2003-02-12 20:55 ` Rob Browning
2003-02-13 10:43 ` Mikael Djurfeldt
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1045081065.1033.451.camel@localhost \
--to=orre@nada.kth.se \
--cc=gdt@ir.bbn.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).