Python: как быстро?

Question

Период Mersenne Twister, используемый в модуле random, равен (мне сказали) 2 ** 19937 - 1. Как двоичное число, это 19937 '1-е подряд (если я не ошибаюсь) , Python преобразует его в десятичный довольно чертовски быстро:

$ python -m timeit '2**19937'
10000000 loops, best of 3: 0.0271 usec per loop

$ python -m timeit -s 'result = 0' 'result += 2**19937'
100000 loops, best of 3: 2.09 usec per loop

Полагаю, вторая версия требует преобразования?

И это не просто двоичный файл. Это тоже быстро. (Вместо того, чтобы показывать числа, я показываю длину десятичной дроби, преобразованной в строку):

>>> import math
>>> N = 1000
>>> s = str((int(N*math.e))**(int(N*math.pi)))
>>> len(s)
10787
>>> N = 5000
>>> s = str((int(N*math.e))**(int(N*math.pi)))
>>> len(s)
64921

Сроки:

python -m timeit -s 'import math' -s 'N=1000' 's = str((int(N*math.e))**(int(N*math.pi)))'
10 loops, best of 3: 51.2 msec per loop

Вопрос: как это на самом деле делается?

Я просто наивен, чтобы быть впечатленным? Я нахожу вид оболочки Python, генерирующей около 5000 мест в одно мгновение, действительно впечатляющим.

Edit:

Дополнительные временные параметры, предложенные @dalke и @ truppo

$ python -m timeit 'x=2' 'x**19937'
1000 loops, best of 3: 230 usec per loop
$ python -m timeit 'x=2' 'int(x**19937)'
1000 loops, best of 3: 232 usec per loop
$ python -m timeit 'x=2' 'str(x**19937)'
100 loops, best of 3: 16.6 msec per loop

$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937'
1000 loops, best of 3: 237 usec per loop
$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937' 'int(result)'
1000 loops, best of 3: 238 usec per loop
$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937' 'str(result)'
100 loops, best of 3: 16.6 msec per loop

Так что мне кажется, что result = 0; result += 2**19937, вероятно, вызывает преобразование.

Answer 1

Ненавижу дождь на вашем параде, но причина, по которой он так быстр, в том, что математический модуль фактически не реализован в Python.

Python поддерживает загрузку общих библиотек, которые экспортируют API-интерфейсы Python, но реализованы на других языках. math.so, который предоставляет модуль, который вы получаете из import math, оказывается одним из них (как и _random.so).

Answer 2

При компиляции в байт-код константные выражения, такие как 2**19937, будут оптимизированы до одной константы:

>>> def foo(): return 2**10
... 
>>> import dis
>>> dis.dis(foo)
  1           0 LOAD_CONST               3 (1024)
              3 RETURN_VALUE        
>>> 

Рассмотрим вместо этого:

[~] python -m timeit 'x=2' 'x**19937'
1000 loops, best of 3: 210 usec per loop

Answer 3

Python преобразует его в десятичный довольно чертовски быстро.

Я не знаю Python, но нет, этого не нужно делать. 2 ^ 19937 не требует вычислений, это просто двоичный сдвиг («<<») с 19937, поэтому он очень быстрый. Только если вы напечатаете это в десятичном виде, фактическое преобразование необходимо, и это намного медленнее. </p>

EDIT: Возведение в степень может быть таким же, как сдвиг (= перемещение точки), если числовая база идентична базовой экспоненты.

10 ^ -1 = 0,1 10 ^ 0 = 1
10 ^ 1 = 10
10 ^ 2 = 100
10 ^ 3 = 1000
10 ^ n = 1 (n нулей)

Вы видите, что возведение в степень 10 с показателем n просто сдвигает число. Теперь компьютеры в основном используют внутреннюю базу 2 (биты), поэтому при вычислении 2 ^ 19937 бит устанавливается в позицию 19937 (считая битовые позиции от нуля).
В качестве дополнительной информации: Преобразование в десятичную форму обычно выполняется с помощью алгоритма «разделяй и властвуй», который последовательно делит число на степени десяти. Как вы видите, фактическое преобразование медленнее в полмиллиона раз.

Второй пример более интересен: поскольку вы вычисляете m ^ n с большими целыми числами m, n самым быстрым способом является его умножение подряд и сохранение временных результатов.

Пример: 10 ^ 345

a = 10 ^ 2
б = а а = 10 ^ 4
с = b b = 10 ^ 16
д = с * с = 10 ^ 256

результат = d c c c c c c c c b b * 10

(Может быть дополнительно оптимизировано: см. Кнут, Полу-численные алгоритмы)

Так что вам нужны только длинные умножения, и они могут быть вычислены довольно эффективно.

РЕДАКТИРОВАТЬ: Точная реализация умножения зависит: Помимо умножения в обычной школе умножение Карацубы, Тома-Кука и Шёнхагена-Штрассе (БПФ) б.

Answer 4

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

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