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

2116

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.

Rick apoia Monica
fonte
70
Observe que esse é o caso apenas se o item que estamos verificando for do tipo a boolou long, com outros tipos de objetos ele ficará louco. Tente com:100000000000000.0 in range(1000000000000001)
Ashwini Chaudhary
10
Quem te disse que rangeé um gerador?
Abarnert 6/05/15
7
@abarnert Acho que a edição que fiz deixou a confusão intacta.
Rick suporta Monica
5
@AshwiniChaudhary não é o Python2 xrangeigual ao Python3range ?
Superbest
28
Os xrange()objetos @Superbest não têm __contains__método, portanto a verificação do item precisa percorrer todos os itens. Além disso, existem algumas outras mudanças em range(), como ele suporta corte (que novamente retorna um rangeobjeto) e agora também tem counte indexmétodos para torná-lo compatível com o collections.SequenceABC.
Ashwini Chaudhary

Respostas:

2171

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.

Martijn Pieters
fonte
58
Curiosidade: como você tem uma implementação operacional de __getitem__e __len__, a __iter__implementação é realmente desnecessária.
Lucretiel
2
@ Lucretiel: No Python 2.3 , um especial xrangeiteratorfoi adicionado especificamente porque não era rápido o suficiente. E então em algum lugar no 3.x (não tenho certeza se era 3.0 ou 3.2) foi lançado e eles usam o mesmo listiteratortipo que listusa.
Abarnert
1
Eu definiria o construtor como def __init__(self, *start_stop_step)e analisaria a partir daí; a maneira como os argumentos são rotulados agora é agora meio confusa. No entanto, +1; você ainda definitivamente explicou o comportamento.
Cody Piersall
1
@CodyPiersall: Infelizmente, essa é a assinatura do inicializador da classe real. rangeé mais antigo que *args(muito menos a argclinicAPI que permite que as funções da C-API tenham assinaturas completas do Python). Algumas outras funções antigas (e algumas funções mais recentes, como xrange,, slicee itertools.islice, por consistência) funcionam da mesma maneira, mas, na maioria das vezes, Guido e o restante dos desenvolvedores principais parecem concordar com você. Os documentos 2.0+ até descrevem rangee amigos como se fossem sobrecargas no estilo C ++, em vez de mostrar a assinatura confusa.
Abarnert 16/05
2
@CodyPiersall: Na verdade, aqui está uma citação de Guido na argclinicdiscussão, quando Nick Coghlan encontrou uma maneira de definir rangesem ambiguidade: "Por favor, não facilite as pessoas copiarem minha pior decisão de design". Então, eu tenho certeza que ele concorda que rangeé confuso como está escrito.
Abarnert
845

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

abarnert
fonte
10
Isso é uma coisa muito importante para esclarecer. Suponho que as diferenças entre Python 2 e 3 possam ter levado à minha confusão sobre este ponto. De qualquer forma, eu deveria ter percebido uma vez que rangeestá listado (junto com liste tuple) como um tipo de sequência .
Rick apoia Monica
4
@ RickTeachey: Na verdade, em 2.6+ (acho; talvez 2.5+), também xrangeé uma sequência. Veja 2.7 documentos . De fato, sempre foi uma quase sequência.
Abarnert
5
@ RickTeachey: Na verdade, eu estava errado; em 2.6-2.7 (e 3.0-3.1), ele afirma ser uma sequência, mas ainda é apenas uma quase sequência. Veja minha outra resposta.
abarnert
2
Não é um iterador, é uma sequência (Iterável em termos de Java, IEnumerable de C #) - algo com um .__iter__()método que retornará um iterador. Por sua vez, pode ser usado apenas uma vez.
Smit Johnth
4
@ Thomashole: Como rangenão está verificando tipos quando não é um número inteiro, já que é sempre possível que um tipo tenha um __eq__que seja compatível int. Claro, strobviamente não vai funcionar, mas eles não queriam desacelerar as coisas, verificando explicitamente todos os tipos que não podem estar lá (e, afinal, uma strsubclasse pode substituir __eq__e estar contida no range).
ShadowRanger
377

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)
wim
fonte
144

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
cutucar
fonte
11
@ ChrisWesseling: Eu acho que essa é uma informação diferente o suficiente (e suficiente) que a edição da resposta de Martijn não seria apropriada aqui. É uma decisão de julgamento, mas as pessoas geralmente erram por não fazer mudanças drásticas nas respostas de outras pessoas.
abarnert
105

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.

abarnert
fonte
4
A partir dos comentários aqui: melhorarxrange.__contains__ , parece que eles não fizeram o backport para o Python 2 apenas para deixar um elemento de surpresa para os usuários e já era tarde demais o_O. A counte index remendo foi adicionado mais tarde. Arquivo naquela época: hg.python.org/cpython/file/d599a3f2e72d/Objects/rangeobject.c
Ashwini Chaudhary
12
Eu tenho uma suspeita sinistra que alguns devs núcleo python são parciais para "amor duro" para 2.x python porque querem incentivar as pessoas para mudar para o python3 muito superior de :)
wim
4
Também aposto que é um fardo enorme ter que adicionar novos recursos às versões antigas. Imagine se você fosse à Oracle e dissesse: "Estou no Java 1.4 e mereço expressões lambda! Faça o backport deles para nada".
Rob Grant
2
@ RickTeachey sim, é apenas um exemplo. Se eu dissesse 1,7, ainda seria aplicável. É uma diferença quantitativa, não qualitativa. Basicamente, os desenvolvedores (não pagos) não podem criar novas coisas legais no 3.x para sempre e fazer o backport para o 2.x para aqueles que não desejam atualizar. É um fardo enorme e ridículo. Você acha que ainda há algo errado com o meu raciocínio?
Rob Grant
3
@ RickTeachey: 2,7 estava entre 3,1 e 3,2, e não em torno de 3,3. E isso significa que 2.7 estava em rc quando as últimas alterações para 3.2 foram implementadas, o que facilita a compreensão dos comentários sobre os erros. Enfim, acho que eles cometeram alguns erros em retrospecto (especialmente assumindo que as pessoas migrariam via e 2to3não via código de versão dupla com a ajuda de bibliotecas como six, e é por isso que temos coisas como dict.viewkeysessas que ninguém nunca vai usar), e havia algumas mudanças que vieram tarde demais no 3.2, mas na maioria das vezes o 2.7 foi um lançamento impressionante "último 2.x de sempre".
Abarnert 16/05
47

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.

Stefan Pochmann
fonte
27

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

Sławomir Lenart
fonte
4
Cuidado ao flutuar números inteiros grandes. Na maioria das máquinas, float(sys.maxsize) != sys.maxsize)apesar de tudo sys.maxsize-float(sys.maxsize) == 0.
precisa saber é o seguinte
18

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

RBF06
fonte
0
  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.

Naruto
fonte
1
Você pode compartilhar fonte para isso? Mesmo se isso soa legítimo, que seria bom para fazer estas reivindicações por código real
Nico Haase
Eu acho que este é um exemplo disso poderia ser implementado. Não é exatamente o modo como é implementado. Embora nenhuma referência seja fornecida, é uma dica boa o suficiente para entender por que a verificação de inclusão no intervalo pode ser muito mais rápida que a lista ou a tupla
Mohammed Shareef C
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.

benjimin
fonte