python3 not python performance python-3.x range python-internals

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



python3 xrange (9)

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, 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 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 aún 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é está haciendo el objeto range() debajo del 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 sobre lo que significa que el range sea ​​una secuencia completa en Python 3, y alguna información / advertencia sobre la inconsistencia potencial para la optimización de la función __contains__ través de 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 de xrange en Python 2). Las respuestas por poke y por wim proporcionan el código fuente C relevante y explicaciones para aquellos que estén interesados.

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 secuencialmente, 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. Dado que los objetos de range conocen sus límites y zancadas, esto es muy fácil de implementar en O (1).

¡Usa la source , Luke!

En CPython, el range(...).__contains__ (un contenedor de métodos) eventualmente delegará en un cálculo simple que verifica si el valor puede 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. Verifique que el número esté entre start y stop , y
  2. Verifique que el valor de paso no "sobrepase" nuestro número.

Por ejemplo, 994 está dentro del 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 administración de 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, observe 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, sino que _PySequence_IterSearch 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)

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

En realidad, el range 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 una list es que un range es una secuencia perezosa o dinámica ; no recuerda todos sus valores, solo 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? Un listiterator no usa nada especial sobre 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 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 implementar el range.__contains__ solo para verificarlo matemáticamente ( (val - start) % step , pero con cierta complejidad adicional para lidiar con pasos negativos) que generar y probar todos los valores, entonces ¿por qué no debería hacerlo? es la mejor manera?

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

Si range realmente fuera 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 obvio. Si ya ha iterado los primeros 3 valores, ¿está todavía 1 in el generador? ¿Deben las pruebas para 1 hacer que itere y consuma todos los valores hasta 1 (o hasta el primer valor >= 1 )?

El objeto range() Python 3 no produce números de inmediato; 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 constante O (1). Nunca es necesario escanear todos los enteros posibles en el rango.

De 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 (pequeña) de memoria, sin importar el tamaño del rango que representa (ya que solo almacena los valores de start , stop y step , calcular elementos individuales y subranges 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 varias cosas que admite un range() real range() (como los .index() o .count() , hashing, pruebas de igualdad o segmentación), pero deberían darle una idea.

También simplifiqué la implementación de __contains__ para centrarme solo en pruebas de enteros; si le da a un objeto range() real un valor no entero (incluidas las subclases de int ), se inicia una exploración lenta para ver si hay una coincidencia, al igual que si utiliza 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 también admitan la aritmética de enteros. Vea el problema original de Python que implementó la prueba de contención.

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 se puede usar muchas veces (incluso al iterar sobre él), no solo un generador de una sola vez.

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 objetos PyLong (que es int en Python 3), usará 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 , recurre a iterar hasta que encuentre 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

Se trata de un enfoque perezoso para la evaluación y una optimización adicional del range . Los valores en rangos no necesitan ser calculados hasta el uso real, o incluso más debido a una 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 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 confiar en ellos, ya que esto puede cambiar en el futuro.

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 3.2 , pero no se realizó un backport a 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 fuera en ese punto).

Mientras tanto:

Originalmente, xrange era un objeto que no era de secuencia completa. Como dicen los documentos 3.1 :

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 realidad soportaba 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 hacerlas secuencias completas en ese momento.

Luego, como parte de la implementación del PEP de las clases base abstractas , era importante determinar qué tipos incorporados deberían marcarse como implementando qué ABC y xrange / range afirmaban implementar collections.Sequence xrange , a pesar de que todavía solo manejaba el mismo "muy poco comportamiento ". Nadie notó ese problema hasta el número 9213 . El parche para ese problema no solo agregó index y count al range de 3.2, sino que también reestructuró las __contains__ optimizadas (que comparte la misma matemática con el index y se utiliza directamente por count ). ** Este cambio también entró en 3.2, y no fue retrocedido 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).

Por lo tanto, hubo dos oportunidades para que esta optimización se transfiriera a 2.7, pero ambos fueron rechazados.

* De hecho, incluso obtienes iteraciones gratis solo con indexación, pero en 2.3 xrange objetos tienen un iterador personalizado.

** 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 del parche de Daniel Stutzbach restauró la mayor parte del código anterior, incluido el retroceso al _PySequence_IterSearch genérico y lento que el range.__contains__ anterior a 3.2 range.__contains__ se usaba implícitamente cuando la optimización no se aplica.

Aquí está la implementación en C# . Puede ver cómo funciona Contains en el tiempo O (1).

public struct Range { private readonly int _start; private readonly int _stop; private readonly int _step; // other members omitted for brevity public bool Contains(int number) { // precheck - if the number is not in a valid step point, return false // for example, if start=5, step=10, stop=1000, it is obvious that 163 is not in this range (due to remainder) if ((_start % _step + _step) % _step != (number % _step + _step) % _step) return false; // with the help of step sign, we can check borders in linear manner int s = Math.Sign(_step); // no need if/else to handle both cases - negative and positive step return number * s >= _start * s && number * s < _stop * s; } }