Re: Most used words in current buffer

[Bob Proulx <bob@proulx.com>]

tomas@tuxteam.de wrote:
> Stefan Monnier wrote:
> > I'd use a hash-table (implemented in C) rather than an avl-tree
> > (implemented in Elisp).

With exactly those choices above I would agree completely.

> Plus, a (well-implemented) hash table will always be faster (for inserts
> and random lookups) than a balanced (AVL, red-black) binary tree. The
> latter affords you sorted lookup (find first greater than, output in order).
>
> You pay for that :-)

Again the hash table is good until you need to grow the table.  Then
there is a pause while memory is shuffled around.  But that never
happens with a balanced tree because that cost is always amortized
along as you go.

Also if you need to extract the entries in sorted order then the
balanced tree is already sorted.  Whereas with the hash table an extra
sort step is needed.

One of looking at this is that it is global optimization versus local
optimization.

In some ways it is swings and roundabouts.  But in other ways it
depends upon what you need.

Bob