Python3 で range(1000000000000001) の 1000000000000000 が速いのはなぜですか

Python では、 range(1000000000000001) の式 1000000000000000 はどのくらい速く実行できますか?

要素 x が true を返すかどうかを判断する最も単純かつ大雑把な方法、その時間計算量は O(n)、ハッシュ アルゴリズムを使用する理論的な時間計算量は O( 1)、二分探索の時間計算量が O(log n) の場合、Python は何を使用しますか?これを達成するためにどのアルゴリズムが使用されますか?

最初に実験してみましょう:

#python2
timeit.timeit('1000000000 in range(0,1000000000,10)', number=1)
5.50357640805305
timeit.timeit('1000000000 in xrange(0,1000000000,10)', number=1)
2.3025200839183526
# python3
import timeit
timeit.timeit('1000000000 in range(0,1000000000,10)', number=1)
4.490355838248402e-06

Python2 の range 関数がリスト オブジェクトを返し、すべての要素を一度にメモリにロードすることは誰もが知っているので、最初の式を実行します。システムが突然非常に固まったように感じられ、5 秒以上かかります。

xrange は Python3 の range 関数に似ており、どちらもイテレータ オブジェクトを返しますが、実行結果は驚くべきことに大きく異なります。 3 番目の式にはほぼ 0 秒かかりますが、Python2 の xrange と Python3 の range 関数の間にこれほど大きな違いがあるのはなぜですか?この謎を理解するには、in 操作がどのように実行されるかを理解する必要があります。次の Python ドキュメントのルールに従います。

クラスが contains() メソッドを実装している場合、y.contains(x) が true を返す限り、y の x も true を返し、その逆も同様です。

contains() メソッドは実装されていませんが、iter() メソッドは実装されています。その後、反復プロセス中に、特定の値 z==x がある場合は true を返し、それ以外の場合は true を返します。間違い。

上記の 2 つのメソッドのどちらも実装されていない場合は、getitem() メソッドを確認してください。x==y[i] のようなインデックス i がある場合は true を返し、それ以外の場合は false を返します。

in のルールを理解した後、まず xrange が提供するメソッドを見てみましょう:

dir(xrange)
['__class__','__getitem__', '__hash__', '__init__', 
'__iter__', '__len__', '__new__', ...]

はい、xrange 関数は getitem と iter を実装して、x が y に必要かどうかを判断するだけです。比較は値ごとに繰り返し実行されます。これは、xrange の時間計算量が O(n) であることを意味します。

Python3 の range メソッドを見てみましょう:

 dir(range)
['__class__', '__contains__', '__getitem__', '__iter__',  
'count', 'index', 'start', 'step', 'stop', ...]

Range は、xrange よりも多くの属性を提供します。getitem と iter を実装するだけでなく、contains も実装するため、呼び出されます。最初にメソッドが含まれており、さらに、start、stop、step の 3 つの属性も提供されます。では、なぜこれほど高速に実行されるのでしょうか? contains メソッドがどのように実装されるかを見てみましょう。

Python3 では、contains は値を 1 つずつ反復して比較するのではなく、次のようなロジックを採用しています。

まず、x が開始と停止の間にあるかどうかを確認します。範囲: start <= x < stop

この間隔内にある場合は、ステップに従って x が xrange 間隔内の特定の値に該当するかどうかを計算します。ここではモジュロ法を使用して決定します。 : - start) % step == 0

真実はこの時点で明らかになります。xrange の時間計算量は O(1)、つまり、xrange(start の stop 値がどんなに大きくても) です。 、停止、ステップ）は、時間計算量はすべて定数です。したがって、Python3 の range メソッドはメモリを節約できるだけでなく、より効率的に実行できるため、Python2 を学習するか Python3 を学習するかについて心配する必要はありません。

以上がPython3 で range(1000000000000001) の 1000000000000000 が速いのはなぜですかの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。