From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Joris van der Hoeven Newsgroups: gmane.lisp.guile.user,gmane.lisp.guile.devel Subject: Re: Resizing hash tables in Guile Date: Thu, 13 Feb 2003 10:52:12 +0100 (MET) Sender: guile-user-bounces+guile-user=m.gmane.org@gnu.org Message-ID: References: <1045081065.1033.451.camel@localhost> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Trace: main.gmane.org 1045130160 4341 80.91.224.249 (13 Feb 2003 09:56:00 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Thu, 13 Feb 2003 09:56:00 +0000 (UTC) Cc: Greg Troxel Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 18jG2a-0000tO-00 for ; Thu, 13 Feb 2003 10:52:25 +0100 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18jG3j-0002eN-0C for guile-user@m.gmane.org; Thu, 13 Feb 2003 04:53:36 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10.13) id 18jG2r-0002Tm-00 for guile-user@gnu.org; Thu, 13 Feb 2003 04:52:41 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10.13) id 18jG2e-0002JL-00 for guile-user@gnu.org; Thu, 13 Feb 2003 04:52:30 -0500 Original-Received: from mathups.math.u-psud.fr ([129.175.52.4] helo=matups.math.u-psud.fr) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18jG2R-0002BX-00; Thu, 13 Feb 2003 04:52:15 -0500 Original-Received: from anh.math.u-psud.fr (anh.math.u-psud.fr [129.175.50.156]) h1D9qDZ03675 ; Thu, 13 Feb 2003 10:52:13 +0100 (MET) Original-Received: from anh (anh [129.175.50.156]) by anh.math.u-psud.fr (Postfix) with SMTP id 6BD2FB2C8; Thu, 13 Feb 2003 10:52:12 +0100 (MET) X-Sender: texmacs@anh Original-To: Roland Orre In-Reply-To: <1045081065.1033.451.camel@localhost> Original-cc: djurfeldt@nada.kth.se Original-cc: guile-user@gnu.org Original-cc: Joris van der Hoeven Original-cc: guile-devel@gnu.org Original-cc: Andreas Rottmann Original-cc: Marius Vollmer X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1b5 Precedence: list List-Id: General Guile related discussions List-Help: List-Post: List-Subscribe: , List-Archive: List-Unsubscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.user:1646 gmane.lisp.guile.devel:1927 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:1646 > > 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. In fact, it is even better to specify the resizing behaviour using optional arguments. For instance: up-ratio : size up when size/slots >= up-ratio up-factor : new nr slots := old nr slots * up-factor down-ratio : size up when size/slots < down-ratio down-factor: new nr slots := old nr slots / down-factor Using a small up-ratio will improve the constant factor in the lookup speed, but require the usage of a larger number of slots. > 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. Yes. > 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. Well: lookup time in a balanced search tree is O(log n), while lookup time in a table is O(1)... _______________________________________________ Guile-user mailing list Guile-user@gnu.org http://mail.gnu.org/mailman/listinfo/guile-user