☰

Python 3 ではなぜ「100000000000000000 in range(10000000000000001)」がこんなに速いのでしょうか? 質問する

tag-icon • tag-icon python performance python-3.x range python-internals
Python 3 ではなぜ「100000000000000000 in range(10000000000000001)」がこんなに速いのでしょうか? 質問する

私の理解ではrange()、その機能は実際にはPython 3のオブジェクト型は、ジェネレーターと同様に、その内容を即座に生成します。

このような場合、1 兆が範囲内にあるかどうかを判断するには、1 兆個の値を生成する必要があるため、次の行には非常に長い時間がかかることが予想されます。

1_000_000_000_000_000 in range(1_000_000_000_000_001)

さらに、ゼロをいくつ追加しても、計算にかかる時間はほぼ同じ (基本的には瞬時) ようです。

次のようなことも試してみましたが、計算はほぼ瞬時に完了します。

# count by tens
1_000_000_000_000_000_000_000 in range(0,1_000_000_000_000_000_000_001,10)

独自の範囲関数を実装しようとすると、結果はあまり良くありません。

def my_crappy_range(N):
    i = 0
    while i < N:
        yield i
        i += 1
    return

range()オブジェクトが内部で何をして、これほど高速化しているのでしょうか?

マルティン・ピータースの回答完全性のために選ばれましたが、abarnertの最初の回答Python 3 で がrange完全なシーケンスであるということの意味についての詳しい説明と、 __contains__Python 実装間での関数の最適化の潜在的な不一致に関する情報/警告があります。abarnert の他の回答xrangePython 3 の最適化の歴史 (およびPython 2の最適化の欠如) に興味のある人のために、さらに詳しく説明し、リンクを提供しています。回答ポケそしてウィム興味のある人のために、関連する C ソース コードと説明を提供します。

ベストアンサー1

Python 3range()オブジェクトはすぐに数値を生成するのではなく、スマートなシーケンスオブジェクト要求に応じて数値を生成します。開始値、停止値、ステップ値のみが含まれており、オブジェクトを反復処理すると、反復ごとに次の整数が計算されます。

このオブジェクトは、object.__contains__針、そして、その数値がその範囲内にあるかどうかを計算します。計算は（ほぼ）一定時間の処理です*。範囲内の可能なすべての整数をスキャンする必要はありません。

からrange()オブジェクトのドキュメント:

range型が通常のlistやよりも優れている点はtuple、範囲オブジェクトは、それが表す範囲のサイズに関係なく、常に同じ（小さな）量のメモリを使用することです（ 、 、 値のみを格納しstart、必要にstop応じstepて個々の項目とサブ範囲を計算するため）。

したがって、オブジェクトは少なくともrange()次のことを実行します。

class my_range:
    def __init__(self, start, stop=None, step=1, /):
        if stop is None:
            start, stop = 0, start
        self.start, self.stop, self.step = start, stop, step
        if step < 0:
            lo, hi, step = stop, start, -step
        else:
            lo, hi = start, stop
        self.length = 0 if lo > hi else ((hi - lo - 1) // step) + 1

    def __iter__(self):
        current = self.start
        if self.step < 0:
            while current > self.stop:
                yield current
                current += self.step
        else:
            while current < self.stop:
                yield current
                current += self.step

    def __len__(self):
        return self.length

    def __getitem__(self, i):
        if i < 0:
            i += self.length
        if 0 <= i < self.length:
            return self.start + i * self.step
        raise IndexError('my_range object index out of range')

    def __contains__(self, num):
        if self.step < 0:
            if not (self.stop < num <= self.start):
                return False
        else:
            if not (self.start <= num < self.stop):
                return False
        return (num - self.start) % self.step == 0

これには、実数がrange()サポートするいくつかの機能 (またはメソッド、ハッシュ、等価性テスト、スライスなど) がまだ欠けていますが、概要.index()は.count()わかるはずです。

また、__contains__実装を簡素化して整数テストのみに焦点を当てました。実range()オブジェクトに非整数値（のサブクラスを含むint）を与えると、すべての値のリストに対して包含テストを使用するのと同じように、一致するものがあるかどうかを確認するために低速スキャンが開始されます。これは、たまたま整数との等価性テストをサポートしているが、整数演算もサポートするとは期待されていない他の数値型を引き続きサポートするために行われました。元のPythonの問題封じ込めテストを実施した。

* Python の整数は無制限であるため、N が大きくなるにつれて数学演算の時間も長くなり、これは O(log N) 演算になるため、ほぼ一定時間です。すべて最適化された C コードで実行され、Python は整数値を 30 ビットのチャンクに格納するため、ここで関係する整数のサイズが原因でパフォーマンスへの影響が現れる前にメモリが不足します。

おすすめ記事