python3 - 파이썬 2 3 차이




Python 3에서 왜 "1000000000000000 in range(1000000000000001)"가 그렇게 빠릅니까? (6)

TL; DR

range() 의해 반환 된 객체는 실제로 range 객체입니다. 이 객체는 이터레이터 인터페이스를 구현하므로 생성기처럼 값을 순차적으로 반복 할 수 있지만 객체가 in 연산자의 오른쪽에 나타날 때 실제로 호출되는 __contains__ 인터페이스도 구현합니다. __contains__() 메서드는 항목이 객체에 있는지 여부에 대한 부울을 반환합니다. range 객체는 경계와 걸음을 알고 있으므로 O (1)에서 구현하기가 매우 쉽습니다.

실제로 파이썬 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의 답변 은 완전성으로 선정되었지만 Python 3에서 range 가 완전한 시퀀스 가되는 것이 무엇을 의미하는지에 대한 좋은 토론과 __contains__ 함수 최적화에 대한 잠재적 불일치에 관한 정보 / 경고에 대한 abarnert의 첫 번째 답변 을 참조하십시오. 파이썬 구현. abarnert의 다른 대답 은 좀 더 자세히 설명하고 Python 3의 최적화 뒤에 숨겨진 역사에 관심이있는 사람들을위한 링크를 제공합니다 (Python 2의 xrange 최적화 부족). poke 와 wim의 답변은 관심있는 사람들을위한 관련 C 소스 코드와 설명을 제공합니다.


Martijn의 답변에 추가하기 위해 이것은 소스 의 관련 부분입니다 (C에서 범위 객체가 원시 코드로 작성 됨).

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 객체 (Python 3에서는 int )의 경우 range_contains_long 함수를 사용하여 결과를 결정합니다. 그리고이 함수는 ob 가 지정된 범위에 있는지 확인합니다 (C에서는 조금 더 복잡해 보이지만).

int 객체가 아닌 경우 값을 찾을 때까지 반복으로 돌아갑니다.

전체 논리는 다음과 같이 의사 파이썬으로 변환 될 수 있습니다.

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 추가 최적화에 관한 것 range . 실제 사용하기 전까지 또는 추가 최적화로 인해 범위 내의 값을 계산할 필요가 없습니다.

그건 그렇고, 정수가 그렇게 크지 않습니다 sys.maxsize 고려 sys.maxsize

sys.maxsize in range(sys.maxsize) 는 매우 빠릅니다.

최적화로 인해-주어진 정수를 최소 및 최대 범위와 쉽게 비교할 수 있습니다.

그러나:

float(sys.maxsize) in range(sys.maxsize) 는 꽤 느립니다 .

(이 경우 range 최적화가 없으므로 파이썬이 예기치 않은 부동 소수점을 수신하면 파이썬은 모든 숫자를 비교합니다)

구현 세부 사항을 알고 있어야하지만 나중에 변경 될 수 있으므로 의존해서는 안됩니다.


다른 답변은 이미 잘 설명했지만 범위 객체의 특성을 보여주는 다른 실험을 제공하고 싶습니다.

>>> 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.__contains__ 에 추가 된 이유와 2.7의 xrange.__contains__ 에 추가 되지 않은 이유가 궁금한 경우 :

먼저 Ashwini Chaudhary가 발견 한대로 이슈 1766304 가 명시 적으로 개방되어 [x]range.__contains__ 최적화되었습니다. 이것에 대한 패치는 3.2에 대해 승인되고 체크인 되었지만 "xrange는 이렇게 늦게 패치를 커밋하기 위해 우리가 사는 것이 무엇인지 알지 못하는 정도로 오랫동안 이런 식으로 행동했기 때문에 2.7로 백 포트되지 않았습니다." (2.7은 그 시점에 거의 나갔다.)

그 동안에:

원래 xrange 는 quite-sequence 객체였습니다. 3.1 문서에서 말한 것처럼 :

범위 객체는 동작이 거의 없습니다. 인덱싱, 반복 및 len 함수 만 지원합니다.

이것은 사실이 아니었다. xrange 객체는 실제로 __contains__ (선형 검색을 통해)를 포함하여 인덱싱 및 len 과 함께 자동으로 제공되는 몇 가지 다른 기능을 지원했습니다. 그러나 당시에는 전체 시퀀스를 만들 가치가 있다고 생각한 사람은 아무도 없었습니다.

그런 다음 추상 기본 클래스 PEP를 구현하는 과정에서 어떤 내장 유형이 어떤 ABC를 구현하는 것으로 표시되어야하는지, xrange / range collections.Sequence 을 구현한다고 주장하는 것으로 파악해야 collections.Sequence . 작은 행동 ". 9213 호 까지는 그 문제를 눈치 채지 못했습니다 . 이 문제에 대한 패치는 indexcount 를 3.2의 range 에 추가했을뿐만 아니라 최적화 된 __contains__ ( index 와 동일한 수학을 공유하고 count 의해 직접 사용됨)를 재 작업했습니다. ** 이 변경 은 3.2에도 적용되었으며 "새로운 방법을 추가하는 버그 수정"이기 때문에 2.x로 백 포트되지 않았습니다. (이 시점에서 2.7은 이미 rc 상태를 지났습니다.)

따라서이 최적화를 2.7로 백 포트 할 수있는 두 가지 기회가 있었지만 둘 다 거부되었습니다.

실제로 len 과 indexing을 사용하여 무료로 반복을 얻을 수 있지만 2.3 xrange 객체에는 사용자 정의 반복자가 있습니다. 그런 다음 3.x에서 손실되었으며 list 와 동일한 listiterator 유형을 사용 list .

** 첫 번째 버전은 실제로이를 다시 구현하고 세부 정보가 잘못되었습니다. 예를 들어 MyIntSubclass(2) in range(5) == False . 그러나 Daniel Stutzbach의 업데이트 된 버전의 패치는 3.2 이전의 일반적인 느린 _PySequence_IterSearch 대한 폴백을 포함하여 이전 코드의 대부분을 복원했습니다 range.__contains__ 는 최적화가 적용되지 않을 때 암시 적으로 사용되었습니다.


source 사용하십시오, Luke!

CPython에서 range(...).__contains__ (메소드 래퍼)는 결국 값이 범위 내에 있는지 확인하는 간단한 계산에 위임합니다. 여기서 속도의 이유 는 range object의 직접 반복이 아닌 경계에 대한 수학적 추론을 사용 하기 때문 입니다. 사용 된 논리를 설명하려면 :

  1. 숫자가 startstop 사이에 있는지 확인하고
  2. 보폭이 우리의 숫자를 "스텝"하지 않는지 확인하십시오.

예를 들어, 994 range(4, 1000, 2) 입니다.

  1. 4 <= 994 < 1000
  2. (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 !를 사용하여 범위의 멍청한 반복 검색으로 돌아 _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)




python-internals