unofficial mirror of guile-user@gnu.org 
 help / color / mirror / Atom feed
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


  reply	other threads:[~2003-02-12 20:17 UTC|newest]

Thread overview: 32+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2003-02-08 11:00 Efficiency and flexibility of hash-tables Joris van der Hoeven
2003-02-08 13:57 ` Roland Orre
2003-02-08 14:14   ` Joris van der Hoeven
2003-02-08 14:55     ` Roland Orre
2003-02-08 15:14       ` Joris van der Hoeven
2003-02-08 15:31         ` Mikael Djurfeldt
2003-02-11 11:14           ` Joris van der Hoeven
2003-02-11 11:28             ` Joris van der Hoeven
2003-02-11 12:50               ` Mikael Djurfeldt
2003-02-08 15:44         ` Roland Orre
2003-02-10  9:55           ` Andreas Rottmann
2003-02-10 14:24             ` Greg Troxel
2003-02-10 15:00               ` Roland Orre
2003-02-10 16:52                 ` Mikael Djurfeldt
2003-02-10 17:09                   ` Roland Orre
2003-02-10 17:11                   ` Mikael Djurfeldt
2003-02-11 13:59                     ` Resizing hash tables in Guile Mikael Djurfeldt
2003-02-11 17:34                       ` Roland Orre
2003-02-12 11:41                         ` Marius Vollmer
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
2003-02-12 20:47       ` Efficiency and flexibility of hash-tables Paul Jarc
2003-02-12 21:58         ` Roland Orre

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