2008/4/4, Ilan Berci <coder68 / yahoo.com>:
> Eivind Eklund wrote:
>
>  >
>  > Apart from that, this is solvable in O(log N) per lookup using a
>  > binary tree.  If you need something faster, you could do it by
>  > constructing your tree in byte based buckets - essentially, you end up
>  > with one lookup per byte in your number, finding what range it is part
>  > of when the number is well enough resolved that it can only be in one
>  > range.

>  As a clarification, it's only LogN if you are using a sorted array with
>  binary lookup, the RangedHash implementation as above will not perform
>  LogN.. It will be N..
>
>  I also believe that this is not a case of premature optimization, If
>  someone says hash to me, I immediately expect it to behave as a LogN and

Did you want to say "behave as O(1)" - because that's what is usually
considered to be hash lookup performance?

>  I don't want to concern myself with number of entries within the
>  container.. Hashes are simply hashes, and if you want to make them
>  perform different than from what every coder knows them to be, then at
>  least have the courtesy to change the class name..

Absolutely.

Kind regards

robert

-- 
use.inject do |as, often| as.you_can - without end