0からlog（len（list）、2）の範囲を作成するのがなぜ遅いのですか？

Question

私には、なぜこれが起こっているのかという手がかりはありません。私はいくつかのリストを使いこなしていたので、ループは0からlog(n, 2)になるforループが必要でした。ここで、nはリストの長さです。しかし、コードは驚くほど遅かったので、ちょっとした研究の後に問題がレンジ生成にあることが分かりました。デモ用サンプルコード：

n = len([1,2,3,4,5,6,7,8]) 
k = 8 
timeit('range(log(n, 2))', number=2, repeat=3) # Test 1 
timeit('range(log(k, 2))', number=2, repeat=3) # Test 2 

出力

2 loops, best of 3: 2.2 s per loop 
2 loops, best of 3: 3.46 µs per loop 

テストの数は、（私はこれが10分以上を実行していることを望まなかった）低いですが、それはすでにrange(log(n, 2))があることを示しています整数の対数だけを使用して、対応するものよりも桁違いのオーダです。これは本当に驚くべきことですが、私はなぜこれが起こっているのかについて何の手がかりも持っていません。たぶん私のPCの問題、おそらくSageの問題かPythonのバグです（私はPythonでも同じことをやっていませんでした）。

rangeの代わりにxrangeを使用するとどちらも役に立ちません。また、.n()で番号を取得した場合、テスト1は2の同じ速度で実行されます。

何が起こっているのか分かりませんか？ ありがとう！

Answer 1

良い悲しみ - 私はこれを認識します。それは私のもの、traC#12121に関連しています。

sage: log(8, 2) 
3 
sage: type(log(8, 2)) 
sage.rings.integer.Integer 
sage: log(8r, 2) 
log(8)/log(2) 
sage: type(log(8r, 2)) 
sage.symbolic.expression.Expression 
sage: %timeit log(8, 2) 
1000000 loops, best of 3: 1.4 us per loop 
sage: %timeit log(8r, 2) 
1000 loops, best of 3: 404 us per loop 

（rサフィックスが「生」を意味し、Integer(2)にリテラル2を包むからセイジプリパーサーを防止する）：退屈な理由のためセイジIntegerとは対照的に、まず、あなたは、Python intを使用してから余分なオーバーヘッドを取得します

そしてそれは変です。 rangeが消費するintを生成するために、Sageはlog(8)/log(2)を3にする方法を見つけなければならず、彼女は可能な限り最悪のことをしていることが分かります。私の元の診断を忠告します（準用する場合）：

まず、このオブジェクトがintを取得する独自の方法を持っているかどうかを確認します。そこで、彼女はlog（8）/ log（2）からRealIntervalオブジェクトを構築します。これは彼女ができる最悪の事であることが判明しました！彼女は、区間の下部と上部が一致するかどうかをチェックします（つまり、床が何であるかを確実に知るため）。しかし、この場合、実際には整数なので、！これはいつものように見えるように起こっている：

これら2つの境界がありませんセイジは、彼女がまだ問題を解決していないことを決定して、等しくない床を持っている、と彼女は20000に精度を増加し続け

sage: y = log(8)/log(2) 
sage: rif = RealIntervalField(53)(y) 
sage: rif 
3.000000000000000? 
sage: rif.endpoints() 
(2.99999999999999, 3.00000000000001) 

彼女は彼らが...であることを証明することができるかどうかを知るためにビットを見ていますが、建設によっては決して動かないでしょう。最後に、彼女はあきらめて、それを簡素化しようとすると、成功している：それは割り切れ例あまのじゃく財産の言葉なし

sage: y.simplify_full() 
3 

証明：

sage: %timeit range(log(8r, 2)) 
1 loops, best of 3: 2.18 s per loop 
sage: %timeit range(log(9r, 2)) 
1000 loops, best of 3: 766 us per loop 
sage: %timeit range(log(15r, 2)) 
1000 loops, best of 3: 764 us per loop 
sage: %timeit range(log(16r, 2)) 
1 loops, best of 3: 2.19 s per loop 

Answer 2

おそらくlog(x, 2)（別名ld()）を使用していることは、最初は良い考えではありません。私は実装するint型の値をシフト使用することを提案したいld()：

n = len(array) 
while n: 
    n >>= 1 
    # perform the loop stuff 

あなたはrange()とlog()と、これらすべてのuglinessesを避けるかもしれないこの方法です。

通常の状況では、log()を呼び出すには、intの単純なビットシフトよりも時間がかかります。例：nための差が小さくなる大きな値と

>>> timeit('for i in range(int(math.log(8, 2))): pass', setup='import math') 
0.6762251853942871 
>>> timeit('n = 8\nwhile n:\n n >>= 1') 
0.24107813835144043 

。 n = 10000の場合、私は0.8163230419158936と0.8106038570404053を得ましたが、これは、ループの初期化と比較して、ループ本体が大部分の時間を取るためです。

Answer 3

は、Python 2の範囲（some_float）を可能にするが、それは非推奨とPython 3

のサンプルコードは、指定された出力を与えないで動作しません。しかし、私たちはそれを歩くことができます。まず、完全なスクリプトを必要とはtimeit、はtimeitを呼び出すスクリプト内のインポートは使用されません。

>>> timeit('range(log(8,2))') 
    Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    File "/usr/lib64/python2.6/timeit.py", line 226, in timeit 
    return Timer(stmt, setup, timer).timeit(number) 
    File "/usr/lib64/python2.6/timeit.py", line 192, in timeit 
    timing = self.inner(it, self.timer) 
    File "<timeit-src>", line 6, in inner 
NameError: global name 'log' is not defined 

あなたがタイムアウトしているスクリプトにインポートを追加した場合、それはセットアップ時間が含まれています

>>> timeit('from math import log;range(log(8,2))') 
3.7010221481323242 

あなたはセットアップにインポートを移動する場合は、その優れたが、ワンショットのタイミングは、悪名高い不正確です：

>>> timeit('range(log(8,2))',setup='from math import log') 
1.9139349460601807 

最後に、時代の束にそれを実行し、あなたはかなりの数を取得：

を

>>> timeit('range(log(8,2))',setup='from math import log',number=100) 
0.00038290023803710938 

Answer 4

これはSageバグのようです。

私は新しいノートブックを作成し、これをした：

n = len([1,2,3,4,5,6,7,8]) 
k = 8 
timeit('range(log(n, 2))', number=2, repeat=3) # Test 1 
timeit('range(log(len([1,2,3,4,5,6,7,8]), 2))', number=2, repeat=3) # Test 1.5 
timeit('range(log(k, 2))', number=2, repeat=3) # Test 2 

テスト1.5は、テスト1と同じように遅いです。しかし、あなたはrangeをオフ任意のテイク方法でそれを打破する、あるいはm=n+0を追加した場合と、 nの代わりにmを使用すると、マイクロ秒に低下します。

明らかに、Sageは表現を評価して混乱する中で、ここで何か複雑なことをしようとしています。これを確認するには

---

、昔ながらのipythonで：

n = len([1,2,3,4,5,6,7,8]) 
k = 8 
%timeit 'range(log(n, 2))' 
%timeit 'range(log(len([1,2,3,4,5,6,7,8]), 2))' 
%timeit 'range(log(k, 2))' 

彼らはすべて、あなたが期待するように、均等に速いです。

---

だからあなたはどうしますか？

まあ、セージのバグを追跡し、上流にファイルしてみてください。しかし一方で、おそらくあなたのコードには回避策が必要です。

上記のように、m = n+0を実行し、nの代わりにmを使用するだけでスピードアップするようです。それがあなたのために働くかどうかを見ますか？