"1000000000000000 in range(1000000000000001)"가 파이썬 3에서 왜 이렇게 빠른가요?

내 이해에 따르면, 실제로는 an object type in Python 3 인 range() 함수는 생성기와 비슷하게 즉석에서 콘텐츠를 생성합니다.

이 경우를 고려하면, 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

의자 아래에 있는 물건이 그렇게 빠르게 작동하는지 뭐가 그 아래에 있는 건가요?

Martijn Pieters's answer는 완성도 때문에 선택되었지만, abarnert's first answer은 Python 3에서 완전한 순서열이 무엇을 의미하는지에 대한 좋은 논의와 함께, Python 구현 전체에서 함수 최적화의 잠재적인 불일치에 대한 정보/경고를 제공하기 위해 볼만합니다. abarnert's other answer은 Python 3에서 최적화의 역사와 Python 2에서 xrange의 최적화 부재에 관심 있는 사람들을 위해 자세한 설명과 링크를 제공합니다. 답변 by poke와#$^@&#^$&는 관심 있는 사람들을 위해 해당 C 소스 코드와 설명을 제공합니다.

답변 1

Python 3 range() 객체는 즉시 숫자를 생성하지 않습니다. 그것은 필요할 때 숫자를 생성하는 똑똑한 sequence object입니다. 그 안에 담긴 것은 시작, 중지 및 단계 값뿐이며, 객체를 반복하면 각 반복마다 다음 정수가 계산됩니다.

이 객체는 또한 object.__contains__ hook 를 구현하고, 당신의 숫자가 그 범위에 속하는지 계산합니다. 계산은 (근사) 상수 시간 작업입니다 * . 범위 내 모든 가능한 정수를 스캔할 필요가 없습니다.

range() object documentation로부터:

일반적인 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() 메소드, 해싱, 동등성 테스트 또는 슬라이싱)가 누락되어 있지만, 이것이 당신에게 아이디어를 줄 것입니다.

나는 또한 # $&@$! #! $ & 구현을 정수 테스트에만 집중하도록 단순화했습니다. 실제 # $ * # & # ^^ $ & 객체에 정수 값 이외의 값을 제공하면 (# $$ ^ $ * @ $ & 및 그 하위 클래스 포함), 모든 포함된 값의 목록에 대한 포함 테스트를 사용하는 것과 같이 일치 여부를 확인하기 위해 느린 스캔이 시작됩니다. 이것은 정수 산술을 지원하지만 정수 평등 검사만 지원하는 다른 숫자 형식을 계속 지원하기 위해 수행되었습니다. 포함 테스트를 구현한 원래 #$ *^!!$@$&을 참조하십시오.

* Python 정수가 무제한이므로 수학 연산도 N이 커짐에 따라 시간이 증가하여 거의 일정한 시간이 소요되므로 이는 O(log N) 작업입니다. 모두 최적화된 C 코드에서 실행되며 Python은 정수 값을 30 비트 청크에 저장하므로 여기에 관련된 정수 크기 때문에 성능에 영향을 미치기 전에 메모리가 부족해질 것입니다.

답변 2

파이썬에서 1000000000000000 in range(1000000000000001) 구문이 왜 빠를까요?

파이썬에서는 매우 큰 정수값 역시 연산이 가능합니다. 이는 파이썬이 정수 형태를 나타내는 방식으로, 내부적으로 범위 계산 방식을 사용하기 때문입니다. 그러나 이는 또한 시스템 리소스에 따라서 엄청나게 많은 메모리를 필요로하게 됩니다.

그렇다면, 1000000000000000 in range(1000000000000001) 구문이 어떻게 이렇게 빨리 처리될까요? 이는 파이썬 내부에서 지원하는 lazy evaluation(지연 평가)라는 방식 때문입니다. 이 방식은 range() 함수의 결과를 루프를 도는 동안 한 번에 평가하지 않고, 필요할 때만 평가하여 처리할 수 있도록 합니다.

그렇기 때문에 range() 함수는 매우 큰 범위를 구할 때에도, 메모리 문제 없이 빠르게 처리할 수 있게 됩니다. 파이썬 개발자들은 이러한 지연 평가 방식을 적극적으로 활용하며, 파이썬 실행 속도를 높일 수 있도록 노력하고 있습니다.

따라서, 1000000000000000 in range(1000000000000001) 구문이 빠른 이유는 파이썬 내부에서 range() 함수의 지연 평가를 활용하여 처리하기 때문입니다. 이를 통해 매우 큰 범위를 가지는 연산도 손쉽게 처리할 수 있으며, 파이썬 개발자들은 이러한 방식을 통해 사용자들에게 편리하고 빠른 서비스를 제공하고 있습니다.