Python：どれくらい速いですか？

Question

モジュールで使用されている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

2番目のバージョンは変換が必要なバージョンだと思いますか？

そして、それは単なるバイナリではありません。これも高速です。 （数字を表示するのではなく、文字列に変換された小数の長さを表示します）：

>>> 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 おそらく変換を強制します。

Answer 1

Pythonは、それをかなり速く小数点に変換します。

私はPythonを知りませんが、いや、それをする必要はありません。 2^19937計算は必要ありません。19937の単なるバイナリシフト（ "<<"）であるため、非常に高速です。それを10進数で印刷する場合にのみ、実際の変換が必要であり、それははるかに遅くなります。

編集：指数ベースが指数ベースと同一である場合、指数はシフト（=ポイントの移動）と同じです。

10^-1 = 0.1 10^0 = 1
10^1 = 10
10^2 = 100
10^3 = 1000
10^n = 1（nゼロ）

指数nを使用した10の指数が数字をシフトすることがわかります。現在、コンピューターは主に内部ベース2（ビット）を使用しているため、2^19937の計算は19937（ゼロからビット位置をカウント）に少し設定しています。
追加情報として：10進数への変換は通常、数を10のパワーで連続的に分割する征服とディバイドのアルゴリズムによって実装されます。ご覧のとおり、実際の変換は50万倍遅くなります。

2番目の例はより興味深いものです。大きな整数mでm^nを計算しているため、最速の方法はそれを連続して乗算し、一時的な結果を保存することです。

例：10^345

a = 10^2
b = aa = 10^4
c = bb = 10^16
d = c*c = 10^256

結果= dccccccccbB*10

（さらに最適化できます：Knuth、Seminumerical Algorithmsを参照）

したがって、長い乗算だけが必要であり、それらはかなり効果的に計算できます。

編集：乗算の正確な実装は次のとおりです。通常の学校の乗算カルツバ、Tom-Cooke、Schoenhagen-Strasse（FFT）の乗算が使用されます。

Answer 2

パレードで雨が降るのは嫌いですが、それが非常に速い理由は、数学モジュールが実際にPythonで実装されていないためです。

Pythonは、Python APIをエクスポートするが、他の言語で実装されている共有ライブラリの読み込みをサポートしています。 Math.SO、あなたが得るモジュールを提供します import math, 、たまたまそれらの1つです（そして_random.soもそうです）。

Answer 3

バイトコードにコンパイルするとき、 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 4

私はこれがどのようなものであるかについてほとんど何も知らない 実際に Pythonで実装されていますが、これが基本的に原始的な乗算と対数であることを考えると、非常に速いことでもかなり速いことに、私はそれほど驚かないことはありません。

などの任意の精密な数学ライブラリがあります GMP この目的のために、アセンブリで最適化された非常に効果的な方法で多種多様な操作を実装します。