On 1 Oct 2009, at 13:38, Krzysztof Sobolewski wrote:
Dnia czwartek 01 październik 2009 o 14:25:11 Manik Surtani
napisał(a):
> 2. The use of the entire range of ints on the number line. I can
> see
> the benefits here (removal of the mod and abs functions in my impl),
> but this greatly increases the range of numbers to scan. Granted a
> binary search is fast - O (log n) - but still such a massive number
> range is unnecessary given that, even at a push (for now anyway),
> we'd
> see 10,000 servers in a cluster? :-)
Well, doing it on the whole range instead on half of it would
increase lookup
time by O(1). Or, exactly by one iteration. At most.
But that's moot anyway, because the n in O(log n) is not the size of
search
space (it's 2 billion in your current impl.), it's the number of
items we care
about, that is number of nodes. At least that's how I understand it :)
D'oh, of course - I need more coffee. :-)
--
Manik Surtani
manik(a)jboss.org
Lead, Infinispan
Lead, JBoss Cache
http://www.infinispan.org
http://www.jbosscache.org