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

Мне любопытно, почему это намного быстрее, чтобы размножаться, чем принимать полномочия в 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. Но это не слишком удивительно.

Ответ 1

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

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

Ответ 2

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

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

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

Ответ 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", но работать с этим намного сложнее. Например. в моем примере это невозможно, поскольку любой объект может быть передан квадратной функции.

Ответ 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

Ответ 5

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

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

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

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

Ответ 6

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

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