From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Roland Orre Newsgroups: gmane.lisp.guile.user Subject: Re: Efficiency and flexibility of hash-tables Date: 08 Feb 2003 15:55:48 +0100 Organization: Royal Institute of Technology Sender: guile-user-bounces+guile-user=m.gmane.org@gnu.org Message-ID: <1044716148.1033.177.camel@localhost> References: NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Trace: main.gmane.org 1044716114 16106 80.91.224.249 (8 Feb 2003 14:55:14 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Sat, 8 Feb 2003 14:55:14 +0000 (UTC) Cc: guile-user@gnu.org 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 18hWNt-0004Bd-00 for ; Sat, 08 Feb 2003 15:55:13 +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 18hWOv-00037B-07 for guile-user@m.gmane.org; Sat, 08 Feb 2003 09:56:17 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10.13) id 18hWOZ-00036q-00 for guile-user@gnu.org; Sat, 08 Feb 2003 09:55:55 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10.13) id 18hWOX-00036e-00 for guile-user@gnu.org; Sat, 08 Feb 2003 09:55:54 -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 18hWOW-00036X-00 for guile-user@gnu.org; Sat, 08 Feb 2003 09:55:52 -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 h18EtnwV026467 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NO); Sat, 8 Feb 2003 15:55:49 +0100 (MET) Original-To: Joris van der Hoeven In-Reply-To: X-Mailer: Ximian Evolution 1.2.1 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:1607 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:1607 On Sat, 2003-02-08 at 15:14, Joris van der Hoeven wrote: > Hi, > > Thanks for your reply. Unfortunately, I think that > you did not fully understand my question. Yes, I misunderstood it. > My question was: is the number of slots automatically adapted > as a function of the number or entries, or is it not? > If you cannot have a good estimate for the number of entries, > then this auto-adaptation may be important. > In fact, I think that a good low level implementation of > general purpose hash tables should have this feature. I agree. I once developed (in Ada) for a debugging system, a hash table where the hash entries were balanced trees instead of lists. This could maybe be a good approach to reach good performance as balanced trees are quite good from this point of view. (like the new Reiser file system in Linux is using) Your idea, about adaptive hash table length, could easily be made into guile but from my opinion not as a general solution, as there will be a lot of reshuffling of every item each time the vector length changes. I guess somewhere out there, a balanced tree solution may exist for guile, otherwise I could try to find my old ada-source and give it a try. The disadvantage with the balanced tree solution though is that it's not enough with a hash function (and equal?), it also needs a comparision (<) function. Best regards Roland _______________________________________________ Guile-user mailing list Guile-user@gnu.org http://mail.gnu.org/mailman/listinfo/guile-user