¿Por qué es “100000000000000000 en el rango (100000000000000001)” tan rápido en Python 3?

Tengo entendido que la función range() , 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, habría esperado que la siguiente línea tomara una cantidad de tiempo excesiva, porque para determinar si 1 cuatrillón está en el rango, habría que generar un cuatrillón de valores:

 1000000000000000 in range(1000000000000001) 

Además: parece que no importa cuántos ceros agreguen, el cálculo lleva más o menos 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 

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


La respuesta de Martijn Pieters fue elegida por su integridad, pero también puede ver la primera respuesta de abarnert para una buena discusión de lo que significa que el range sea ​​una secuencia completa en Python 3, y alguna información / advertencia con respecto a la posible inconsistencia para __contains__ optimización de funciones en Implementaciones de Python. La otra respuesta de abarnert es más detallada 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). Las respuestas de poke y de wim proporcionan el código fuente de C relevante y las explicaciones para aquellos que estén interesados.

El objeto range() 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 recorre 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 constante O (1). Nunca es necesario explorar todos los enteros posibles en el rango.

Desde la documentación del objeto range() :

La ventaja del tipo de range sobre una list regular o tuple es que un objeto de rango siempre tomará la misma cantidad de memoria (pequeña), sin importar el tamaño del rango que representa (ya que solo almacena los valores de start , stop y step , calculando ítems individuales y subrangos según sea necesario).

Entonces, como mínimo, su objeto range() 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 algunas cosas que admite un range() real range() (como los .index() o .count() , el hashing, las pruebas de igualdad o el corte), pero debería darle una idea.

También simplifiqué la implementación __contains__ para centrarme solo en pruebas de enteros; Si le asigna a un objeto range() 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 solo son compatibles con las pruebas de igualdad con enteros, pero no se espera que también sean compatibles con la aritmética de enteros. Vea el problema original de Python que implementó la prueba de contención.

El malentendido fundamental aquí es pensar que el range es 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 realmente es el range , 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:

 >>> a[3] # indexable 3 >>> len(a) # sized 5 >>> 3 in a # membership True >>> reversed(a) # reversible  >>> a.index(3) # implements 'index' 3 >>> a.count(3) # implements 'count' 1 

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

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


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

Pero no parece haber nada en el lenguaje que garantice que esto sucederá. Como lo señala Ashwini Chaudhari, si le asigna un valor no integral, en lugar de convertirlo en entero y hacer la prueba matemática, recurrirá a la iteración de todos los valores y los comparará 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 para que IronPython o NewKickAssPython 3.x no puedan omitirla. (Y, de hecho, CPython 3.0-3.1 no lo incluyó).


Si el range realmente un generador, como my_crappy_range , entonces no tendría sentido probar __contains__ esta manera, o al menos la forma en que tiene sentido no sería obvia. Si ya has iterado los primeros 3 valores, ¿hay 1 todavía in el generador? ¿Las pruebas para 1 hacen iterar y consumir 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á a un cálculo simple que verifica si el valor puede estar en el rango. La razón de la velocidad aquí es que estamos utilizando 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 el start y la stop , y
  2. Compruebe que el valor de zancada no “pasa por alto” nuestro número.

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

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

El código completo de C se incluye a continuación, que es un poco más detallado debido a la administració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, mire la función range_contains en la parte inferior del fragmento de código. Si la verificación de tipo exacta falla, entonces no usamos el algoritmo inteligente descrito, en lugar de eso, _PySequence_IterSearch a una búsqueda por iteración del rango usando _PySequence_IterSearch ! Puedes 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); } 

Por lo tanto, 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 verifica 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 encuentra el valor (o no).

Toda la lógica podría traducirse 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ó al range.__contains__ , y por qué no se agregó a xrange.__contains__ en 2.7:

Primero, como descubrió Ashwini Chaudhary, el número 1766304 se abrió explícitamente para optimizar el [x]range.__contains__ . Se aceptó un parche para esto y se registró en la versión 3.2 , pero no se realizó una copia de seguridad de la versión 2.7 porque “xrange se ha comportado así durante tanto tiempo que no veo qué es lo que nos compra a cometer el parche tan tarde”. (2.7 estaba casi fuera en ese punto).

Mientras tanto:

Originalmente, xrange era un objeto no completamente secuenciado. Como dicen los documentos 3.1 :

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

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

Luego, como parte de la implementación del PEP de clases base abstractas , fue importante determinar qué tipos incorporados deben marcarse como implementadores de qué ABC, y xrange / range reclamó implementar collections.Sequence xrange , aunque todavía solo se maneja el mismo “muy poco comportamiento “. Nadie notó ese problema hasta el número 9213 . El parche para ese problema no solo agregó el index y el count al range de 3.2, sino que también volvió a trabajar el __contains__ optimizado (que comparte las mismas matemáticas con el index , y se usa directamente por count ). ** Este cambio fue también para la versión 3.2, y no fue portado a la versión 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 rc).

Por lo tanto, había dos posibilidades de que esta optimización fuera portada a 2.7, pero ambas fueron rechazadas.


* De hecho, incluso obtienes una iteración gratuita con len e indexación, pero en 2.3 objetos xrange obtuvimos un iterador personalizado. Que luego perdieron en 3.x, que utiliza el mismo tipo de listiterator que list .

** La primera versión realmente lo MyIntSubclass(2) in range(5) == False a MyIntSubclass(2) in range(5) == False y obtuvo los detalles incorrectos, por ejemplo, le daría 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, incluyendo el repliegue al genérico, lento _PySequence_IterSearch que el range.__contains__ 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 se puede usar 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 . Los valores en rangos no necesitan computarse hasta su uso real, o incluso más debido a la optimización adicional.

Por cierto, su número 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 rango mínimo y máximo.

pero:

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

(en este caso, no hay una optimización en el range , por lo que si Python recibe una flotación inesperada, Python comparará todos los números)

Debe conocer los detalles de la implementación, pero no debe confiarse en ellos, ya que esto puede cambiar en el futuro.

Aquí hay una implementación similar en C# . Puede ver cómo Contains hecho en O (1) tiempo.

 public struct Range { private readonly int _start; private readonly int _stop; private readonly int _step; //other methods/properties omitted public bool Contains(int number) { // precheck: if the number isn't in a valid point, return false // for example, if start is 5 and step is 10, then it's impossible for 163 to be in range (due to modulo) if ((_start % _step + _step) % _step != (number % _step + _step) % _step) return false; // v is vector: 1 means positive step, -1 means negative step // this value makes final checking formula straightforward. int v = Math.Abs(_step) / _step; // since we have vector, no need to write if/else to handle both cases: negative and positive step return number * v >= _start * v && number * v < _stop * v; } } 

TL; DR

El objeto devuelto por range() es en realidad un objeto de range . Este objeto implementa la interfaz del iterador para que pueda recorrer sus valores de forma secuencial, como un generador, pero también implementa la interfaz __contains__ , que en realidad es lo que se llama cuando aparece un objeto en el lado derecho del operador in . El __contains__() devuelve un bool de si el elemento está o no en el objeto. Como los objetos de range conocen sus límites y su paso, esto es muy fácil de implementar en O (1).