From: Peter Vandenabeele <peter@...>
Date: 2012-01-19T06:50:55+09:00
Subject: Re: uniq with count; better way?

--bcaec519618990a4fc04b6d470fb
Content-Type: text/plain; charset=UTF-8

On Wed, Jan 18, 2012 at 10:24 PM, Ryan Davis <ryand-ruby@zenspider.com>wrote:

>
> On Jan 18, 2012, at 12:26 , Ralph Shnelvar wrote:
>
> > I agree with you.  Obviously there is sorting going on.
>
> The nice thing about open source is you guys don't need to sit around and
> blindly speculate...
>
> % cd RUBY19
> /Users/ryan/Links/RUBY19
> % grep -i sort hash.c st.c
> %
>
> Not conclusive, I know.
>
> You're more than welcome to read the two files. They're less than 5k loc
> in sum.
>
>
I stand corrected ... (should have looked instead of speculated).

Do I understand correctly from `st_lookup` in `st.c` that:

* if (table->entries_packed) there is a linear search in bins
* else FIND_ENTRY uses a hashing mechanism to keep the cost of
  look-up essentially linear.

I had speculated that a b-tree with sorting was used to keep the
look-up cost low (but I presume now that is not the case)!

Thanks !

Peter

--bcaec519618990a4fc04b6d470fb--