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:28:18 +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 1044962966 23583 80.91.224.249 (11 Feb 2003 11:29:26 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Tue, 11 Feb 2003 11:29:26 +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 18iYbM-00068F-00 for ; Tue, 11 Feb 2003 12:29:24 +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 18iYbj-0004fP-03 for guile-user@m.gmane.org; Tue, 11 Feb 2003 06:29:47 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10.13) id 18iYap-0004UB-00 for guile-user@gnu.org; Tue, 11 Feb 2003 06:28:51 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10.13) id 18iYaN-0004M7-00 for guile-user@gnu.org; Tue, 11 Feb 2003 06:28:25 -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 18iYaJ-0004Hm-00 for guile-user@gnu.org; Tue, 11 Feb 2003 06:28:19 -0500 Original-Received: from anh.math.u-psud.fr (anh.math.u-psud.fr [129.175.50.156]) h1BBSJB12946 ; Tue, 11 Feb 2003 12:28:19 +0100 (MET) Original-Received: from anh (anh [129.175.50.156]) by anh.math.u-psud.fr (Postfix) with SMTP id 44B71B2C8; Tue, 11 Feb 2003 12:28:18 +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:1627 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:1627 > 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. Here follows a slight improvement of the code for the case that you want to use boolean values for the entries of the hash table. Notice also that the hash value of the key is computed twice whenever you want to assign a value to a key; in a more low-level implementation, the second call can be avoided. Best wishes, Joris ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ;; MODULE : ahash-table.scm ;; 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-get-handle h key) (hash-get-handle (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-get-handle (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