Считайте следующий код (отсюда с количеством тестов увеличенным):
from timeit import Timer
def find_invpow(x,n):
"""Finds the integer component of the n'th root of x,
an integer such that y ** n <= x < (y + 1) ** n.
"""
high = 1
while high ** n < x:
high *= 2
low = high/2
while low < high:
mid = (low + high) // 2
if low < mid and mid**n < x:
low = mid
elif high > mid and mid**n > x:
high = mid
else:
return mid
return mid + 1
def find_invpowAlt(x,n):
"""Finds the integer component of the n'th root of x,
an integer such that y ** n <= x < (y + 1) ** n.
"""
low = 10 ** (len(str(x)) / n)
high = low * 10
while low < high:
mid = (low + high) // 2
if low < mid and mid**n < x:
low = mid
elif high > mid and mid**n > x:
high = mid
else:
return mid
return mid + 1
x = 237734537465873465
n = 5
tests = 1000000
print "Norm", Timer('find_invpow(x,n)', 'from __main__ import find_invpow, x,n').timeit(number=tests)
print "Alt", Timer('find_invpowAlt(x,n)', 'from __main__ import find_invpowAlt, x,n').timeit(number=tests)
Использование Python 2.6 (Python 2.6.5 (r265:79063, Apr 16 2010, 13:57:41) [GCC 4.4.3] on linux2
), времена, о которых сообщают:
Norm 9.73663210869
Alt 9.53973197937
Однако на той же машине с помощью Python 3.1 (Python 3.1.2 (r312:79147, Apr 15 2010, 15:35:48) [GCC 4.4.3] on linux2
), времена:
Norm 28.4206559658
Alt 26.8007400036
Кто-либо знает, почему этот код работает в три раза медленнее на Python 3.1?
Я получил стабильно уменьшающееся время от 2.5, 2.6, 2.7 и 3.1 (Windows XP SP2) ... с версией "/". С //, время 3.1 было значительно меньше, чем время 2.X, например, "Norm" упало с 6.35 (py2.7) до 3.62 (py3.1).
Обратите внимание, что в 2.x есть ints (машинное слово, 32 или 64 бита) и longs (переменная длина). В 3.x long был переименован в int, а int исчез. Я предполагаю, что преобразование из long в float может быть причиной дополнительного времени с /.
В любом случае, гораздо лучшая версия "Alt" начиналась бы с такого кода:
high = 1
highpown = 1
while highpown < x:
high <<= 1
highpown <<= n
Оператор //
выполняет целочисленное деление (или деление полов) как в Python 2, так и в 3, тогда как оператор /
выполняет деление полов в Python 2 с учетом целочисленных операндов и истинное деление в Python 3 с любыми операндами.
Попробуйте заменить оператор /
оператором //
.