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


Entiendo que el range() función, que es en realidad un tipo de objeto en Python 3, genera sus contenidos sobre la marcha, de forma similar a un generador.

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

1000000000000000 in range(1000000000000001)

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

También he intentado cosas como esta, pero el cálculo es 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

Cuál es el range() hacer objetos debajo del capó que lo hace tan rápido?


La respuesta de Martijn Pieters fue elegido por su integridad, pero también ver La primera respuesta de abarnert para una buena discusión de lo que significa para range ser un completo secuencia en Python 3, y alguna información / advertencia con respecto a posibles incoherencias para __contains__ optimización de funciones en implementaciones de Python. 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 de xrange en Python 2). Respuestas por poke y por wim proporcione el código fuente relevante de C y las explicaciones para aquellos que estén interesados.


1364
2018-05-06 15:32


origen


Respuestas:


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

El objeto también implementa el object.__contains__ ganchoy calcula si su número es parte de su rango. El cálculo es una operación de tiempo constante O (1). Nunca es necesario escanear todos los enteros posibles en el rango.

Desde el range() documentación del objeto:

La ventaja de range escriba más de lo normal list o tuple es que un objeto rango siempre tomará la misma cantidad (pequeña) de memoria, sin importar el tamaño del rango que representa (ya que solo almacena el start, stop y step valores, calculando elementos individuales y subrangos según sea necesario).

Entonces, como mínimo, tu 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 = stop, start
        else:
            lo, hi = start, stop
        self.length = ((hi - lo - 1) // abs(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

Todavía faltan varias cosas que un verdadero range() soportes (como el .index() o .count() métodos, hashing, pruebas de igualdad o segmentación), pero deberían darle una idea.

También simplifiqué __contains__ implementación para enfocarse solo en pruebas enteras; si das un verdadero range() object 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 la aritmética de enteros también. Ver el original Problema de Python que implementó la prueba de contención.


1351
2018-05-06 15:33



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

Puedes decir esto bastante fácilmente:

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

Qué range en realidad 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 un range y un list es que una range es un perezoso o dinámica secuencia; no recuerda todos sus valores, solo recuerda su start, stopy stepy crea los valores según demanda en __getitem__.

(Como nota al margen, si print(iter(a)), notarás que range usa el mismo listiterator escriba como list. ¿Cómo funciona? UN listiterator no usa nada especial sobre list excepto por el hecho de que proporciona una implementación C de __getitem__, así que funciona bien para range también.)


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

Pero no parece haber nada en el lenguaje que garantías esto es lo que va a ocurrir. Como señala Ashwini Chaudhari, si le das un valor no integral, en lugar de convertirlo a entero y hacer la prueba matemática, volverá a iterar todos los valores y compararlos uno por uno. Y solo porque las versiones de CPython 3.2+ y PyPy 3.x contengan 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 hizo incluirlo)


Si range en realidad era un generador, como my_crappy_range, entonces no tendría sentido probar __contains__ de esta manera, o al menos de la manera en que tiene sentido, no sería obvio. Si ya había iterado los primeros 3 valores, es 1 todavía in ¿el generador? Debería probar para 1 provocar iterar y consumir todos los valores hasta 1 (o hasta el primer valor >= 1)?


561
2018-05-06 16:01



Utilizar el fuente¡Luke!

En CPython, range(...).__contains__ (un contenedor de método) eventualmente delegará a un simple cálculo que verifica si el valor puede estar dentro del 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 rango. Para explicar la lógica utilizada:

  1. Verifique que el número esté entre start y stopy
  2. Compruebe que el valor de zancada no "sobrepase" nuestro número.

Por ejemplo, 994 es 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 de recuento de referencias, pero la idea básica está allí:

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 el range_contains función en la parte inferior del fragmento de código. Si falla la verificación de tipo exacta, no usamos el algoritmo inteligente descrito, sino que volvemos 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)

285
2018-05-06 15:41



Para agregar a la respuesta de Martijn, esta es la parte relevante de la fuente (en C, como el objeto 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 PyLong objetos (que es int en Python 3), usará range_contains_long función para determinar el resultado. Y esa función esencialmente verifica si ob está en el rango especificado (aunque parece un poco más complejo en C).

Si no es un int objeto, 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

106
2018-05-06 15:41



Si te estás preguntando por qué esta optimización se agregó a range.__contains__y por qué no fue añadido a xrange.__contains__ en 2.7:

Primero, como descubrió Ashwini Chaudhary, número 1766304 fue abierto explícitamente para optimizar [x]range.__contains__. Un parche para esto fue aceptado y registrado para 3.2, pero no backported a 2.7 porque "xrange se ha comportado así durante tanto tiempo que no veo lo que nos compra para comprometer el parche tan tarde". (2.7 estuvo casi fuera en ese punto).

Mientras tanto:

Originalmente, xrange era un objeto que no era bastante secuencia. Como los 3.1 documentos decir:

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

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

Luego, como parte de la implementación del Clases base abstractas PEP, era importante determinar qué tipos de componentes incorporados deberían marcarse para implementar qué ABC, y xrange/range reclamado para implementar collections.Sequence, aunque solo manejó el mismo "muy poco comportamiento". Nadie notó ese problema hasta número 9213. El parche para ese problema no solo se agregó index y count a 3.2's range, también re-trabajó el optimizado __contains__ (que comparte la misma matemática con index, y es utilizado directamente por count)**  Este cambio también ingresó 3.2 y no fue transferido a 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).

Entonces, hubo dos oportunidades para que esta optimización se transfiriera a 2.7, pero ambas fueron rechazadas.


* De hecho, incluso obtiene iteración gratis con len e indexación, pero en 2.3  xrange objetos obtuvieron un iterador personalizado. Que luego perdieron en 3.x, que usa el mismo listiterator escriba como list.

** La primera versión realmente lo volvió a implementar y obtuvo los detalles incorrectos, 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, incluida la alternativa al genérico, lento _PySequence_IterSearch ese pre-3.2 range.__contains__ estaba usando implícitamente cuando la optimización no se aplica.


79
2018-05-06 21:42



Las otras respuestas ya lo explicaron bien, pero me gustaría ofrecer otro experimento que ilustre 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 cuando se itera sobre él), no solo un generador de una sola vez.


35
2018-05-06 16:04



Se trata de un enfoque perezoso de la evaluación y de una optimización adicional de range. No es necesario calcular los valores en 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 el número entero dado con un mínimo y un máximo de rango.

pero:

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

(en este caso no hay optimización en range, así que como recibes flotante inesperado, Python comparará todos los números)


3
2018-03-16 10:47