6

モジュールで使用されているメルセンヌ ツイスターの周期randomは (聞いたところでは) 2**19937 - 1 です。2 進数としては、19937 '1 が連続しています (私の間違いでなければ)。Python はこれを非常に高速に 10 進数に変換します。

$ 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 番目のバージョンだと思いますか?

そして、それは単なるバイナリではありません。これも速いです。(数字を表示するのではなく、文字列に変換された 10 進数の長さを表示します):

>>> 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

4 に答える 4

6

あなたのパレードに雨が降るのを嫌いますが、それがとても速い理由は、数学モジュールが実際には Python で実装されていないからです.

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

于 2010-01-23T23:27:00.313 に答える
5

バイトコードにコンパイルする場合、次のような定数式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
于 2010-01-23T23:49:35.697 に答える
4

Pythonはそれを10進数に変換します。

私は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を計算しているので、nを連続して乗算し、一時的な結果を保存するのが最も速い方法です。

例：10 ^ 345

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

結果=dc c c c c c c c b b * 10

（さらに最適化することができます：クヌース、半数値アルゴリズムを参照してください）

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

編集：乗算の正確な実装は異なります：通常の学校の乗算に加えて、カラツバ、トム-クークとシェーンハーゲン-シュトラーセ（FFT）の乗算が使用されます。

于 2010-01-23T23:48:54.310 に答える
0

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

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

于 2010-01-23T23:28:48.177 に答える