Python: как настолько быстро?
Период вихря Мерсенна используется в модуле random (мне говорят), 2 ** 19937 - 1. Как двоичное число, которое является 19937 '1's подряд (если я не ошибаюсь). 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, так что он очень быстр. Только если вы распечатаете это в десятичной дроби, то реальное преобразование необходимо, а это намного медленнее.
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
.
b = aa = 10^4
c = bb = 10^16
d = c*c = 10^256
result = dccccccccbb*10
(Может быть дополнительно оптимизировано: см. Кнут, Семинумерные Алгоритмы)
Так что вам нужны только длинные умножения, и они могут быть вычислены красиво эффективно.
EDIT: Точная реализация умножения зависит: Кроме обычного школьного умножения Карацуба, Том-Кук и Шоенгаген-Штрассе (БФТ) умножение является следующим Использованный.
Я мало что знаю о том, как это на самом деле реализовано на Python, но учитывая, что это в основном примитивное умножение и логарифмы, меня не удивляет, что оно достаточно быстро даже на достаточно больших числах.
Существуют произвольные прецизионные математические библиотеки, такие как GMP, которые очень эффективно реализуют широкий спектр операций, оптимизированных при сборке, именно для этой цели.
Ненавижу дождь на вашем параде, но причина, по которой это так быстро, потому что математический модуль на самом деле не реализован в Python.
Python поддерживает нагрузочные общие библиотеки, которые экспортируют API на Python, но реализуются на других языках. Math.so, который предоставляет модуль вы попадаете из Импорт математики , случается, оказывается одним из тех (и так и _random.so).
При компиляции в байтовый код такие константные выражения как 2**19937 будут оптимизированы до одной константы:
>>> def foo(): return 2**10
...
>>> import dis
>>> dis.dis(foo)
1 0 LOAD_CONST 3 (1024)
3 RETURN_VALUE
>>>
Consider instead:
[~] python -m timeit 'x=2' 'x**19937'
1000 loops, best of 3: 210 usec per loop