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

Период Mersenne Twister, используемый в модуле random is (мне сказали) 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 мест в одно мгновение, действительно впечатляющим.

Редактировать:

Дополнительные тайминги, предложенные @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 вероятно, заставляет преобразование.

Источник

4 ответа

Решение

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

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

РЕДАКТИРОВАТЬ: Возведение в степень может быть таким же, как сдвиг (= перемещение точки), если числовая база идентична базовой экспоненты.

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

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

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

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

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

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

Источник

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

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

Источник

При компиляции в байт-код, константные выражения, такие как 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
Источник

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

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

Источник
Другие вопросы по тегам