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

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

On Thu, Jan 19, 2012 at 9:10 AM, Robert Klemme
<shortcutter@googlemail.com>wrote:

> On Wed, Jan 18, 2012 at 10:50 PM, Peter Vandenabeele
> <peter@vandenabeele.com> wrote:
> > 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.
> ...
> > 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)!
>
> Peter, a Hash uses _hashing_ to keep lookup cost low.  This has complexity
> O(1).
>
> http://en.wikipedia.org/wiki/Hash_table#Performance_analysis
>
>
Thank you, indeed.

Actually, by now I understand it would be _impossible_ to generically
use b-tree for the keys of a hash, since some objects can be used as
a key that have no < or > operator and thus not sortable ...

1.9.3-p0 :001 > a = Object.new  # => #<Object:0x9d88660>
1.9.3-p0 :002 > b = Object.new  # => #<Object:0x9d814c8>
1.9.3-p0 :003 > a < b
NoMethodError: undefined method `<' for #<Object:0x9d88660>
1.9.3-p0 :004 > h= {a => '10', b => '100'}
 => {#<Object:0x9d88660>=>"10", #<Object:0x9d814c8>=>"100"}
1.9.3-p0 :005 > h[a]
 => "10"

Learned a lot, sorry for the fuss ...

Peter

--00235446fcd41ef7aa04b6e22a5e--