Por que "1000000000000000 no intervalo (1000000000000001)" é tão rápido no Python 3?

Entendo que a range()função, que na verdade é um tipo de objeto no Python 3 , gera seu conteúdo rapidamente, semelhante a um gerador.

Sendo esse o caso, eu esperaria que a linha a seguir levasse um tempo excessivo, porque, para determinar se 1 quadrilhão está no intervalo, seria necessário gerar um quadrilhão de valores:

1000000000000000 in range(1000000000000001)

Além disso: parece que não importa quantos zeros adiciono, o cálculo leva mais ou menos a mesma quantidade de tempo (basicamente instantâneo).

Eu também tentei coisas assim, mas o cálculo ainda é quase instantâneo:

1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens

Se eu tentar implementar minha própria função de faixa, o resultado não é tão bom!

def my_crappy_range(N):
    i = 0
    while i < N:
        yield i
        i += 1
    return

O que o range()objeto está fazendo sob o capô que o torna tão rápido?

A resposta de Martijn Pieters foi escolhida por sua integralidade, mas também é a primeira resposta de abarnert para uma boa discussão sobre o que significa rangeser uma sequência completa no Python 3 e algumas informações / avisos sobre inconsistência potencial para __contains__otimização de funções nas implementações do Python . A outra resposta de abarnert entra em mais detalhes e fornece links para os interessados ​​na história por trás da otimização no Python 3 (e falta de otimização xrangeno Python 2). Respostas por cutucar e por wim fornecem o código fonte C relevante e explicações para aqueles que estão interessados.

O range()objeto Python 3 não produz números imediatamente; é um objeto de sequência inteligente que produz números sob demanda . Tudo o que ele contém são os valores de início, parada e etapa, e à medida que você itera sobre o objeto, o próximo número inteiro é calculado a cada iteração.

O objeto também implementa o object.__contains__gancho e calcula se o seu número faz parte do seu intervalo. O cálculo é uma operação em tempo constante (próximo) ^* . Nunca é necessário verificar todos os números possíveis no intervalo.

Na range()documentação do objeto :

A vantagem do rangetipo sobre um regular listou tupleé que um objeto de intervalo sempre terá a mesma quantidade (pequena) de memória, não importa o tamanho do intervalo que representa (como ele só armazena os start, stope stepvalores, cálculo itens individuais e subranges como necessário).

Portanto, no mínimo, seu range()objeto faria:

class my_range(object):
    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('Index out of range: {}'.format(i))

    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

Isso ainda está faltando várias coisas que um verdadeiro range()suportes (como os .index()ou .count()métodos, hashing, testes igualdade, ou corte), mas deve dar-lhe uma idéia.

Também simplifiquei a __contains__implementação para focar apenas em testes inteiros; se você atribuir a um range()objeto real um valor não inteiro (incluindo subclasses de int), uma varredura lenta será iniciada para verificar se há uma correspondência, como se você usasse um teste de contenção em uma lista de todos os valores contidos. Isso foi feito para continuar a oferecer suporte a outros tipos numéricos que, por acaso, oferecem suporte ao teste de igualdade com números inteiros, mas não é esperado que eles também suportem aritmética inteira. Veja o problema original do Python que implementou o teste de contenção.

* Tempo quase constante, porque os números inteiros do Python são ilimitados e, portanto, as operações matemáticas também crescem com o tempo, à medida que N cresce, tornando essa operação O (log N). Como tudo é executado no código C otimizado e o Python armazena valores inteiros em partes de 30 bits, você fica sem memória antes de ver qualquer impacto no desempenho devido ao tamanho dos números inteiros envolvidos aqui.

O mal-entendido fundamental aqui é pensar que rangeé um gerador. Não é. De fato, não é nenhum tipo de iterador.

Você pode dizer isso facilmente:

>>> a = range(5)
>>> print(list(a))
[0, 1, 2, 3, 4]
>>> print(list(a))
[0, 1, 2, 3, 4]

Se fosse um gerador, iterá-lo uma vez o esgotaria:

>>> b = my_crappy_range(5)
>>> print(list(b))
[0, 1, 2, 3, 4]
>>> print(list(b))
[]

O que rangerealmente é, é uma sequência, como uma lista. Você pode até testar isso:

>>> import collections.abc
>>> isinstance(a, collections.abc.Sequence)
True

Isso significa que ele deve seguir todas as regras de ser uma sequência:

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

A diferença entre a rangee a listé que a rangeé uma sequência lenta ou dinâmica ; ele não se lembra de todos os seus valores, ele apenas se lembra de seu start, stope step, e cria os valores sob demanda on __getitem__.

(Como uma observação lateral, se você print(iter(a))notar que rangeusa o mesmo listiteratortipo de list. Como isso funciona? A listiteratornão usa nada de especial, listexceto pelo fato de fornecer uma implementação C de __getitem__, portanto funciona bem para rangetambém.)

Agora, não há nada que diga que Sequence.__contains__deve haver tempo constante - de fato, para exemplos óbvios de sequências como list, não é. Mas não há nada que diga que não pode ser. E é mais fácil implementar implementar range.__contains__apenas verificá-lo matematicamente ( (val - start) % stepmas com alguma complexidade extra para lidar com etapas negativas) do que realmente gerar e testar todos os valores; por que não fazer da melhor maneira?

Mas parece não haver nada no idioma que garanta que isso aconteça. Como Ashwini Chaudhari aponta, se você der um valor não integral, em vez de converter para número inteiro e fazer o teste matemático, ele voltará a iterar todos os valores e compará-los um por um. E apenas porque as versões do CPython 3.2+ e PyPy 3.x contêm essa otimização, e é uma boa ideia óbvia e fácil de fazer, não há razão para que o IronPython ou o NewKickAssPython 3.x não possam deixar de fora. (E, de fato, o CPython 3.0-3.1 não o incluiu.)

Se, rangena verdade, fosse um gerador, my_crappy_rangenão faria sentido testar __contains__dessa maneira, ou pelo menos a maneira como faz sentido não seria óbvia. Se você já iterou os três primeiros valores, 1ainda é ino gerador? O teste deve 1fazer com que ele itere e consuma todos os valores até 1(ou até o primeiro valor >= 1)?

Use a fonte , Luke!

No CPython, range(...).__contains__(um invólucro de método) acabará delegando um cálculo simples que verifica se o valor pode estar no intervalo. A razão para a velocidade aqui é que estamos usando um raciocínio matemático sobre os limites, em vez de uma iteração direta do objeto range . Para explicar a lógica usada:

1. Verifique se o número está entre starte stop, e
2. Verifique se o valor da passada não ultrapassa o nosso número.

Por exemplo, 994está dentro range(4, 1000, 2)porque:

1. 4 <= 994 < 1000e
2. (994 - 4) % 2 == 0.

O código C completo está incluído abaixo, que é um pouco mais detalhado devido ao gerenciamento de memória e aos detalhes da contagem de referência, mas a idéia básica está lá:

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);
}

A "carne" da ideia é mencionada na linha :

/* result = ((int(ob) - start) % step) == 0 */ 

Como nota final - observe a range_containsfunção na parte inferior do trecho de código. Se a verificação exata do tipo falhar, não usaremos o algoritmo inteligente descrito, em vez disso, voltaremos a uma pesquisa de iteração idiota do intervalo usando _PySequence_IterSearch! Você pode verificar esse comportamento no intérprete (estou usando a v3.5.0 aqui):

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

Para adicionar à resposta de Martijn, esta é a parte relevante da fonte (em C, como o objeto range é escrito no código nativo):

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);
}

Portanto, para PyLongobjetos (que está intno Python 3), ele usará a range_contains_longfunção para determinar o resultado. E essa função essencialmente verifica seob está no intervalo especificado (embora pareça um pouco mais complexo em C).

Se não for um intobjeto, ele volta à iteração até encontrar o valor (ou não).

Toda a lógica pode ser traduzida para pseudo-Python assim:

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

Se você está se perguntando por que essa otimização foi adicionada range.__contains__e por que não foi adicionada xrange.__contains__no 2.7:

Primeiro, como Ashwini Chaudhary descobriu, a edição 1766304 foi aberta explicitamente para otimizar [x]range.__contains__. Um patch para isso foi aceito e registrado no 3.2 , mas não foi portado para 2.7 porque "o xrange se comportou assim por tanto tempo que não vejo o que é necessário para cometer o patch tão tarde". (2,7 estava quase fora nesse ponto.)

Enquanto isso:

Originalmente, xrangeera um objeto que não era exatamente uma sequência. Como dizem os documentos 3.1 :

Os objetos Range têm muito pouco comportamento: eles suportam apenas indexação, iteração e lenfunção.

Isso não era bem verdade; um xrangeobjeto realmente suporta algumas outras coisas que vêm automaticamente com a indexação e len, ^* incluindo __contains__(por meio de pesquisa linear). Mas ninguém pensou que valia a pena fazer sequências completas na época.

Em seguida, como parte da implementação do PEP das Classes base abstratas , era importante descobrir quais tipos internos deveriam ser marcados como implementando quais ABCs e xrange/ rangealegavam implementarcollections.Sequence , mesmo que ainda tratasse apenas o mesmo "muito pouco comportamento". Ninguém percebeu esse problema até a edição 9213 . O remendo para o problema que não só adicionado indexe counta 3,2 da range, também re-trabalhado a optimizado __contains__(que partes da mesma matemática com index, e é utilizado directamente por count). ^** Essa alteração também foi para o 3.2 e não foi suportada para 2.x, porque "é uma correção de bug que adiciona novos métodos". (Nesse ponto, 2.7 já tinha passado do status rc.)

Portanto, havia duas chances de obter essa otimização backported para 2,7, mas ambas foram rejeitadas.

_{* De fato, você obtém iteração de graça apenas com a indexação, mas na versão 2.3 osxrange objetos têm um iterador personalizado.}

_{** A primeira versão realmente a reimplementou e os detalhes foram errados - por exemplo, isso daria a você MyIntSubclass(2) in range(5) == False . Mas a versão atualizada de Daniel Stutzbach do patch restaurou a maior parte do código anterior, incluindo o fallback para o genérico, lento _PySequence_IterSearchque o pré-3.2 range.__contains__estava usando implicitamente quando a otimização não se aplica.}

As outras respostas já explicaram bem, mas eu gostaria de oferecer outro experimento que ilustra a natureza dos objetos de alcance:

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

Como você pode ver, um objeto de intervalo é um objeto que se lembra do seu alcance e pode ser usado várias vezes (mesmo enquanto iterando sobre ele), não apenas um gerador único.

É uma abordagem preguiçosa para a avaliação e uma otimização extra do range. Os valores nos intervalos não precisam ser calculados até o uso real, ou ainda mais devido à otimização extra.

A propósito, seu número inteiro não é tão grande, considere sys.maxsize

sys.maxsize in range(sys.maxsize) é bem rápido

devido à otimização - é fácil comparar um número inteiro fornecido apenas com o mínimo e o máximo do intervalo.

mas:

Decimal(sys.maxsize) in range(sys.maxsize) é bem lento .

(nesse caso, não há otimização range, portanto, se o python receber um decimal inesperado, o python comparará todos os números)

Você deve estar ciente de um detalhe da implementação, mas não deve ser invocado, pois isso pode mudar no futuro.

TL; DR

O objeto retornado por range()é realmente umrange objeto. Este objeto implementa a interface do iterador para que você possa iterar sobre seus valores sequencialmente, como um gerador, lista ou tupla.

Mas também implementa a __contains__interface que é na verdade chamada quando um objeto aparece no lado direito do inoperador. O __contains__()método retorna a boolse o item no lado esquerdo do inobjeto está ou não . Como os rangeobjetos conhecem seus limites e avanços, isso é muito fácil de implementar em O (1).

1. Devido à otimização, é muito fácil comparar números inteiros apenas com os intervalos mínimo e máximo.
2. A razão pela qual a função range () é tão rápida no Python3 é que aqui usamos o raciocínio matemático para os limites, em vez de uma iteração direta do objeto range.
3. Então, para explicar a lógica aqui:
   • Verifique se o número está entre o início e o fim.
   • Verifique se o valor da precisão da etapa não ultrapassa o nosso número.

4. Tomemos um exemplo, 997 está no intervalo (4, 1000, 3) porque:

   4 <= 997 < 1000, and (997 - 4) % 3 == 0.

Tente valores x-1 in (i for i in range(x))grandes x, que usam uma compreensão do gerador para evitar a range.__contains__otimização.