From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Roland Orre Newsgroups: gmane.lisp.guile.devel,gmane.lisp.guile.user Subject: Re: Resizing hash tables in Guile Date: 12 Feb 2003 21:17:46 +0100 Organization: Royal Institute of Technology Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Message-ID: <1045081065.1033.451.camel@localhost> References: <1044889242.1033.310.camel@localhost> <87fzqtjx96.fsf@zagadka.ping.de> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Trace: main.gmane.org 1045081606 9069 80.91.224.249 (12 Feb 2003 20:26:46 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Wed, 12 Feb 2003 20:26:46 +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 18j3Jx-0001lG-00 for ; Wed, 12 Feb 2003 21:17:29 +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 18j3LW-00027s-02 for guile-devel@m.gmane.org; Wed, 12 Feb 2003 15:19:06 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10.13) id 18j3LB-0001eq-00 for guile-devel@gnu.org; Wed, 12 Feb 2003 15:18:45 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10.13) id 18j3Ks-00015i-00 for guile-devel@gnu.org; Wed, 12 Feb 2003 15:18:28 -0500 Original-Received: from smtp0.nada.kth.se ([130.237.222.202] helo=smtp.nada.kth.se) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18j3Kk-0000lc-00; Wed, 12 Feb 2003 15:18:18 -0500 X-Authentication-Info: Sender authentication was Original-Received: from c600 (h122n2fls33o875.telia.com [217.208.54.122]) (authenticated bits=0) by smtp.nada.kth.se (8.12.1/8.12.1) with ESMTP id h1CKHiwV006259 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NO); Wed, 12 Feb 2003 21:17:44 +0100 (MET) Original-To: djurfeldt@nada.kth.se In-Reply-To: X-Mailer: Ximian Evolution 1.2.1 Original-cc: guile-user@gnu.org Original-cc: Joris van der Hoeven Original-cc: Marius Vollmer Original-cc: guile-devel@gnu.org Original-cc: Andreas Rottmann X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1b5 Precedence: list List-Id: Developers list for Guile, the GNU extensibility library List-Help: List-Post: List-Subscribe: , List-Archive: List-Unsubscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.devel:1921 gmane.lisp.guile.user:1640 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.devel:1921 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