Re: avl-trees vs. hashes

[Jay Glascoe <jglascoe@jay.giss.nasa.gov>]

On 26 Oct 1998, Harvey J. Stein wrote:

> The delete-item! I emailed you takes a comparison fcn.  You could pass
> it (lambda (x y) (and (= (car x) (car y)) (eq? (cadr x) (cadr y)))).
> 

yes, I duplicate it here for others (and so I don't lose it again -- the
Guile mailing list is my personal post-it note ;)

   (define (delete-item! lst obj cmp?)
     (define (del-itm! lst tail obj cmp?)
       (cond ((null? tail))
             ((cmp? obj (car tail))
              (set-cdr! lst (cdr tail)))
             (else (del-itm! (cdr lst) (cdr tail) obj cmp?))))

     (cond ((null? lst) '())
           ((cmp? obj (car lst))
            (cdr lst))
           (else (del-itm! lst (cdr lst) obj cmp?)
                 lst)))

snippets of my C code look like this

    for (one_behind = bucket, entry_list = SCM_CDR(bucket);
	 entry_list != SCM_EOL;
	 one_behind = entry_list, entry_list = SCM_CDR(entry_list))
    {
...
	SCM_SETCAR(bucket, SCM_MAKINUM(bucket_size - 1));
	SCM_SETCDR(one_behind, SCM_CDR(entry_list));
	break;
    }

but then there's this thing (if the deleted entry is from the current
largest bucket):

	if (i == ilargest_bucket_index &&
	    bucket_size == ilargest_bucket_size)
	{
	    int new_largest_bucket_size =
		my_find_largest_bucket(vector, ilargest_bucket_size, &i);
...

unfortunately "my_find_largest_bucket" is an O(n) procedure.  The thing
is, I need to keep track of the largest bucket size and index (its
location in the hash table vector) so that my hash tables know when to
re-size.  Keeping track of the total number of entries (and using this for
re-size purposes) would be a BIG win for the deletion procedure, but a
small loss for insertion.  So, in your opinion, should I make the switch?

> -- 
> Harvey J. Stein
> BFM Financial Research
> hjstein@bfr.co.il
> 

	Jay
	jglascoe@jay.giss.nasa.gov