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

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

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