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]

Re: avl-trees vs. hashes


Jay Glascoe <jglascoe@jay.giss.nasa.gov> writes:

 > On 20 Oct 1998, Harvey J. Stein wrote:
 >
 > that was sort of an off-the-cuff remark.  I agree, in theory shrinking a
 > hash table should take no longer than growing one.  But in the timing
 > tests I'm using, garbage collection is much slower than, uh, garbage
 > creation. 
 > 
 > > I'm still not sure exactly what you mean about shrinking & growing
 > > being different, but I'm sure it'll become clear when I see the code.

I meant different in the code, not different in run time.  Consider a
rebuild-hash-table fcn which takes a hashtable & an array, populates
the array with the items in the hashtable & then replaces the array in
the hashtable with the new array.  Such a fcn could be used for
growing the hashtable as well as shrinking it.  There should be no
difference in the code.

This was just in relation to your comment:

 > I'm working on deletion and downsizing for my hashtables right now.
 > Deletion seems to be REAL SLOW, because I basically have to rebuild a
 > bucket (basically an alist) every time I remove an entry.  I could use
 > "dummy entries" or something, but that seems like such an ugly solution.

I thought that downsizing would just be a matter of adding a call to
rebuild-hash-table at the appropriate time.  In retrospect I guess you
meant you were adding the bookkeepping necessary for deciding when to
call rebuild-hash-table with a smaller array.

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