질문자 :Rick supports Monica
실제로 Python 3의 객체 유형인 range() 함수는 생성기와 유사하게 내용을 즉석에서 생성합니다.
이 경우 1,000조가 범위에 있는지 여부를 확인하려면 1,000조 값이 생성되어야 하기 때문에 다음 행에 과도한 시간이 소요될 것으로 예상했습니다.
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 가 본격적인 시퀀스 가 된다는 것이 무엇을 의미하는지에 대한 좋은 토론 __contains__ 함수 최적화에 대한 잠재적인 불일치에 관한 일부 정보/경고에 대한 abarnert의 첫 번째 답변도 참조하십시오. 파이썬 구현. 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 문제를 참조하세요.
* 파이썬 정수 N이 이것을 O하고, 성장함에 따라 연산 작업도 시간에 성장 있도록 작업 (N 로그)적이고 제한 때문에 근처 일정한 시간. 모두 최적화된 C 코드에서 실행되고 Python은 정수 값을 30비트 청크로 저장하므로 여기에 관련된 정수의 크기로 인한 성능 영향을 보기 전에 메모리가 부족할 것입니다.
여기서 근본적인 오해는 range 가 발전기라고 생각하는 것입니다. 그렇지 않다. 사실, 그것은 어떤 종류의 반복자가 아닙니다.
이것을 아주 쉽게 말할 수 있습니다.
>>> a = range(5) >>> print(list(a)) [0, 1, 2, 3, 4] >>> print(list(a)) [0, 1, 2, 3, 4]
그것이 제너레이터라면 한 번 반복하면 소진됩니다.
>>> b = my_crappy_range(5) >>> print(list(b)) [0, 1, 2, 3, 4] >>> print(list(b)) []
range 는 목록과 같은 시퀀스입니다. 다음을 테스트할 수도 있습니다.
>>> import collections.abc >>> isinstance(a, collections.abc.Sequence) True
이는 시퀀스가 되는 모든 규칙을 따라야 함을 의미합니다.
>>> a[3] # indexable 3 >>> len(a) # sized 5 >>> 3 in a # membership True >>> reversed(a) # reversible <range_iterator at 0x101cd2360> >>> a.index(3) # implements 'index' 3 >>> a.count(3) # implements 'count' 1
range 와 list 의 차이점은 range 가 지연 또는 동적 시퀀스라는 것입니다. 모든 값을 기억하지 않고 start , stop 및 step __getitem__ 에서 요청 시 값을 생성합니다.
(보조 노트로서, 당신은 경우 print(iter(a)) , 당신이 알 수 range 동일한 사용 listiterator 같은 유형의 list . 그 일이? Â 않는 방법 listiterator 에 대해 아무것도 특수를 사용하지 않는 list 사실 그 제외 __getitem__ 의 C 구현을 제공 range 에서도 잘 작동합니다.)
Sequence.__contains__ 가 상수 시간이어야 한다고 말하는 것은 없습니다 list 와 같은 시퀀스의 명백한 예에서는 그렇지 않습니다. 하지만 안 된다고 하는 것은 없습니다. 그리고 그것을 구현하기 쉽게 range.__contains__ 단지 그것을 확인하려면 수학적으로 ( (val - start) % step 지만, 부정적인 단계를 다루는 몇 가지 추가 복잡성을) 실제로보다는 생성하고 모든 값을 테스트, 그래서 왜하지 말아야 더 나은 방법입니까?
그러나 이것이 일어날 것이라고 보장 하는 언어는 없는 것 같습니다. Ashwini Chaudhari가 지적했듯이 정수로 변환하고 수학적 테스트를 수행하는 대신 정수가 아닌 값을 제공하면 모든 값을 반복하고 하나씩 비교하는 방식으로 대체됩니다. 그리고 CPython 3.2+ 및 PyPy 3.x 버전에 이러한 최적화가 포함되어 있고 이는 분명 좋은 아이디어이고 수행하기 쉽기 때문에 IronPython 또는 NewKickAssPython 3.x가 이를 제외하지 않을 이유가 없습니다. (사실 CPython 3.0-3.1에는 포함 되지 않았습니다.)
range my_crappy_range 와 같은 생성기 __contains__ 이 방법으로 __contains__ 를 테스트하는 것이 이치에 맞지 않거나 적어도 이치에 맞는 방식이 명확하지 않을 것입니다. 이미 처음 3 개 값을 반복하려는 경우이며, 1 여전히 in 발전기? 1 대한 테스트로 1 (또는 첫 번째 값 >= 1 )까지 모든 값을 반복하고 소비해야 합니까?
출처를 사용하세요, 루크!
CPython에서 range(...).__contains__ (메소드 래퍼)는 결국 값이 범위 내에 있을 수 있는지 확인하는 간단한 계산에 위임합니다. 여기서 속도가 나는 이유는 범위 객체의 직접적인 반복이 아니라 경계에 대한 수학적 추론을 사용하기 때문입니다. 사용된 논리를 설명하려면:
-
start 와 stop 사이에 있는지 확인하고 - 보폭 값이 숫자를 "넘어가지" 않는지 확인하십시오.
예를 들어, 994 는 다음과 같은 이유로 range(4, 1000, 2)
-
4 <= 994 < 1000 , -
(994 - 4) % 2 == 0 .
전체 C 코드가 아래에 포함되어 있습니다. 메모리 관리 및 참조 카운팅 세부 정보 때문에 좀 더 장황하지만 기본 아이디어는 다음과 같습니다.
static int range_contains_long(rangeobject *r, PyObject *ob) { int cmp1, cmp2, cmp3; PyObject *tmp1 = NULL; PyObject *tmp2 = NULL; PyObject *zero = NULL; int result = -1; zero = PyLong_FromLong(0); if (zero == NULL) /* MemoryError in int(0) */ goto end; /* Check if the value can possibly be in the range. */ cmp1 = PyObject_RichCompareBool(r->step, zero, Py_GT); if (cmp1 == -1) goto end; if (cmp1 == 1) { /* positive steps: start <= ob < stop */ cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE); cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT); } else { /* negative steps: stop < ob <= start */ cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE); cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT); } if (cmp2 == -1 || cmp3 == -1) /* TypeError */ goto end; if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */ result = 0; goto end; } /* Check that the stride does not invalidate ob's membership. */ tmp1 = PyNumber_Subtract(ob, r->start); if (tmp1 == NULL) goto end; tmp2 = PyNumber_Remainder(tmp1, r->step); if (tmp2 == NULL) goto end; /* result = ((int(ob) - start) % step) == 0 */ result = PyObject_RichCompareBool(tmp2, zero, Py_EQ); end: Py_XDECREF(tmp1); Py_XDECREF(tmp2); Py_XDECREF(zero); return result; } static int range_contains(rangeobject *r, PyObject *ob) { if (PyLong_CheckExact(ob) || PyBool_Check(ob)) return range_contains_long(r, ob); return (int)_PySequence_IterSearch((PyObject*)r, ob, PY_ITERSEARCH_CONTAINS); }
아이디어의 "고기"는 다음 줄에 언급되어 있습니다.
/* result = ((int(ob) - start) % step) == 0 */
마지막으로 코드 스니펫 하단의 range_contains 정확한 유형 검사가 실패하면 설명된 영리한 알고리즘을 사용하지 않고 대신 _PySequence_IterSearch 사용하여 범위의 멍청한 반복 검색으로 대체합니다! 인터프리터에서 이 동작을 확인할 수 있습니다(여기서 v3.5.0을 사용하고 있습니다).
>>> x, r = 1000000000000000, range(1000000000000001) >>> class MyInt(int): ... pass ... >>> x_ = MyInt(x) >>> x in r # calculates immediately :) True >>> x_ in r # iterates for ages.. :( ^\Quit (core dumped)
Martijn의 답변에 추가하려면 이것은 소스 의 관련 부분입니다(C에서는 range 객체가 네이티브 코드로 작성되기 때문에).
static int range_contains(rangeobject *r, PyObject *ob) { if (PyLong_CheckExact(ob) || PyBool_Check(ob)) return range_contains_long(r, ob); return (int)_PySequence_IterSearch((PyObject*)r, ob, PY_ITERSEARCH_CONTAINS); }
따라서 PyLong 객체( int 임)의 경우 range_contains_long 함수를 사용하여 결과를 결정합니다. 그리고 그 함수는 본질적으로 ob 가 지정된 범위에 있는지 확인합니다(C에서는 조금 더 복잡해 보이지만).
int 객체가 아니면 값을 찾을 때까지(또는 찾지 않을 때까지) 반복합니다.
전체 논리는 다음과 같이 의사 Python으로 변환될 수 있습니다.
def range_contains (rangeObj, obj): if isinstance(obj, int): return range_contains_long(rangeObj, obj) # default logic by iterating return any(obj == x for x in rangeObj) def range_contains_long (r, num): if r.step > 0: # positive step: r.start <= num < r.stop cmp2 = r.start <= num cmp3 = num < r.stop else: # negative step: r.start >= num > r.stop cmp2 = num <= r.start cmp3 = r.stop < num # outside of the range boundaries if not cmp2 or not cmp3: return False # num must be on a valid step inside the boundaries return (num - r.start) % r.step == 0
이 최적화가 추가 된 이유를 궁금해하는 경우 range.__contains__ , 그리고 왜이 추가되지 않은 xrange.__contains__ 2.7 :
먼저 Ashwini Chaudhary가 발견한 것처럼 [x]range.__contains__ 를 최적화하기 위해 문제 1766304 가 명시적으로 공개되었습니다. 이에 대한 패치가 3.2에 대해 승인 및 체크인 되었지만 2.7로 백포팅되지 않았습니다. " xrange 가 너무 오랫동안 이와 같이 동작하여 늦게까지 패치를 커밋하는 데 무엇이 도움이 되는지 알 수 없기 때문입니다." (2.7은 그 시점에서 거의 끝났습니다.)
그 동안에:
원래 xrange 는 순차 객체가 아니었습니다. 3.1 문서에서 다음과 같이 말합니다.
Range 개체는 동작이 거의 없습니다. 인덱싱, 반복 및 len 함수만 지원합니다.
이것은 사실이 아니었습니다. xrange __contains__ (선형 검색을 통해)를 포함하여 * len 과 함께 자동으로 제공되는 몇 가지 다른 것들을 지원했습니다. 그러나 그 당시에는 아무도 그것들을 완전한 시퀀스로 만들 가치가 있다고 생각하지 않았습니다.
그런 다음, 구현의 일환으로 추상 기본 클래스 PEP를, 그것은 내장 유형이있는 상식 및 구현으로 표시되어야하는 알아낼 중요 xrange / range 구현하는 주장 collections.Sequence 가 여전히 "같은 매우 처리에도 불구하고, 작은 행동" 문제 9213 까지 아무도 그 문제를 알아차리지 못했습니다. 해당 문제에 대한 패치는 index 와 count 를 3.2의 range 에 추가했을 뿐만 아니라 최적화된 __contains__ index 와 동일한 수학을 공유하고 count 직접 사용됨). ** 이 변경 사항 은 3.2에도 적용되었으며 "새 메서드를 추가하는 버그 수정"이기 때문에 2.x로 백포트되지 않았습니다. (이 시점에서 2.7은 이미 rc 상태를 벗어났습니다.)
따라서 이 최적화를 2.7로 백포트할 기회가 두 번 있었지만 둘 다 거부되었습니다.
* 사실, 인덱싱만으로도 무료로 이터레이션을 얻을 수 있지만 2.3에서는 xrange 객체에 커스텀 이터레이터가 있습니다.
** 첫 번째 버전은 실제로 이를 다시 구현했지만 세부 정보가 잘못되었습니다. 예를 들어 MyIntSubclass(2) in range(5) == False 제공합니다. 그러나 Daniel Stutzbach의 업데이트된 버전의 패치는 최적화가 적용되지 않을 때 3.2 이전 range.__contains__ _PySequence_IterSearch 대체를 포함하여 이전 코드의 대부분을 복원했습니다.
다른 답변은 이미 잘 설명했지만 범위 객체의 특성을 보여주는 또 다른 실험을 제안하고 싶습니다.
>>> r = range(5) >>> for i in r: print(i, 2 in r, list(r)) 0 True [0, 1, 2, 3, 4] 1 True [0, 1, 2, 3, 4] 2 True [0, 1, 2, 3, 4] 3 True [0, 1, 2, 3, 4] 4 True [0, 1, 2, 3, 4]
보시다시피 range 객체는 범위를 기억하고 일회성 생성기가 아니라 여러 번(반복하는 동안에도) 사용할 수 있는 객체입니다.
평가에 대한 게으른 접근 방식 range 추가 최적화에 관한 것입니다. 범위의 값은 실제 사용할 때까지 또는 추가 최적화로 인해 더 이상 계산할 필요가 없습니다.
그건 그렇고, 당신의 정수는 그렇게 크지 않습니다. sys.maxsize
sys.maxsize in range(sys.maxsize) 는 꽤 빠릅니다.
최적화로 인해 - 주어진 정수를 범위의 최소값과 최대값으로 쉽게 비교할 수 있습니다.
하지만:
Decimal(sys.maxsize) in range(sys.maxsize) 은 꽤 느립니다 .
(이 경우 range 최적화가 없으므로 파이썬이 예기치 않은 Decimal을 받으면 파이썬은 모든 숫자를 비교합니다)
구현 세부 사항을 알고 있어야 하지만 나중에 변경될 수 있으므로 이에 의존해서는 안 됩니다.
TL;DR
range() 의해 반환된 객체는 실제로 range 객체입니다. 이 객체는 반복자 인터페이스를 구현하므로 생성기, 목록 또는 튜플과 마찬가지로 해당 값을 순차적으로 반복할 수 있습니다.
그러나 그것은 또한 in 연산자의 오른쪽에 나타날 때 실제로 호출되는 __contains__ 인터페이스를 구현합니다. __contains__() 메소드는 반환 bool 의 좌측에 있는지 여부를 항목 in 오브젝트이다. range 객체는 경계와 보폭을 알고 있으므로 O(1)에서 구현하기가 매우 쉽습니다.
- 최적화로 인해 주어진 정수를 최소 및 최대 범위로 비교하는 것은 매우 쉽습니다.
- range() 함수가 Python3에서 매우 빠른 이유는 여기에서 범위 객체의 직접적인 반복보다는 경계에 대한 수학적 추론을 사용하기 때문입니다.
- 여기에서 논리를 설명하기 위해:
- 번호가 시작과 중지 사이에 있는지 확인하십시오.
- 단계 정밀도 값이 우리의 숫자를 초과하지 않는지 확인하십시오.
예를 들어 997은 다음과 같은 이유로 범위(4, 1000, 3)에 있습니다.
4 <= 997 < 1000, and (997 - 4) % 3 == 0.
큰 x x-1 in (i for i in range(x)) 를 시도하십시오 range.__contains__ 최적화 호출을 피하기 위해 생성기 이해를 사용합니다.
TLDR; range 는 산술 계열이므로 개체가 있는지 여부를 매우 쉽게 계산할 수 있습니다. 목록이 정말 빨리 같은 경우 색인을 얻을 수도 있습니다.
출처 : http:www.stackoverflow.com/questions/30081275/why-is-1000000000000000-in-range1000000000000001-so-fast-in-python-3