Почему 2 * x * x быстрее, чем 2 * (x * x) в Python 3.x, для целых чисел?

Ответ 1

Прежде всего, обратите внимание, что мы не видим то же самое в Python 2.x:

>>> timeit("for i in range(1000): 2*i*i")
51.00784397125244
>>> timeit("for i in range(1000): 2*(i*i)")
50.48330092430115

Таким образом, это заставляет нас думать, что это связано с тем, как целые числа изменялись в Python 3: в частности, Python 3 использует long (произвольно большие целые числа) везде.

Для достаточно малых целых чисел (включая те, которые мы рассматриваем здесь) CPython фактически просто использует алгоритм умножения на цифровую цифру O (MN) по цифровому алгоритму (для больших целых чисел он переключается на алгоритм Карацубы). Вы сами видите это в источнике.

Число цифр в x*x примерно в два раза больше цифр 2*x или x (так как log (x ²) = 2 log (x)). Обратите внимание, что "цифра" в этом контексте не является базой-10, а 30-битным значением (которое рассматривается как отдельные цифры в реализации CPython). Следовательно, 2 является одноразрядным значением, а x и 2*x являются одноразрядными значениями для всех итераций цикла, но x*x является двузначным для x >= 2**15. Следовательно, для x >= 2**15, 2*x*x требуется только однократные умножения, тогда как для 2*(x*x) требуется однократная и однократная двузначная умножение (поскольку x*x имеет 2 30-битных цифры).

Вот прямой способ увидеть это (Python 3):

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
5.796971936999967
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
4.3559221399999615

Снова сравните это с Python 2, который не использует целые числа произвольной длины всюду:

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
3.0912468433380127
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
3.1120400428771973

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

Ответ 2

Представление Python для целых чисел является специальным, оно использует слоты в 30 бит:

In [6]: sys.getsizeof(2**30-1)
Out[6]: 28 # one slot + heading

In [7]: sys.getsizeof(2**30)
Out[7]: 32 # two slots 

Итак, все происходит так, как если бы Python рассчитывал в базе B = 2**30 = 1 073 741 824 ~1 billion.

Для человека, который хочет рассчитать 2 * 4 * 4, двумя способами:

• (2 * 4) * 4 = 8 * 4 = 32 = 30 + 2 немедленно, если вы знаете свои добавочные таблицы.
• 2 * (4 * 4) = 2 * 16 = 2 * 10 + 2 * 6 = (2 * 10 + 10) + 2 = 30 + 2, так как мы должны положить операцию вниз.

У Python такая же проблема. Если x - число, такое, что 2x < B < x², пусть x² = aB+b, a,b <B. x² хранится в 2 слотах, что я отмечаю (a|b). Вычисления приводят к (без управления здесь):

   (x*x)*2 =>  (a|b)*2 => (2*a|2*b)
   (2*x)*x =>  (2x)*x =>(2a|2b)

в первом случае операция 2* выполняется два раза, против только одного в первом случае. Это объясняет разницу.

Ответ 3

Если ваш тест правильный (не проверял), это может быть связано с тем, что целые числа Python могут быть двумя разными: нативные целые числа, когда они малы (с быстрым вычислением), и большие целые числа, когда они увеличиваются в размере (медленнее вычисление). Первый синтаксис позволяет уменьшить размер после первой операции, тогда как второй синтаксис может привести к двум операциям с большими целыми числами.

Ответ 4

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

Соответствующая часть 2 * x * x:

7          28 LOAD_FAST                1 (num)
           30 LOAD_CONST               3 (2)
           32 LOAD_FAST                2 (x)
           34 BINARY_MULTIPLY
           36 LOAD_FAST                2 (x)
           38 BINARY_MULTIPLY
           40 INPLACE_ADD
           42 STORE_FAST               1 (num)
           44 JUMP_ABSOLUTE           24

Соответствующая часть 2 * (x * x):

  7          28 LOAD_FAST                1 (num)
             30 LOAD_CONST               3 (2)
             32 LOAD_FAST                2 (x)
             34 LOAD_FAST                2 (x)
             36 BINARY_MULTIPLY                 <=== 1st multiply x*x in a temp value
             38 BINARY_MULTIPLY                 <=== then multiply result with 2
             40 INPLACE_ADD
             42 STORE_FAST               1 (num)
             44 JUMP_ABSOLUTE           24

Ответ 5

Отредактировано из-за предыдущего ответа, не относящегося к вопросу только потому, что я не получил то, что вам нужно.

Итак, ответ - это то, что сказал Б. М и аршаджий.