Korzystanie z potęgowania ** 0,5 mniej wydajne niż math.sqrt?

Question

Cytat z „Python Programming: An Introduction to Computer Science”

Mogliśmy podjęły pierwiastek kwadratowy użyciu potęgowanie **. Korzystanie zmath.sqrt jest nieco bardziej wydajne.

"Nieco", ale w jakim stopniu i jak?

Answer 1

Teoretycznie, hammar's answer i duffymo's answer są dobrymi przypuszczeniami. Jednak w praktyce, na moim komputerze, to nie bardziej efektywne:

>>> 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 

Częścią problemu jest operacja .. Jeśli importujesz plik sqrt bezpośrednio do przestrzeni nazw, uzyskujesz niewielką poprawę.

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

Słowo kluczowe istnieje: niewielkie.

Dalsze testowanie wskazuje, że wraz ze wzrostem liczby zwiększa się korzyść, którą można uzyskać dzięki użyciu sqrt. Ale wciąż nie przez wiele!

>>> 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

** musi obsługiwać każdy wykładnik, podczas gdy math.sqrt wie, że zawsze jest to 0.5. math.sqrt może zatem używać bardziej wyspecjalizowanego (a zatem prawdopodobnie bardziej wydajnego) algorytmu.

Answer 3

Domyślam się, że Math.sqrt wykorzystuje Newton's method, który zbiega kwadratowo i potęgowanie używa czegoś innego, który jest wolniejszy.

Answer 4

Nie trzeba zgadywać realizacji, możemy odczytać kod!

math.sqrt jest cienką owijki wokół sqrt ze standardowej biblioteki C: patrz mathmodule.c, line 956

Operator ** ma wiele implementacje, w zależności od typów argumentów, ale w przypadku zmiennoprzecinkowej wykładnik, ostatecznie wywołania do pow ze standardowej biblioteki C (patrz floatobject.c line 783).

Nowoczesne procesory często mają specjalne instrukcje dotyczące pierwiastków kwadratowych, których nie używają ogólne procedury potęgowania (porównaj i porównuj implementacje pow i sqrt w glibc dla x86-64, na przykład). Ale po dodaniu wszystkich kosztów obsługi interpretatora (kody bajtów, sprawdzanie typu, wysyłanie metod itp.) Różnica w prędkości początkowej nie ma większego znaczenia i może być zdominowana przez takie problemy, jak zadzwonienie pod numer sqrt bezpośrednio lub wyszukiwanie za pośrednictwem moduł math (co pokazują czasy w innych odpowiedziach).

Answer 5

Oto nieco inne podejście. Chcemy, aby int był większy niż pierwiastek kwadratowy. Dwa sposoby (które nie zgadzają się z numerami kwadratowych ale to jest OK):

>>>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 

Więc funkcje matematyczne są szybciej ... aż przekonwertować pływaka do int.(Muszę wykonać wiele porównań z wartością, a gdy tego nie testowałem, porównywanie liczb całkowitych powinno być tańsze niż porównywanie pływaków.)

Ale hej, to Python. Masz zbyt wiele abstrakcji, by spróbować zoptymalizować wydajność przy takim poziomie szczegółowości.