Python3에서 범위(1000000000000001)의 1000000000000000이 왜 그렇게 빠른가요?

범위(1000000000000001) 내의 1000000000000000 표현식을 Python에서 얼마나 빨리 실행할 수 있나요?

요소인지 여부를 결정하는 가장 간단하고 조악한 방법은 O(n)입니다. 해시 알고리즘을 사용하는 이론적 시간 복잡도는 O(1)입니다. 그렇다면 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의 범위 함수가 모든 요소를 ​​메모리에 한 번에 로드하는 목록 객체를 반환한다는 것을 알고 있습니다. 따라서 첫 번째 표현식이 실행되면 시스템이 갑자기 매우 느린 느낌을 받게 됩니다. , 5초 이상 소요됩니다.

xrange는 python3의 range 함수와 비슷합니다. 둘 다 반복자 객체를 반환하지만 실행 결과가 매우 다르기 때문에 놀랍습니다. 세 번째 표현식은 거의 0초가 걸립니다. python2의 xrange와 python3의 range 함수 사이에 왜 그렇게 큰 차이가 있습니까? 미스터리를 이해하기 위해서는 그 작업이 어떻게 수행되는지 이해해야 합니다. Python 문서의 in 규칙에 따르면:

클래스가 contain() 메서드를 구현하는 경우 y.contains(x)가 true를 반환하는 한 y의 x도 true를 반환하고 그 반대의 경우도 마찬가지입니다.

contains() 메소드는 구현되지 않았지만 iter() 메소드는 구현되었습니다. 그런 다음 반복 프로세스 중에 특정 값 z==x가 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

위 두 메서드 중 어느 것도 구현되지 않은 경우 getitem() 메서드를 살펴보세요. x==y[i]와 같은 인덱스 i가 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

in의 규칙을 이해한 후 먼저 xrange가 제공하는 메서드를 살펴보겠습니다.

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

예, xrange 함수는 x가 y에 있는지 확인하기 위해 getitem과 iter만 구현합니다. 비교를 위한 것, 즉 xrange의 시간 복잡도가 O(n)이라고 가정해 보겠습니다.

python3의 range 메서드를 살펴보겠습니다.

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

range는 xrange보다 더 많은 속성을 제공할 뿐만 아니라 포함도 구현하므로 포함 메서드를 먼저 호출합니다. 또한 세 가지 속성인 시작, 중지, 단계를 제공합니다. 그렇다면 정확히 왜 그렇게 빨리 실행되는 걸까요? Contains 메소드가 어떻게 구현되는지 살펴보겠습니다.

Python3에서는 값을 하나씩 반복적으로 비교하지 않고 다음과 같은 논리를 사용합니다.

먼저 x가 시작 범위와 중지 범위 사이에 있는지 확인합니다. start <= x < 이 간격 범위는 x가 단계를 기반으로 xrange 간격의 특정 값에 속하는지 여부를 계산합니다. 여기서는 모듈로 방법을 사용하여 판단합니다. (x - 시작) % 단계 == 0

이에서 진실이 드러납니다. moment, xrange 시간 복잡도는 O(1)입니다. 즉, xrange(start, stop, step)의 중지 값이 아무리 크더라도 시간 복잡도는 일정합니다. 따라서 python3의 range 메소드는 메모리를 절약할 수 있을 뿐만 아니라 더 효율적으로 수행할 수 있으므로 Python2를 배울지, Python3을 배울지 고민하지 마세요.

위 내용은 Python3에서 범위(1000000000000001)의 1000000000000000이 왜 그렇게 빠른가요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!