It's because __lt__()
and related comparison methods are quite commonly used indirectly in list sorts and such. Sometimes the algorithm will choose to try another way or pick a default winner. Raising an exception would break out of the sort unless caught, whereas NotImplemented
doesn't get raised and can be used in further tests.
http://jcalderone.livejournal.com/32837.html
To summarise that link:
"NotImplemented
signals to the runtime that it should ask someone else to satisfy the operation. In the expression a == b
, if a.__eq__(b)
returns NotImplemented
, then Python tries b.__eq__(a)
. If b
knows enough to return True
or False
, then the expression can succeed. If it doesn't, then the runtime will fall back to the built-in behavior (which is based on identity for ==
and !=
)."
Let's test it:
import collections
import math
import timeit
def power_bit_length(x):
return 2**(x-1).bit_length()
def shift_bit_length(x):
return 1<<(x-1).bit_length()
def power_log(x):
return 2**(math.ceil(math.log(x, 2)))
def test(f):
collections.deque((f(i) for i in range(1, 1000001)), maxlen=0)
def timetest(f):
print('{}: {}'.format(timeit.timeit(lambda: test(f), number=10),
f.__name__))
timetest(power_bit_length)
timetest(shift_bit_length)
timetest(power_log)
The reason I'm using range(1, 1000001)
instead of just range(1000000)
is that the power_log
version will fail on 0
. The reason I'm using a small number of reps over a largeish range instead of lots of reps over a small range is because I expect that different versions will have different performance over different domains. (If you expect to be calling this with huge thousand-bit numbers, of course, you want a test that uses those.)
With Apple Python 2.7.2:
4.38817000389: power_bit_length
3.69475698471: shift_bit_length
7.91623902321: power_log
With Python.org Python 3.3.0:
6.566169916652143: power_bit_length
3.098236607853323: shift_bit_length
9.982460380066186: power_log
With pypy 1.9.0/2.7.2:
2.8580930233: power_bit_length
2.49524712563: shift_bit_length
3.4371240139: power_log
I believe this demonstrates that the 2**
is the slow part here; using bit_length
instead of log
does speed things up, but using 1<<
instead of 2**
is more important.
Also, I think it's clearer. The OP's version requires you to make a mental context-switch from logarithms to bits, and then back to exponents. Either stay in bits the whole time (shift_bit_length
), or stay in logs and exponents (power_log
).
Best Answer
As pointed out by other answers, in python they return floats probably because of historical reasons to prevent overflow problems. However, they return integers in python 3.
You can find more information in PEP 3141.