Usando exponenciación ** 0.5 menos eficiente que math.sqrt?

Question

Una cita de "Python Programming: An Introduction to Computer Science"

que podríamos haber tomado el uso de exponenciación raíz cuadrada **. El uso de math.sqrt es algo más eficiente.

"Algo", pero ¿en qué medida y cómo?

Answer 1

Teóricamente, hammar's answer y duffymo's answer son buenas conjeturas. Pero en la práctica, en mi máquina, no es más eficiente:

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

Parte del problema es la operación .. Si importa sqrt directamente en el espacio de nombres, obtiene una ligera mejora.

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

palabra clave existe: ligero.

Las pruebas adicionales indican que a medida que el número aumenta, la ventaja que obtiene al usar sqrt aumenta. ¡Pero todavía no por mucho!

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

** tiene que admitir cualquier exponente, mientras que math.sqrt sabe que siempre es 0.5. math.sqrt puede por lo tanto usar un algoritmo más especializado (y por lo tanto probablemente más eficiente).

Answer 3

Mi conjetura es que math.sqrt utiliza Newton's method, que converge cuadráticamente y exponenciación utiliza otra cosa que es más lento.

Answer 4

¡No hace falta adivinar la implementación, podemos leer el código!

math.sqrt es una envoltura delgada sobre sqrt de la biblioteca estándar de C: ver mathmodule.c, line 956

El operador ** tiene múltiples implementaciones en función de los tipos de los argumentos, pero en el caso de un exponente de coma flotante, con el tiempo se distribuye al pow desde la biblioteca C estándar (consulte floatobject.c line 783).

Las CPU modernas a menudo tienen instrucciones de raíz cuadrada especiales que las rutinas de exponenciación generales no usan (comparar y contrastar las implementaciones de pow y sqrt en glibc para x86-64, por ejemplo). Pero una vez que se agrega toda la sobrecarga del intérprete (códigos de bytes, verificación de tipos, envío de métodos, etc.), la diferencia en la velocidad bruta no importa demasiado, y puede estar dominada por problemas como llamar al sqrt directamente o buscarlo a través de el módulo math (como se muestra por los tiempos en otras respuestas).

Answer 5

Aquí hay un enfoque ligeramente diferente. Queremos un int simplemente más grande que la raíz cuadrada. Dos maneras (que discrepan de los números cuadrados, pero eso está bien):

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

Así las funciones matemáticas son más rápidos ... hasta que convierta el flotador a int.(Tengo que hacer muchas comparaciones con el valor, y aunque no lo he probado, que comparan números enteros debería ser más barato que los flotadores de comparación.)

Pero bueno, es Python. Está al tanto de demasiadas abstracciones para tratar de optimizar el rendimiento con este nivel de detalle.