This is the mail archive of the guile@cygnus.com mailing list for the guile project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
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