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 Subject: Re: Efficiency and flexibility of hash-tables Date: Tue, 11 Feb 2003 12:14:33 +0100 (MET) Sender: guile-user-bounces+guile-user=m.gmane.org@gnu.org Message-ID: References: NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Trace: main.gmane.org 1044962081 19359 80.91.224.249 (11 Feb 2003 11:14:41 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Tue, 11 Feb 2003 11:14:41 +0000 (UTC) Cc: Roland Orre 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 18iYN3-00051y-00 for ; Tue, 11 Feb 2003 12:14:38 +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 18iYO3-0005tA-03 for guile-user@m.gmane.org; Tue, 11 Feb 2003 06:15:39 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10.13) id 18iYNC-0005gA-00 for guile-user@gnu.org; Tue, 11 Feb 2003 06:14:46 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10.13) id 18iYN6-0005N1-00 for guile-user@gnu.org; Tue, 11 Feb 2003 06:14:42 -0500 Original-Received: from matups.math.u-psud.fr ([129.175.50.4]) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18iYN1-00053F-00 for guile-user@gnu.org; Tue, 11 Feb 2003 06:14:35 -0500 Original-Received: from anh.math.u-psud.fr (anh.math.u-psud.fr [129.175.50.156]) h1BBEYB12802 ; Tue, 11 Feb 2003 12:14:34 +0100 (MET) Original-Received: from anh (anh [129.175.50.156]) by anh.math.u-psud.fr (Postfix) with SMTP id 21234B2C8; Tue, 11 Feb 2003 12:14:34 +0100 (MET) X-Sender: texmacs@anh Original-To: Mikael Djurfeldt In-Reply-To: Original-cc: guile-user@gnu.org Original-cc: contact@texmacs.org 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:1626 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:1626 > > So does there exist an adaptive-number-of-slots solution in guile? > > No. We'd be happy to include adaptation in the standard Guile > hash-tables, though. Would it be possible for you to contribute a > patch? I don't have much knowledge about how to write low-level guile functions. In the meantime, you might want to use the following code. I only use the equal?-based access methods, but it would be easy to add the eq?- and eqv?-based methods. The 'adaptive hash tables' are stored as a pair with a usual hashtable and its number of entries. I have tested the code a bit and it seems to work. If you find any bugs, then please let me know. Best wishes, Joris ----------------------------------------------------------- Joris van der Hoeven http://www.texmacs.org: GNU TeXmacs scientific text editor http://www.math.u-psud.fr/~vdhoeven: personal homepage ----------------------------------------------------------- ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ;; MODULE : ahash-table.scm (part of GNU TeXmacs) ;; DESCRIPTION : adaptive hash tables ;; COPYRIGHT : (C) 2003 Joris van der Hoeven ;; ;; This software falls under the GNU general public license and comes WITHOUT ;; ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for details. ;; If you don't have this file, write to the Free Software Foundation, Inc., ;; 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Adaptive hash tables ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (define (make-ahash-table) (cons (make-hash-table 1) 0)) (define (ahash-ref h key) (hash-ref (car h) key)) (define (ahash-size h) (cdr h)) (define (ahash-slots! h new-size) (let ((new-h (make-hash-table new-size))) (hash-fold (lambda (key value dummy) (hash-set! new-h key value)) #f (car h)) (set-car! h new-h))) (define (ahash-set! h key value) (if (hash-ref (car h) key) (hash-set! (car h) key value) (begin (if (>= (cdr h) (vector-length (car h))) (ahash-slots! h (+ (* 2 (vector-length (car h))) 1))) (set-cdr! h (+ (cdr h) 1)) (hash-set! (car h) key value)))) (define (ahash-remove! h key) (let ((removed (hash-remove! (car h) key))) (if removed (begin (set-cdr! h (- (cdr h) 1)) (if (< (+ (* 4 (cdr h)) 1) (vector-length (car h))) (ahash-slots! h (quotient (vector-length (car h)) 2))))) removed)) (define (ahash-fold h) (hash-fold (car h))) _______________________________________________ Guile-user mailing list Guile-user@gnu.org http://mail.gnu.org/mailman/listinfo/guile-user