[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Resizing hash tables in Guile
From: |
Harvey J. Stein |
Subject: |
Re: Resizing hash tables in Guile |
Date: |
13 Feb 2003 13:30:58 -0500 |
Joris van der Hoeven <address@hidden> writes:
> > > average. This means that, on average, operations are O(1).
> >
> > Inserts are, but lookups aren't necessarily.
>
> Both aren't necessarily, because inserting requires looking up too.
Yes, if you want to return an error for inserting 2 items with the
same key. No, if you allow multiple items with the same key.
> > And good hashing functions are still hard to write.
>
> I do not really agree. A good hash algorithm for lists (or strings),
> which I use in TeXmacs, is ...
I guess "hard" isn't quite the word for it. What I meant was that the
obvious ones don't work well. You basically need to look up a good
one to get good behavior. Tcl's fcn works pretty well too. I forget
what it does.
> > With this many items, log(N) is still just 32, so an O(log(N))
> > algorithm will still beat an O(1) algorithm if it's really
> > log_2(N) vs 32.
>
> Yes, but the O(1) is really *table lookup* multiplied by a small
> constant here, so this is *fast*. You may adjust the small constant
> by choosing an appropriate threshold for "size/nr buckets".
Not just table lookup. Also hash calculation from the key, which can
be more time consuming than a key comparison, and key comparisons for
everything in the bucket.
> > Trees also sort the data for you, which hash tables don't give you.
>
> But you need a compairison operation for that,
> which may be even less natural than a hash function.
Yes. For hash tables you just need a key equality test. For trees
you need to be able to order the keys.
> > So, ideally, one would have a hash table object with & without
> > resizing, and various sorts of tree (AVL, red/black, B*, etc) objects.
> > insert and delete and map would be methods that work on all of the
> > above, with map on trees returning the data in sorted order. For that
> > matter, insert & delete might as well also work on lists...
>
> Agreed: ideally, we have everything :^)
I think we're on the same page here...
STk had a nice scheme interface for hash tables. The code uses the
Tcl hash tables, they autoresize and if I recall correctly, many of
the important parameters can be modified. You might want to model the
guile stuff on this, or utilize this work. I advocated this when the
discussion came up years ago on the guile mailing list.
BTW, there was a long discussion of hash tables on the guile list some
number of years ago. At the time I didn't like liked the guile (aka
scm) hash tables. They were a very minimal implementation. The user
had to do too much to use them. I don't know what it's like these
days, but it'd certainly be nice to have a good implementation
available which includes autosizing.
--
Harvey Stein
Bloomberg LP
address@hidden
- Re: Efficiency and flexibility of hash-tables, (continued)
- Re: Resizing hash tables in Guile, Marius Vollmer, 2003/02/12
- Re: Resizing hash tables in Guile, Mikael Djurfeldt, 2003/02/12
- Re: Resizing hash tables in Guile, Roland Orre, 2003/02/12
- Re: Resizing hash tables in Guile, Mikael Djurfeldt, 2003/02/13
- Re: Resizing hash tables in Guile, Harvey J. Stein, 2003/02/13
- Re: Resizing hash tables in Guile, Joris van der Hoeven, 2003/02/13
- Re: Resizing hash tables in Guile,
Harvey J. Stein <=
- Re: Resizing hash tables in Guile, Paul Jarc, 2003/02/13
- Re: Resizing hash tables in Guile, Joris van der Hoeven, 2003/02/13
- Re: Resizing hash tables in Guile, Rob Browning, 2003/02/12
- Re: Efficiency and flexibility of hash-tables, Roland Orre, 2003/02/10
- Re: Efficiency and flexibility of hash-tables, Paul Jarc, 2003/02/12
- Re: Efficiency and flexibility of hash-tables, Roland Orre, 2003/02/12