¿Por qué es" 1000000000000000 en rango(1000000000000001) " tan rápido en Python 3?

El malentendido fundamental aquí está en pensar que range es un generador. No lo es. De hecho, no es ningún tipo de iterador.

Puedes decir esto muy fácilmente: {[34]]}

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

Si fuera un generador, iterarlo una vez lo agotaría: {[34]]}

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

Lo que range realmente es, es una secuencia, al igual que una lista. Incluso puedes probar esto:

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

Esto significa que tiene que seguir todas las reglas de ser una secuencia: {[34]]}

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

La diferencia entre a range y a list es que a range es una secuencia perezosa o dinámica ; no recuerda todos sus valores, solo recuerda su start, stop, y step, y crea los valores bajo demanda en __getitem__.

(Como nota al margen, si print(iter(a)), notarás que range usa el mismo tipo listiterator que list. ¿Cómo funciona eso? A listiterator no usa nada especial sobre list excepto por el hecho de que proporciona una implementación en C de __getitem__, por lo que funciona bien para range demasiado.)

Ahora, no hay nada que diga que Sequence.__contains__ tiene que ser tiempo constante-de hecho, para ejemplos obvios de secuencias como list, no lo es. Pero no hay nada que diga que no pueda ser. Y es más fácil implementar range.__contains__ simplemente comprobarlo matemáticamente ((val - start) % step, pero con cierta complejidad adicional para lidiar con pasos negativos) que realmente generar y probar todos los valores, así que ¿por qué no debería hacerlo de la mejor manera?

Pero no parece haber cualquier cosa en el lenguaje quegarantiza esto sucederá. Como señala Ashwini Chaudhari, si le das un valor no integral, en lugar de convertir a entero y hacer la prueba matemática, volverá a iterar todos los valores y compararlos uno por uno. Y solo porque CPython 3.2+ y PyPy 3.las versiones x contienen esta optimización, y es una buena idea obvia y fácil de hacer, no hay razón para que IronPython o NewKickAssPython 3.x no podía dejarlo fuera. (Y, de hecho, CPython 3.0-3.1 no incluirlo.)

Si range realmente fuera un generador, como my_crappy_range, entonces no tendría sentido probar __contains__ de esta manera, o al menos la forma en que tiene sentido no sería obvia. Si ya había iterado los primeros 3 valores, es 1 todavía in el generador? ¿Debería probar 1 hacer que itere y consuma todos los valores hasta 1 (o hasta el primer valor >= 1)?

Usa la fuente , Luke!

En CPython, range(...).__contains__ (un envoltorio de método) eventualmente delegará a un cálculo simple que comprueba si el valor puede estar posiblemente en el rango. La razón de la velocidad aquí es que estamos usando razonamiento matemático sobre los límites, en lugar de una iteración directa del objeto de rango. Para explicar la lógica utilizada:

1. Compruebe que el número está entre start y stop, y
2. Compruebe que el valor de zancada no "paso sobre" nuestro número.

Por ejemplo, 994 está en range(4, 1000, 2) porque:

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

El código C completo se incluye a continuación, que es un poco más detallado debido a la gestión de la memoria y los detalles de conteo de referencias, pero la idea básica está ahí:

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

La "carne" de la idea se menciona en la línea:

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

Como nota final - mira la función range_contains en la parte inferior del fragmento de código. Si el la verificación exacta del tipo falla, entonces no usamos el algoritmo inteligente descrito, sino que volvemos a una búsqueda de iteración tonta del rango usando _PySequence_IterSearch! Puede comprobar este comportamiento en el intérprete (estoy usando v3.5.0 aquí):

>>> 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 añadir a la respuesta de Martijn, esta es la parte relevante de la fuente (en C, ya que el objeto range está escrito en 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);
}

Así que para los objetos PyLong (que es int en Python 3), utilizará la función range_contains_long para determinar el resultado. Y esa función esencialmente comprueba si ob está en el rango especificado (aunque parece un poco más complejo en C).

Si no es un objeto int, vuelve a iterar hasta que encuentre el valor (o ni).

Toda la lógica podría ser traducida a pseudo-Python así:

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

Si se pregunta por qué esta optimización se agregó a range.__contains__, y por qué no se agregó a xrange.__contains__ en 2.7:

Primero, como Ashwini Chaudhary descubrió, el número 1766304 se abrió explícitamente para optimizar [x]range.__contains__. Un parche para esto fue aceptado y registrado para la versión 3.2, pero no fue backportado a la versión 2.7 porque "xrange se ha comportado así durante tanto tiempo que no veo qué nos compra confirmar el parche tan tarde."(2.7 estaba casi fuera en eso punto.)

Mientras tanto:

Originalmente, xrange era un objeto no muy secuencial. Como los documentos 3.1 dicen:

Los objetos de rango tienen muy poco comportamiento: solo admiten indexación, iteración y la función len.

Esto no era del todo cierto; un objeto xrange en realidad soportaba algunas otras cosas que vienen automáticamente con la indexación y len,^* incluido __contains__ (mediante búsqueda lineal). Pero nadie pensó que valía la pena hacerlos secuencias completas en ese momento.

Luego, como parte de la implementación del Abstract Base Classes PEP, fue importante averiguar qué tipos incorporados deben marcarse como implementando qué ABCs, y xrange/range afirmó implementar collections.Sequence, a pesar de que todavía solo manejaba el mismo "muy poco comportamiento". Nadie notó ese problema hasta issue 9213. El parche para ese problema no solo agregó index y count a range de 3.2, sino que también reelaboró el __contains__ optimizado (que comparte la misma matemática con index, y es usada directamente por count).^**Este cambio fue por 3.2, y no fue portado a 2.x, porque "es una corrección de errores que añade nuevos métodos". (En este punto, 2.7 ya había pasado el estado de rc.)

Por lo tanto, había dos posibilidades de obtener esta optimización backported a 2.7, pero ambos fueron rechazados.

_{* De hecho, incluso obtienes iteración gratis con len e indexación, pero en 2.3 xrange los objetos tienen un iterador personalizado. Que luego perdieron en 3.x, que usa el mismo tipo listiterator que list.}

_{** La primera versión realmente lo reimplementó, y obtuvo los detalles incorrectos-por ejemplo, le daría MyIntSubclass(2) in range(5) == False. Pero la versión actualizada de Daniel Stutzbach del parche restauró la mayor parte del código anterior, incluyendo el respaldo al genérico y lento _PySequence_IterSearch que antes de la 3.2 range.__contains__ estaba usando implícitamente cuando la optimización no se aplica.}

Las otras respuestas ya lo explicaron bien, pero me gustaría ofrecer otro experimento que ilustra la naturaleza de los objetos de rango:

>>> 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 puede ver, un objeto de rango es un objeto que recuerda su rango y se puede usar muchas veces (incluso mientras itera sobre él), no solo un generador de una sola vez.

Se trata de un enfoque perezoso para la evaluación, y una optimización adicional de range. Los valores en rangos no necesitan ser calculados hasta el uso real, o incluso más debido a la optimización adicional.

Por cierto, su entero no es tan grande, considere sys.maxsize

sys.maxsize in range(sys.maxsize) es bastante rápido

Debido a la optimización, es fácil comparar un entero dado solo con el mínimo y el máximo de rango.

Pero:

float(sys.maxsize) in range(sys.maxsize) es bastante lento.

(en este caso no hay optimización en range, por lo que desde recibir float inesperado, python comparará todos los números)