ランダムな整数を生成するための「通常の」方法が遅いのはなぜですか？

Question

数学専攻でもCS専攻でもなく、私はPython（通常はビデオゲームのシミュレーション/理論作成のためのスクリプトを作っています）を騙していて、random.randintの性能が賢明でないことを発見しました。 random.randintやrandom.randrangeがなぜ使用されているのか、どうやって作られたのか不思議です。私はrandom.randintするために同一の結果（すべての意図と実際の目的のために）を生成する機能を作った：

big_bleeping_float= (2**64 - 2)/(2**64 - 2) 
def fastrandint(start, stop): 
    return start + int(random.random() * (stop - start + big_bleeping_float)) 

範囲（両端を含む）の整数を生成するためにそれを使用して大規模な180％の速度向上があります0- random.randrange（0、66）と比較して、次の最も速い方法です。

>>> timeit.timeit('random.randint(0, 66)', setup='from numpy import random', number=10000) 
0.03165552873121058 

>>> timeit.timeit('random.randint(0, 65)', setup='import random', number=10000) 
0.022374771118336412 

>>> timeit.timeit('random.randrange(0, 66)', setup='import random', number=10000) 
0.01937231027605435 

>>> timeit.timeit('fastrandint(0, 65)', setup='import random; from fasterthanrandomrandom import fastrandint', number=10000) 
0.0067909916844523755 

また、random.choiceに代わるものとして、この関数の適応は、75％高速で、私は追加確信大よりオン段差私はそれをテストしていないものの、範囲は（速くなり）。あなたは、単にインラインでそれを書くことができますfastrandint機能を使用して、ほぼ倍の速度の向上のために：それは良い場合

>>> timeit.timeit('int(random.random() * (65 + big_bleeping_float))', setup='import random; big_bleeping_float= (2**64 - 2)/(2**64 - 2)', number=10000) 
0.0037642723021917845 

ので要約では、なぜ私は私の機能が優れていることを間違っている、なぜそれが、高速で、私がやっていることをもっと速くやり遂げる方法はありますか？

Answer 1

これはおそらくほとんど問題ではありませんが、randint(0,10**1000)が動作し、fastrandint(0,10**1000)がクラッシュします。遅く時間が

Answer 2

random.randint() ...おそらく、あなたはすべての可能な場合のために働く機能を持って支払う必要が価格で、他は直接random()への呼び出しが、正当な理由という非効率的でありうるrandom.getrandbits()に呼びかけています。

実際には、random.getrandbits()を呼び出すrandintを使用する方が、より偏りのない方法で行うことができます。

random.randomを使用して範囲内の値を生成すると、0と1の間のM浮動小数点数しかないため（Mがかなり大きいため）、偏ってしまうことがわかります。 Mに分割しないNをとり、0<r<Nに対してM = k N + rと書く。最高でもrandom.random() * (N+1) を使用すると、の確率は確率（k + 1）/ Mで出現し、N-rの数字は確率k/Mで出てきます。 （これはで、最高でです。実際には、バイアスの悪化が予想されます）。このバイアスは

• サンプリング
Nが（0,1]

におけるフロートの数Mの大部分である

の多数のためにのみ顕著であること

注したがって、科学計算などの偏りのない値が必要であることがわかっていない限り、おそらくあなたにとって重要ではありません。

対照的に、randint(0,N)の値はrandom.getrandbits()への繰り返し呼び出しからの拒否サンプリングを使用して除算します。もちろん、これを管理することで追加のオーバーヘッドが生じる可能性があります別に

カスタムランダムな実装を使用して終了した場合

その後、python 3 docs

から

ほとんどすべてのモジュールの機能が が生成するランダムな基本機能（）に依存半オープン範囲[0.0,1.0]で一様にフロートします。

これはrandintなどがrandom.randomを使用して実施することができることを示唆しています。このような場合には、遅くなることが予想されますが、 は、コールごとに少なくとも1つの追加機能コールオーバーヘッドが発生します。

https://stackoverflow.com/a/37540577/221955で参照されているコードを見ると、ランダムな実装でgetrandbits()機能が提供されない場合に発生することがわかります。

Answer 3

randintrandrangeを呼び出し、範囲/タイプのチェックと変換を行い、次に_randbelowを使用してランダムintを生成します。 _randbelowは再び範囲チェックを行い、最終的にrandomを使用します。

エッジケースと関数呼び出しオーバーヘッドのすべてのチェックを削除しても、fastrandintが高速です。