Re: Most used words in current buffer

[Udyant Wig]

On 07/23/2018 11:39 AM, Bob Proulx wrote:
> 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.

Would you choose differently if Emacs had a native code compiler besides
a byte code one?

>> 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.

Yes.

> 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.

It just occured to me that when I obtain a list of the elements of the
AVL tree solution, I get a sorted list, though in ascending order.
After this, I sort to get the list in descending order.  I could have
avoided this silly sorting and simply reversed the list.

> 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.

Which might entail more swings and roundabouts.

> Bob

Udyant Wig
-- 
We make our discoveries through our mistakes: we watch one another's
success: and where there is freedom to experiment there is hope to
improve.
                                -- Arthur Quiller-Couch