Почему x ** 3 медленнее, чем x * x * x?

Ответ 1

В соответствии с этим ответом это потому, что реализация возведения в степень имеет некоторые накладные расходы, которые не умножаются. Однако наивное умножение будет медленнее и медленнее по мере увеличения показателя. Эмпирическая демонстрация:

 In [3]: x = np.random.rand(1e6)

 In [15]: %timeit x**2
 100 loops, best of 3: 11.9 ms per loop

 In [16]: %timeit x*x
 100 loops, best of 3: 12.7 ms per loop

 In [17]: %timeit x**3
 10 loops, best of 3: 132 ms per loop

 In [18]: %timeit x*x*x
 10 loops, best of 3: 27.2 ms per loop

 In [19]: %timeit x**4
 10 loops, best of 3: 132 ms per loop

 In [20]: %timeit x*x*x*x
 10 loops, best of 3: 42.4 ms per loop

 In [21]: %timeit x**10
 10 loops, best of 3: 132 ms per loop

 In [22]: %timeit x*x*x*x*x*x*x*x*x*x
 10 loops, best of 3: 137 ms per loop

 In [24]: %timeit x**15
 10 loops, best of 3: 132 ms per loop

 In [25]: %timeit x*x*x*x*x*x*x*x*x*x*x*x*x*x*x
 1 loops, best of 3: 212 ms per loop

Обратите внимание, что время экспонирования остается более или менее постоянным, за исключением случая x**2, который, как я подозреваю, имеет специальную оболочку, а умножение становится медленнее и медленнее. Кажется, вы можете использовать это, чтобы получить более высокую степень экспоненциальности... например:

In [26]: %timeit x**16
10 loops, best of 3: 132 ms per loop

In [27]: %timeit x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x
1 loops, best of 3: 225 ms per loop

In [28]: def tosixteenth(x):
   ....:     x2 = x*x
   ....:     x4 = x2*x2
   ....:     x8 = x4*x4
   ....:     x16 = x8*x8
   ....:     return x16
   ....:

In [29]: %timeit tosixteenth(x)
10 loops, best of 3: 49.5 ms per loop

Кажется, вы могли применить эту технику в общем случае, разделив любое целое число на сумму степеней двух, вычисляя каждую степень двух, как указано выше, и суммируя:

In [93]: %paste
def smartintexp(x, exp):
    result = np.ones(len(x))
    curexp = np.array(x)
    while True:
        if exp%2 == 1:
            result *= curexp
        exp >>= 1
        if not exp: break
        curexp *= curexp
    return result
## -- End pasted text --

In [94]: x
Out[94]:
array([ 0.0163407 ,  0.57694587,  0.47336487, ...,  0.70255032,
        0.62043303,  0.0796748 ])

In [99]: x**21
Out[99]:
array([  3.01080670e-38,   9.63466181e-06,   1.51048544e-07, ...,
         6.02873388e-04,   4.43193256e-05,   8.46721060e-24])

In [100]: smartintexp(x, 21)
Out[100]:
array([  3.01080670e-38,   9.63466181e-06,   1.51048544e-07, ...,
         6.02873388e-04,   4.43193256e-05,   8.46721060e-24])

In [101]: %timeit x**21
10 loops, best of 3: 132 ms per loop

In [102]: %timeit smartintexp(x, 21)
10 loops, best of 3: 70.7 ms per loop

Это быстро для малых четных степеней двух:

In [106]: %timeit x**32
10 loops, best of 3: 131 ms per loop

In [107]: %timeit smartintexp(x, 32)
10 loops, best of 3: 57.4 ms per loop

Но становится медленнее по мере увеличения экспоненты:

In [97]: %timeit x**63
10 loops, best of 3: 133 ms per loop

In [98]: %timeit smartintexp(x, 63)
10 loops, best of 3: 110 ms per loop

И не быстрее для больших худших случаев:

In [115]: %timeit x**511
10 loops, best of 3: 135 ms per loop

In [114]: %timeit smartintexp(x, 511)
10 loops, best of 3: 192 ms per loop

Ответ 2

В качестве примечания, если вы вычисляете полномочия и беспокоитесь о скорости:

x = np.random.rand(5e7)

%timeit x*x*x
1 loops, best of 3: 522 ms per loop

%timeit np.einsum('i,i,i->i',x,x,x)
1 loops, best of 3: 288 ms per loop

Почему einsum быстрее, остается открытым вопросом . Хотя его, как из-за einsum, можно использовать SSE2, в то время как numpy ufuncs не будет до 1,8.

На месте еще быстрее:

def calc_power(arr):
    for x in xrange(arr.shape[0]):
        arr[x]=arr[x]*arr[x]*arr[x]
numba_power = autojit(calc_power)

%timeit numba_power(x)
10 loops, best of 3: 51.5 ms per loop

%timeit np.einsum('i,i,i->i',x,x,x,out=x)
10 loops, best of 3: 111 ms per loop

%timeit np.power(x,3,out=x)
1 loops, best of 3: 609 ms per loop

Ответ 3

Я ожидаю, потому что x**y должен обрабатывать общий случай, когда оба x и y являются float. Математически мы можем написать x**y = exp(y*log(x)). Следуя вашему примеру, я нахожу

x = np.random.rand(1e6)
%timeit x**3
10 loops, best of 3: 178 ms per loop

%timeit np.exp(3*np.log(x))
10 loops, best of 3: 176 ms per loop

Я не проверял фактический код numpy, но он должен делать что-то вроде этого внутри.

Ответ 4

Это связано с тем, что полномочия в python выполняются как операция с плавающей точкой (это верно и для numpy, так как использует C).

В C функция pow предоставляет 3 метода:

double pow (double x, double y)

long powl (длинный двойной x, длинный двойной y)

float powf (float x, float y)

Каждый из них представляет собой операции с плавающей запятой.

Ответ 5

Согласно spec:

Форма двух аргументов pow (x, y) эквивалентна использованию мощности оператор: x ** y.

Аргументы должны иметь числовые типы. Со смешанными типами операндов применяются правила принуждения для двоичных арифметических операторов.

Другими словами: поскольку x - это float, экспонента преобразуется из int в float, и выполняется операция генерирования полной с плавающей запятой. Внутренне это обычно переписывается как:

x**y = 2**(y*lg(x))

2**a и lg a (логарифм логарифма 2 от a) - это отдельные инструкции для современных процессоров, но он по-прежнему занимает гораздо больше времени, чем несколько умножений.

Ответ 6

timeit np.multiply(np.multiply(x,x),x)

раз совпадает с x*x*x. Я предполагаю, что np.multiply использует быстрый пакет линейной алгебры Fortran, такой как BLAS. Я знаю из другой проблемы, что numpy.dot использует BLAS для определенных случаев.

Мне нужно это вернуть. np.dot(x,x) в 3 раза быстрее, чем np.sum(x*x). Таким образом, преимущество скорости np.multiply не согласуется с использованием BLAS.

С моим numpy (время будет отличаться в зависимости от машины и доступных библиотек)

np.power(x,3.1)
np.exp(3.1*np.log(x))

взять примерно то же время, но

np.power(x,3)

равно 2x так же быстро. Не так быстро, как x*x*x, но все же быстрее, чем общая мощность. Поэтому он использует некоторое преимущество целочисленной мощности.