Tengo entendido que la función range()
, que en realidad es un tipo de objeto en Python 3, genera su contenido 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 desmesurada, 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 añada, el cálculo tarda más o menos lo mismo (básicamente es instantáneo).
También he probado cosas como ésta, 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 agradable!!!
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?
Martijn Pieters' respuesta fue elegida por su integridad, pero también ver abarnert'primera respuesta para una buena discusión de lo que significa que range
sea una secuencia de pleno derecho en Python 3, y alguna información/advertencia sobre la potencial inconsistencia para la optimización de la función __contains__
a través de las implementaciones de Python. La otra respuesta de abarnert entra en más detalles y proporciona enlaces para los interesados en la historia 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 en C relevante y explicaciones para aquellos que estén interesados.
El objeto range()
de Python 3 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, parada y paso, y luego, al iterar sobre el objeto, se calcula el siguiente entero en cada iteración.
El objeto también implementa el gancho object.__contains__
, y calcula si tu número es parte de su rango. El cálculo es una operación de tiempo constante O(1). Nunca hay necesidad de escanear todos los posibles enteros en el rango.
De la documentación del objeto range()
:
La ventaja del tipo
range
sobre unalista
otupla
normal es que un objeto range siempre ocupará la misma (pequeña) cantidad de memoria, sin importar el tamaño del rango que representa (ya que sólo almacena los valoresstart
,stop
ystep
, calculando los elementos individuales y los subrangos según sea necesario).
Así que, como mínimo, tu objeto range()
servirí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 le faltan varias cosas que soporta un verdadero range()
(como los métodos .index()
o .count()
, hashing, pruebas de igualdad, o slicing), pero debería darte una idea.
También he simplificado la implementación de __contains__
para centrarse sólo en las pruebas de enteros; si le das a un objeto real de range()
un valor no entero (incluyendo las subclases de int
), se inicia un lento escaneo para ver si hay una coincidencia, al igual que si utilizas una prueba de contención contra una lista de todos los valores contenidos. Esto se ha hecho para seguir soportando otros tipos numéricos que casualmente soportan la prueba de igualdad con enteros pero que no se espera que soporten también la aritmética de enteros. Ver el original Python issue que implementó la prueba de contención.
¡Usa la fuente, Luke!
En CPython, range(...).__contains__
(un método envolvente) acabará delegando en un simple cálculo que comprueba si el valor puede estar dentro del 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 range. Para explicar la lógica utilizada:
inicio
y parada
, yPor ejemplo, 994
está en range(4, 1000, 2)
porque:
4 <= 994 < 1000
, y(994 - 4) % 2 == 0
.A continuación se incluye el código C completo, que es un poco más prolijo 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 - mira la función range_contains
al final del fragmento de código. Si la comprobación del tipo exacto falla, entonces no utilizamos el algoritmo inteligente descrito, sino que volvemos a una muda búsqueda por iteración del rango utilizando _PySequence_IterSearch
. Puedes comprobar este comportamiento en el intérprete (aquí estoy usando la versión 3.5.0):
>>> 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 encontrar el valor (o no).
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