Скорость расчета мощности (в питоне)

Question

Мне любопытно, почему умножение намного быстрее, чем получение полномочий в python (хотя из того, что я читал, это вполне может быть верно и во многих других языках). Например, это гораздо быстрее сделать

x*x

чем

x**2

Полагаю, оператор ** является более общим и может также иметь дело с дробными степенями. Но если именно поэтому он намного медленнее, почему он не выполняет проверку для показателя int, а затем просто выполняет умножение?

Редактировать: Вот пример кода, который я пробовал ...

def pow1(r, n):
  for i in range(r):
    p = i**n

def pow2(r, n):
  for i in range(r):
    p = 1
    for j in range(n):
      p *= i

Теперь pow2 - всего лишь быстрый пример, и он явно не оптимизирован!
Но даже при этом я обнаружил, что при использовании n = 2 и r = 1 000 000, pow1 занимает ~ 2500 мс, а pow2 - ~ 1700 мс.
Я признаю, что для больших значений n тогда pow1 становится намного быстрее, чем pow2. Но это не так уж удивительно.

Answer 1

В основном наивное умножение - это O (n) с очень низким постоянным коэффициентом. Взятие мощности равно O (log n) с более высоким постоянным коэффициентом (есть особые случаи, которые необходимо проверить ... дробные показатели, отрицательные показатели и т. Д.). Изменить: просто чтобы быть ясно, это O (n), где n это показатель степени.

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

Answer 2

Добавление чека также является расходом. Вы всегда хотите эту проверку там? Скомпилированный язык может проверять постоянную экспоненту, чтобы увидеть, является ли она относительно небольшим целым числом, потому что нет затрат времени выполнения, а только времени компиляции. Интерпретированный язык может не выполнить эту проверку.

Это зависит от конкретной реализации, если такие детали не указаны языком.

Python не знает, каким распределением показателей вы собираетесь его кормить. Если это будет 99% нецелых значений, хотите ли вы, чтобы код каждый раз проверял целое число, делая выполнение еще медленнее?

Answer 3

Выполнение этого в проверке экспоненты замедлит случаи, когда это не простая степень двойки, а вовсе не выигрыш. Однако в случаях, когда показатель степени известен заранее (например, используется литерал 2), сгенерированный байт-код может быть оптимизирован с помощью простой оптимизации глазка. Предположительно, это просто не считалось целесообразным (это довольно конкретный случай).

Вот краткое доказательство концепции, которая выполняет такую ​​оптимизацию (может использоваться в качестве декоратора). Примечание: для запуска вам понадобится модуль byteplay .

import byteplay, timeit

def optimise(func):
    c = byteplay.Code.from_code(func.func_code)
    prev=None
    for i, (op, arg) in enumerate(c.code):
        if op == byteplay.BINARY_POWER:
            if c.code[i-1] == (byteplay.LOAD_CONST, 2):
                c.code[i-1] = (byteplay.DUP_TOP, None)
                c.code[i] = (byteplay.BINARY_MULTIPLY, None)
    func.func_code = c.to_code()
    return func

def square(x):
    return x**2

print "Unoptimised :", timeit.Timer('square(10)','from __main__ import square').timeit(10000000)
square = optimise(square)
print "Optimised   :", timeit.Timer('square(10)','from __main__ import square').timeit(10000000)

Что дает время:

Unoptimised : 6.42024898529
Optimised   : 4.52667593956

[Изменить] На самом деле, если подумать об этом, есть очень веская причина, почему эта оптимизация еще не закончена. Нет никаких гарантий, что кто-то не создаст пользовательский класс, который переопределяет методы __mul__ и __pow__ и будет делать что-то свое для каждого. Единственный способ сделать это безопасно, если вы можете гарантировать, что объект на вершине стека имеет тот же результат "x **2" и "x*x", но решить его намного сложнее. Например. в моем примере это невозможно, так как любой объект может быть передан функции квадрат.

Answer 4

Реализация b ^ p с бинарным возведением в степень

def power(b, p):
    """
    Calculates b^p
    Complexity O(log p)
    b -> double
    p -> integer
    res -> double
    """
    res = 1

    while p:
        if p & 0x1: res *= b
        b *= b
        p >>= 1

    return res

Answer 5

Я подозреваю, что никто не ожидал, что это будет так важно. Как правило, если вы хотите делать серьезные вычисления, вы делаете их в Fortran или C или C ++ или что-то в этом роде (и, возможно, вызываете их из Python).

Рассматривая все как exp (n * log (x)), хорошо работает в случаях, когда n не является целым или довольно большим, но относительно неэффективно для маленьких целых чисел. Проверка, является ли n достаточно маленьким целым числом, требует времени и добавляет сложность.

Ценность проверки зависит от ожидаемых показателей, от того, насколько важно добиться максимальной производительности, и от стоимости дополнительной сложности. По-видимому, Гвидо и остальные члены банды Python решили, что проверка не стоит того, чтобы ее делать.

Если хотите, вы можете написать свою собственную функцию повторного умножения.

Answer 6

как насчет х х х х х? это все еще быстрее, чем х ** 5?

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