Я хочу найти квадратный корень из числа без использования математического модуля, так как мне нужно вызвать функцию примерно 20k раз и не хочу замедлять выполнение, связываясь с математическим модулем каждый раз, когда функция вызывается
Есть ли более быстрый и простой способ поиска квадратного корня?
Импорт математического модуля происходит только один раз, и вы, вероятно, не получите гораздо быстрее, чем математический модуль. Существует также более старый вопрос о Stackoverflow относительно который быстрее в Python: x **. 5 или math.sqrt(x)?. Неясно, какой метод выполняется быстрее.
Возможно, посмотрите NumPy и SciPy, не обязательно для sqrt, но если вы делаете тяжелые вычисления, они могут быть удобными.
Как сказал Фабиан, трудно быть быстрее, чем math.sqrt. Причина в том, что он вызывает функцию соответствия из библиотеки C, с CPython.
Однако вы можете ускорить процесс, удалив служебные данные поиска атрибутов:
from math import sqrt
Каждый последующий вызов sqrt не должен искать его в математическом модуле, что экономит время выполнения:
print sqrt(2)
Здесь приведены временные номера: от самого быстрого до самого медленного (Python 2.6.5, Mac OS X 10.6.3): sqrt быстрее, чем **0.5:
[email protected] ~ % python -m timeit -s 'from math import sqrt; x = 2' 'sqrt(x)'
1000000 loops, best of 3: 0.207 usec per loop
[email protected] ~ % python -m timeit -s 'x = 2' 'x**0.5'
1000000 loops, best of 3: 0.226 usec per loop
[email protected] ~ % python -m timeit -s 'import math; x = 2' 'math.sqrt(x)'
1000000 loops, best of 3: 0.268 usec per loop
Обратите внимание, что тесты времени вычисляют квадратный корень переменной. Они не вычисляют константу как 2**0.5, потому что 2**0.5 предварительно вычисляется в CPython:
import dis
def f():
return 2**0.5
print dis.dis(f)
печатает
2 0 LOAD_CONST 3 (1.4142135623730951)
3 RETURN_VALUE
где вы видите константу float sqrt (2) = 1.414...
Если вы манипулируете массивами чисел, NumPy sqrt - это путь, как указано в другом ответе.
Я думаю, что математическая библиотека, вероятно, будет так же быстро, как и все, что вы могли бы написать сами. Но если вы хотите написать свой собственный, вот один алгоритм. Я не знаю Python, поэтому я просто напишу какой-нибудь псевдокод.
function sqrt(x)
lastGuess=x/2
loop
guess=(lastGuess+x/lastGuess)/2
if abs(guess-lastGuess)<.000001 // or whatever threshold you want
exit loop
lastGuess=guess
return guess
и псевдокод, переведенный на Python:
def sqrt(x):
last_guess= x/2.0
while True:
guess= (last_guess + x/last_guess)/2
if abs(guess - last_guess) < .000001: # example threshold
return guess
last_guess= guess
В некоторых особых случаях вы можете торговать размером программы для скорости вздутия. Создайте большой массив и сохраните предварительно рассчитанный результат для каждой операции с квадратным корнем (используя входное значение в качестве индекса). Это довольно ограничено, но вы не получите ничего быстрее.
(Это как землетрясение)
Вы можете реализовать метод Newton, но, хотя он очень быстро, он вряд ли будет быстрее, чем версия C, которую я предполагаю, реализована в математическом модуле. См. http://en.wikipedia.org/wiki/Methods_of_computing_square_roots.
Используйте оператор питания и поднимите свои цифры на 1/2 мощности:
>>> 2**0.5
1.4142135623730951
Что происходит быстрее:
>>> timeit.timeit(stmt='sqrt(x)', setup='from math import sqrt; x = 2')
0.7182440785071833
>>> timeit.timeit(stmt='x**0.5', setup='from math import sqrt; x = 2')
0.87514279049432275
Фрагмент кода Python для вычисления квадрата. Сначала он делает предварительную догадку, и если догадка не достаточно хороша, она повторяется до тех пор, пока мы не получим хорошее предположение
def gen_square_root_v1(number, epsilon):
#boundary condition check
if number == '1':
return 1
elif number <= 0:
print('this computes square root for positive numbers only' )
else:
pass
prev_estimate = number/2
while True:
#each itearation, calculate a new estimate
new_estimate = (prev_estimate + number/prev_estimate)/2
#Alternatively can use if abs(new_estimate - prev_estimate) < epsilon:
#check the difference between square of new_estimate and number
if abs(new_estimate * new_estimate - number) < epsilon:
return prev_estimate
#if guess is not good enough, use it to make the next guess
prev_estimate = new_estimate
#call the function
print(gen_square_root_v1(16,1e-5))