Использование возведения в степень ** на 0,5 менее эффективно, чем math.sqrt?

Question

Цитата из " Python Programming: Введение в информатику"

Мы могли бы взять квадратный корень, используя возведение в степень **. Использование math.sqrt несколько более эффективно.

"В некоторой степени", но в какой степени и как?

Answer 1

Теоретически, ответ Хаммара и ответ Даффимо - хорошие догадки. Но на практике на моей машине это не более эффективно:

>>> import timeit
>>> timeit.timeit(stmt='[n ** 0.5 for n in range(100)]', setup='import math', number=10000)
0.15518403053283691
>>> timeit.timeit(stmt='[math.sqrt(n) for n in range(100)]', setup='import math', number=10000)
0.17707490921020508

Часть проблемы заключается в . операция. Если вы импортируете sqrt непосредственно в пространство имен, вы получаете небольшое улучшение.

>>> timeit.timeit(stmt='[sqrt(n) for n in range(100)]', setup='from math import sqrt', number=10000)
0.15312695503234863

Ключевое слово там: небольшое.

Дальнейшее тестирование показывает, что с увеличением числа вы получаете выгоду от использования sqrt увеличивается. Но все же не так много!

>>> timeit.timeit(stmt='[n ** 0.5 for n in range(1000000)]', setup='import math', number=1)
0.18888211250305176
>>> timeit.timeit(stmt='[math.sqrt(n) for n in range(1000000)]', setup='import math', number=1)
0.18425297737121582
>>> timeit.timeit(stmt='[sqrt(n) for n in range(1000000)]', setup='from math import sqrt', number=1)
0.1571958065032959

Answer 2

Не нужно угадывать реализацию, мы можем прочитать код!

math.sqrt это тонкая обертка sqrt из стандартной библиотеки C: см. mathmodule.c линия 956

** Оператор имеет несколько реализаций в зависимости от типов аргументов, но в случае показателя с плавающей точкой он в конечном итоге отправляется pow из стандартной библиотеки C (см. floatobject.c строка 783).

Современные ЦП часто имеют специальные квадратно-корневые инструкции, которые не используются общими процедурами возведения в степень (сравнивайте и сравнивайте реализации pow а также sqrt в glibc для x86-64, например). Но как только все служебные данные интерпретатора добавляются (байтовые коды, проверка типов, отправка методов и т. Д.), Разница в необработанной скорости не имеет большого значения, и на нее могут влиять такие проблемы, как, например, вызов sqrt непосредственно или посмотрите через math модуль (как показано на время в других ответах).

Answer 3

** должен поддерживать любой показатель в то время как math.sqrt знает, что это всегда 0.5, math.sqrt поэтому можно использовать более специализированный (и, следовательно, вероятно, более эффективный) алгоритм.

Answer 4

Я предполагаю, что math.sqrt использует метод Ньютона, который сходится квадратично, а возведение в степень - что-то более медленное.

Answer 5

Вот немного другой подход. Мы хотим, чтобы int был больше, чем квадратный корень. Два способа (которые не согласны с квадратными числами, но это нормально):

>>>timeit.timeit(stmt='[int(n**0.5)+1 for n in range(1000000)]', setup='', number=1)  
0.481772899628  
>>>timeit.timeit(stmt='[ceil(sqrt(n)) for n in range(1000000)]', setup='from math import sqrt, ceil', number=1)  
0.293844938278  
>>>timeit.timeit(stmt='[int(ceil(sqrt(n))) for n in range(1000000)]', setup='from math import sqrt, ceil', number=1)  
0.511347055435

Так что математические функции быстрее... пока вы не конвертируете число с плавающей точкой в ​​int. (Мне нужно сделать много сравнений со значением, и хотя я не проверял его, сравнение целых чисел должно быть дешевле, чем сравнение чисел с плавающей запятой.)

Но эй, это Питон. У вас слишком много абстракций, чтобы попытаться оптимизировать производительность с таким уровнем детализации.