Python 3에서“1000000000000000 in range (1000000000000001)”가 빠른 이유

질문 : Python 3에서“1000000000000000 in range (1000000000000001)”가 왜 그렇게 빠른가요?

---

실제로 Python 3의 객체 유형 인 range() 함수는 생성기와 유사하게 즉시 내용을 생성한다는 것을 이해합니다.

이 경우 1 천조가 범위 내에 있는지 확인하려면 1 천조 개의 값을 생성해야하므로 다음 줄에 과도한 시간이 걸릴 것으로 예상했을 것입니다.

1000000000000000 in range(1000000000000001)

게다가, 내가 얼마나 많은 0을 더 했든간에 계산은 거의 같은 시간 (기본적으로 순간적)이 걸리는 것 같습니다.

나는 또한 이와 같은 것을 시도했지만 계산은 여전히 거의 즉각적입니다.

1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens

내 자신의 범위 함수를 구현하려고하면 결과가 좋지 않습니다 !!

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

range() 객체가 그렇게 빠르게 만드는 후드 아래에서 수행하는 작업은 무엇입니까?

Martijn Pieters의 답변 은 완전성을 위해 선택되었지만 range 가 Python 3에서 본격적인 시퀀스 라는 것이 무엇을 의미하는지에 대한 좋은 토론 __contains__ 함수 최적화에 대한 잠재적 인 불일치에 관한 몇 가지 정보 / 경고에 대한 abarnert의 첫 번째 답변을 참조하십시오. Python 구현. abarnert의 다른 답변 은 좀 더 자세히 설명하고 Python 3의 최적화 (및 Python 2 xrange 최적화 부족)의 역사에 관심이있는 사람들을위한 링크를 제공합니다. poke 및 wim 별 답변은 관심있는 사람들에게 관련 C 소스 코드와 설명을 제공합니다.

답변

---

Python 3 range() 객체는 즉시 숫자를 생성하지 않습니다. 요청시 숫자를 생성하는 스마트 시퀀스 개체 입니다. 여기에 포함 된 것은 시작, 중지 및 단계 값뿐입니다. 객체를 반복 할 때마다 다음 정수가 계산됩니다.

객체는 또한 object.__contains__ hook을 구현하고 숫자가 범위의 일부인지 계산합니다. 계산은 (거의) 일정 시간 연산입니다 ^* . 범위에서 가능한 모든 정수를 스캔 할 필요가 없습니다.

range() 객체 문서에서 :

일반 list 또는 tuple range 유형의 장점은 범위 개체가 나타내는 범위의 크기에 관계없이 항상 동일한 (작은) 메모리를 사용한다는 것입니다 ( 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 비트 청크에 저장하므로 여기에 포함 된 정수의 크기로 인해 성능에 영향을 미치기 전에 메모리가 부족합니다.

출처 : https://stackoverflow.com/questions/30081275/why-is-1000000000000000-in-range1000000000000001-so-fast-in-python-3