왜 "1000000000000000 in range (1000000000000001)"가 Python 3에서 그렇게 빠른가요?



Answers

근본적인 오해는 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

rangelist 의 차이는 range지연 또는 동적 순서라는 것입니다. 모든 값을 기억하지 못하고 start , stopstep 기억하고 __getitem__ 에서 필요에 따라 값을 만듭니다.

(참고로, print(iter(a))print(iter(a)) 하면 rangelistiterator 유형과 동일한 listiterator 유형을 사용한다는 것을 알게 될 것입니다. 어떻게 작동합니까? listiteratorlist 특별한 것을 사용하지 않습니다. __getitem__ 의 C 구현을 제공하므로 range 에도 문제가 없습니다.

이제는 Sequence.__contains__ 가 일정한 시간을 Sequence.__contains__ 한다는 사실은 아무것도 없습니다. 실제로 list 와 같은 시퀀스의 명백한 예를 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__ 방법으로 테스트하는 것이 의미가 없거나 적어도 이해가가는 방식은 분명하지 않습니다. 이미 처음 세 개의 값을 반복했다면 1 여전히 제네레이터에 있습니까? 1 테스트하면 모든 값이 최대 1 (또는 첫 번째 값 >= 1 )까지 반복되고 소비됩니다.

Question

실제로 Python 3에서 객체 유형 인 range() 함수는 생성기와 마찬가지로 즉석에서 내용을 생성한다는 것을 알고 있습니다.

이 경우, 나는 다음과 같은 라인이 과도한 양의 시간이 걸릴 것으로 예상 했었을 것이다. 왜냐하면 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의 대답 은 완전성을 위해 선택되었지만 range 가 Python 3에서 본격적인 시퀀스 가된다는 것을 의미하는 좋은 논의에 대한 abarnert의 첫 번째 대답 과 전체에서 __contains__ 함수 최적화에 대한 잠재적 인 불일치에 대한 정보 / 경고 파이썬 구현. abarnert의 다른 대답 은 좀 더 자세하게 설명되어 있으며 Python 3의 최적화에 대한 관심이있는 사람들 (Python 2에서 xrange 의 최적화가 부족함)에 관심이있는 사람들을위한 링크를 제공합니다. poke 와 wim의 답변은 관련 C 소스 코드와 관심있는 사람들의 설명을 제공합니다.




다른 답변은 이미 잘 설명되어 있지만 범위 객체의 특성을 보여주는 또 다른 실험을 제안하고자합니다.

>>> 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]

보시다시피 범위 객체는 범위를 기억하고 한 번만 생성하는 것이 아니라 반복하는 동안 여러 번 사용할 수있는 객체입니다.




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



Related