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

Tengo entendido que la range()función, que en realidad es un tipo de objeto en Python 3 , genera su contenido sobre la marcha, similar a un generador.

Siendo este el caso, hubiera esperado que la siguiente línea tomara una cantidad excesiva de tiempo, porque para determinar si 1 billón está en el rango, se tendrían que generar un billón de valores:

1000000000000000 in range(1000000000000001)

Además: parece que no importa cuántos ceros agregue, el cálculo toma más o menos la misma cantidad de tiempo (básicamente instantáneo).

También he probado cosas como esta, pero el cálculo sigue siendo casi instantáneo:

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

¡Si trato de implementar mi propia función de rango, el resultado no es tan bueno!

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

¿Qué hace el range()objeto debajo del capó que lo hace tan rápido?

La respuesta de Martijn Pieters fue elegida por su integridad, pero también vea la primera respuesta de abarnert para una buena discusión de lo que significa rangeser una secuencia completa en Python 3, y alguna información / advertencia sobre la posible inconsistencia para la __contains__optimización de funciones en las implementaciones de Python . La otra respuesta de abarnert entra en más detalles y proporciona enlaces para aquellos interesados ​​en la historia detrás de la optimización en Python 3 (y la falta de optimización xrangeen Python 2). Las respuestas por empuje y por wim proporcionan el código fuente C relevante y explicaciones para aquellos que estén interesados.

El range()objeto Python 3 no produce números inmediatamente; es un objeto de secuencia inteligente que produce números a pedido . Todo lo que contiene son sus valores de inicio, parada y paso, luego, a medida que itera sobre el objeto, se calcula el siguiente entero en cada iteración.

El objeto también implementa el object.__contains__gancho y calcula si su número es parte de su rango. El cálculo es una operación de tiempo (casi) constante ^* . Nunca es necesario examinar todos los números enteros posibles del rango.

De la range()documentación del objeto :

La ventaja del rangetipo de más de un habitual listo tuplees que un objeto de rango siempre tendrá la misma (pequeña) cantidad de memoria, sin importar el tamaño de la gama que representa (ya que sólo se almacena los start, stopy steplos valores, el cálculo de los elementos individuales y subintervalos según sea necesario).

Entonces, como mínimo, su range()objeto haría:

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

A esto todavía le faltan varias cosas que range()admite una realidad (como los métodos .index()o .count(), el hash, las pruebas de igualdad o el corte), pero debería darle una idea.

También simplifiqué la __contains__implementación para centrarme solo en las pruebas de números enteros; si le da a un range()objeto real un valor no entero (incluidas las subclases de int), se inicia un escaneo lento para ver si hay una coincidencia, como si usara una prueba de contención contra una lista de todos los valores contenidos. Esto se hizo para continuar admitiendo otros tipos numéricos que simplemente admiten pruebas de igualdad con enteros, pero no se espera que admitan también aritmética de enteros. Vea el problema original de Python que implementó la prueba de contención.

* Tiempo casi constante porque los enteros de Python no están acotados y, por lo tanto, las operaciones matemáticas también crecen en el tiempo a medida que crece N, lo que la convierte en una operación O (log N). Dado que todo se ejecuta en código C optimizado y Python almacena valores enteros en fragmentos de 30 bits, se quedaría sin memoria antes de ver algún impacto en el rendimiento debido al tamaño de los enteros involucrados aquí.

El malentendido fundamental aquí es pensar que rangees un generador. No es. De hecho, no es ningún tipo de iterador.

Puedes decir esto con bastante facilidad:

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

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

Lo que rangerealmente es, es una secuencia, como 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:

>>> 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 ay rangea listes que a rangees una secuencia dinámica o perezosa ; que no recuerda todos sus valores, sólo recuerda su , y , y crea los valores de la demanda en .startstopstep__getitem__

(Como nota al margen, si usted print(iter(a)), notará que rangeusa el mismo listiteratortipo que list. ¿Cómo funciona eso? A listiteratorno usa nada especial listexcepto por el hecho de que proporciona una implementación C de __getitem__, por lo que funciona bien para rangetambién.)

Ahora, no hay nada que diga que Sequence.__contains__tiene que ser un tiempo constante; de ​​hecho, para ejemplos obvios de secuencias como list, no lo es. Pero no hay nada que diga que no puede ser. Y es más fácil de implementar range.__contains__para verificarlo matemáticamente ( (val - start) % steppero con cierta complejidad adicional para lidiar con los pasos negativos) que generar y probar todos los valores, entonces, ¿por qué no debería hacerlo de la mejor manera?

Pero no parece haber nada en el idioma que garantice que esto sucederá. Como señala Ashwini Chaudhari, si le da un valor no integral, en lugar de convertir a un número entero y hacer la prueba matemática, volverá a iterar todos los valores y compararlos uno por uno. Y solo porque las versiones CPython 3.2+ y PyPy 3.x contienen esta optimización, y es una buena idea obvia y fácil de hacer, no hay razón por la que IronPython o NewKickAssPython 3.x no puedan omitirla. (Y, de hecho, CPython 3.0-3.1 no lo incluyó).

Si en rangerealidad fuera un generador, my_crappy_rangeentonces no tendría sentido probar de __contains__esta manera, o al menos la forma en que tiene sentido no sería obvia. Si ya ha iterado los primeros 3 valores, ¿sigue 1siendo inel generador? ¿Debería hacer las pruebas para 1que se repita 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 se delegará en un cálculo simple que verifica si el valor puede posiblemente estar en el rango. La razón de la velocidad aquí es que estamos usando un 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 starty stop, y
2. Compruebe que el valor de la zancada no "sobrepase" nuestro número.

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

1. 4 <= 994 < 1000y
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 del recuento 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, mire la range_containsfunción en la parte inferior del fragmento de código. Si la verificación de tipo exacta falla, entonces no usamos el algoritmo inteligente descrito, sino que recurrimos a una búsqueda de iteración tonta del rango usando _PySequence_IterSearch! Puede verificar 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 agregar a la respuesta de Martijn, esta es la parte relevante de la fuente (en C, ya que el objeto de rango 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);
}

Entonces, para los PyLongobjetos (que está inten Python 3), usará la range_contains_longfunción para determinar el resultado. Y esa función esencialmente verifica si obestá en el rango especificado (aunque parece un poco más complejo en C).

Si no es un intobjeto, vuelve a iterar hasta que encuentra el valor (o no).

Toda la lógica podría traducirse a pseudo-Python de esta manera:

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é se agregó esta optimización range.__contains__y por qué no se agregó xrange.__contains__en 2.7:

Primero, como descubrió Ashwini Chaudhary, el número 1766304 se abrió explícitamente para optimizar [x]range.__contains__. Se aceptó un parche para esto y se registró para la versión 3.2 , pero no se actualizó a la versión 2.7 porque "xrange se ha comportado así durante tanto tiempo que no veo lo que nos compra para enviar el parche tan tarde". (2.7 estaba casi terminado en ese momento).

Mientras tanto:

Originalmente, xrangeera un objeto no del todo secuencia. Como dicen los documentos 3.1 :

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

Esto no era del todo cierto; un xrangeobjeto en realidad admite algunas otras cosas que vienen automáticamente con la indexación y len, ^* incluido __contains__(a través de la búsqueda lineal). Pero nadie pensó que valiera la pena hacerlas secuencias completas en ese momento.

Luego, como parte de la implementación del PEP de las clases base abstractas , era importante averiguar qué tipos integrados debían marcarse como implementadores de qué ABC, y xrange/ rangeafirmaba implementar collections.Sequence, aunque todavía solo manejaba el mismo "comportamiento muy pequeño". Nadie notó ese problema hasta el número 9213 . El parche para ese problema no sólo se sumó indexy count3,2 de range, sino que también re-trabajó la optimizado __contains__(que comparte el mismo matemáticas con index, y se utiliza directamente por count). ^** Este cambio también se incluyó en la versión 3.2 y no se actualizó a la 2.x, porque "es una corrección de errores que agrega nuevos métodos". (En este punto, 2.7 ya había pasado el estado de rc).

Por lo tanto, hubo dos posibilidades de que esta optimización se transfiriera a 2.7, pero ambas fueron rechazadas.

_{* De hecho, incluso obtienes iteración gratis solo con la indexación, pero en 2.3 los xrange objetos obtuvieron un iterador personalizado.}

_{** La primera versión en realidad lo reimplementó y se equivocó en los detalles, por ejemplo, le daría MyIntSubclass(2) in range(5) == False. Pero la versión actualizada del parche de Daniel Stutzbach restauró la mayor parte del código anterior, incluido el retroceso al genérico, lento _PySequence_IterSearchque pre-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 puede usarse muchas veces (incluso mientras se 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. No es necesario calcular los valores en los rangos hasta el uso real, o incluso más debido a una optimización adicional.

Por cierto, tu número entero no es tan grande, considera 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:

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

(en este caso, no hay optimización en range, por lo que si python recibe un decimal inesperado, python comparará todos los números)

Debe conocer un detalle de implementación, pero no se debe confiar en él, ya que esto puede cambiar en el futuro.

TL; DR

El objeto devuelto por range()es en realidad un rangeobjeto. Este objeto implementa la interfaz del iterador para que pueda iterar sobre sus valores secuencialmente, como un generador, una lista o una tupla.

Pero también implementa la __contains__interfaz que en realidad es lo que se llama cuando un objeto aparece en el lado derecho del inoperador. El __contains__()método devuelve una indicación boolde si el elemento del lado izquierdo del inestá o no en el objeto. Dado que los rangeobjetos conocen sus límites y zancadas, esto es muy fácil de implementar en O (1).

1. Debido a la optimización, es muy fácil comparar enteros dados solo con el rango mínimo y máximo.
2. La razón por la que la función range () es tan rápida en Python3 es que aquí usamos razonamiento matemático para los límites, en lugar de una iteración directa del objeto range.
3. Entonces, para explicar la lógica aquí:
   • Compruebe si el número está entre el inicio y el final.
   • Compruebe si el valor de la precisión del paso no supera nuestro número.

4. Tomemos un ejemplo, 997 está en el rango (4, 1000, 3) porque:

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

Pruebe x-1 in (i for i in range(x))con xvalores grandes , que utiliza una comprensión del generador para evitar invocar la range.__contains__optimización.

TLDR; range es una serie aritmética, por lo que puede calcular muy fácilmente si el objeto está allí. Incluso podría obtener el índice si fuera list like muy rápido.