[解決済み] Python 3で「1000000000000000 in range(1000000000000001)」はなぜ速いのですか？

疑問点

私の理解では range() 関数は、実際には Python 3 のオブジェクト型 で、ジェネレータのようにその場で内容を生成します。

というのも、1,000兆が範囲内かどうかを判断するためには、1,000兆個の値を生成しなければならないからだ。

1_000_000_000_000_000 in range(1_000_000_000_000_001)

さらに：0をいくつ付けても、多かれ少なかれ計算には同じ時間がかかるようです（基本的に瞬時）。

なども試しましたが、やはり計算はほぼ一瞬です。

# 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() オブジェクトはどのように高速化されているのでしょうか？

Martijn Pietersの回答 を選んだのは、その完成度の高さによるものですが、他にも abarnertの最初の回答 にとってどういう意味があるのか、よく議論されています。 range にすることで、本格的な シーケンス の潜在的な不整合に関するいくつかの情報と警告が表示されます。 __contains__ 関数の最適化は、Python の実装の違いで異なります。 abarnertさんの他の回答 は、Python 3 での最適化の背後にある歴史に興味がある人のために、もう少し詳細な説明とリンクを提供しています。 xrange Python 2 の場合)。回答 pokeで と ウィムによる は、関連するC言語のソースコードと解説を提供していますので、興味のある方はご覧ください。

解決方法は？

Python 3 range() オブジェクトはすぐに数字を生成するわけではありません。 シーケンスオブジェクト 数字を生成する オンデマンド . このオブジェクトには、開始、停止、ステップの値だけが含まれており、オブジェクトを反復するたびに、次の整数が計算されます。

また、このオブジェクトは 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ビット単位で保存するので、ここで扱う整数の大きさによるパフォーマンスの影響を見る前に、メモリを使い果たしてしまうでしょう。