not - xrange python 3




Perché "1000000000000000 nel range(1000000000000001)" è così veloce in Python 3? (6)

TL; DR

L'oggetto restituito da range() è in realtà un oggetto range . Questo oggetto implementa l'interfaccia iteratore in modo da poter scorrere i suoi valori in sequenza, proprio come un generatore, ma implementa anche l'interfaccia __contains__ che è in realtà ciò che viene chiamato quando un oggetto appare sul lato destro dell'operatore in. Il __contains__() restituisce un valore booleano se l'oggetto si trova o meno nell'oggetto. Poiché gli oggetti range conoscono i loro limiti e il passo, questo è molto facile da implementare in O (1).

Comprendo che la funzione range() , che in realtà è un tipo di oggetto in Python 3 , genera il suo contenuto al volo, in modo simile a un generatore.

Stando così le cose, mi sarei aspettato che la seguente riga impiegasse una quantità eccessiva di tempo, perché per determinare se 1 quadrilione è compreso nell'intervallo, sarebbe necessario generare un quadrilione di valori:

1000000000000000 in range(1000000000000001)

Inoltre: sembra che non importa quanti zeri aggiungo, il calcolo richiede più o meno la stessa quantità di tempo (sostanzialmente istantaneo).

Ho anche provato cose del genere, ma il calcolo è ancora quasi istantaneo:

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

Se provo ad implementare la mia funzione di intervallo, il risultato non è così bello !!

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

Cosa sta facendo l'oggetto range() sotto il cofano che lo rende così veloce?

La risposta di Martijn Pieters è stata scelta per la sua completezza, ma vedi anche la prima risposta di abarnert per una buona discussione di cosa significhi per il range essere una sequenza a pieno titolo in Python 3 e alcune informazioni / avvertenze riguardo a potenziali incoerenze per l'ottimizzazione della funzione __contains__ Implementazioni Python. L'altra risposta di abarnert va in qualche dettaglio in più e fornisce collegamenti per coloro che sono interessati alla storia dietro l'ottimizzazione in Python 3 (e la mancanza di ottimizzazione di xrange in Python 2). Le risposte di poke e di wim forniscono il codice sorgente C e le spiegazioni pertinenti per coloro che sono interessati.


Il fraintendimento fondamentale qui è nel pensare che la range sia un generatore. Non è. In realtà, non è alcun tipo di iteratore.

Puoi dirlo abbastanza facilmente:

>>> a = range(5)
>>> print(list(a))
[0, 1, 2, 3, 4]
>>> print(list(a))
[0, 1, 2, 3, 4]

Se fosse un generatore, iterarlo una volta lo esaurirebbe:

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

Che cosa è effettivamente l' range , è una sequenza, proprio come un elenco. Puoi persino provare questo:

>>> import collections.abc
>>> isinstance(a, collections.abc.Sequence)
True

Ciò significa che deve seguire tutte le regole per essere una sequenza:

>>> 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 differenza tra un range e un list è che un range è una sequenza pigra o dinamica ; non ricorda tutti i suoi valori, si ricorda solo di start , stop e step e crea i valori su richiesta su __getitem__ .

(Come nota a listiterator , se print(iter(a)) , noterai che range usa lo stesso tipo di listiterator di list . Come funziona? Un listiterator non usa nulla di speciale su list tranne che per il fatto che fornisce un'implementazione C di __getitem__ , quindi funziona bene anche per l' range .)

Ora, non c'è nulla che dica che la Sequence.__contains__ deve essere un tempo costante - in effetti, per ovvi esempi di sequenze come la list , non lo è. Ma non c'è nulla che dica che non può essere. Ed è più facile implementare l' range.__contains__ controllarlo matematicamente ( (val - start) % step , ma con una certa complessità in più per gestire i passaggi negativi) piuttosto che generare e testare tutti i valori, quindi perché non dovrebbe farlo? è il modo migliore?

Ma non sembra esserci nulla nella lingua che garantisca che ciò accada. Come sottolinea Ashwini Chaudhari, se gli dai un valore non integrale, invece di convertirlo in intero e fare il test matematico, tornerà a iterare tutti i valori e confrontarli uno per uno. E solo perché le versioni di CPython 3.2+ e PyPy 3.x contengono questa ottimizzazione, ed è una buona idea ovvia e facile da fare, non c'è motivo per cui IronPython o NewKickAssPython 3.x non possano lasciarlo fuori. (E in effetti CPython 3.0-3.1 non lo includeva.)

Se il range fosse effettivamente un generatore, come my_crappy_range , non avrebbe senso testare __contains__ questo modo, o almeno il modo in cui ha senso non sarebbe ovvio. Se avessi già ripetuto i primi 3 valori, 1 è ancora in generatore? Il test per 1 dovrebbe far iterare e consumare tutti i valori fino a 1 (o fino al primo valore >= 1 )?


Le altre risposte lo hanno già spiegato bene, ma vorrei offrire un altro esperimento che illustra la natura degli oggetti range:

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

Come puoi vedere, un oggetto range è un oggetto che ricorda il suo range e può essere usato molte volte (anche se iterando su di esso), non solo un generatore una tantum.


Per aggiungere alla risposta di Martijn, questa è la parte rilevante della fonte (in C, poiché l'oggetto range è scritto in codice 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);
}

Quindi, per PyLong oggetti PyLong (che è int in Python 3), utilizzerà la funzione range_contains_long per determinare il risultato. E quella funzione controlla essenzialmente se ob è nell'intervallo specificato (anche se sembra un po 'più complesso in C).

Se non è un oggetto int , ritorna all'iterazione fino a quando non trova il valore (o meno).

L'intera logica potrebbe essere tradotta in pseudo-Python in questo modo:

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 tratta di un approccio pigro alla valutazione e di un'ulteriore ottimizzazione della range . I valori negli intervalli non devono essere calcolati fino a quando non vengono utilizzati o addirittura ulteriormente a causa di un'ulteriore ottimizzazione.

A proposito, il tuo numero intero non è così grande, considera sys.maxsize

sys.maxsize in range(sys.maxsize) è piuttosto veloce

grazie all'ottimizzazione - è facile confrontare un dato numero intero solo con il minimo e il massimo dell'intervallo.

ma:

float(sys.maxsize) in range(sys.maxsize) è piuttosto lento .

(in questo caso, non c'è ottimizzazione range , quindi se python riceve un float inaspettato, python confronterà tutti i numeri)

È necessario essere consapevoli di un dettaglio dell'implementazione, ma non si deve fare affidamento su di esso, perché ciò potrebbe cambiare in futuro.


Usa la source , Luke!

In CPython, l' range(...).__contains__ (un wrapper di metodo) alla fine verrà delegato a un semplice calcolo che verifica se il valore può essere compreso nell'intervallo. La ragione della velocità qui sta usando un ragionamento matematico sui limiti, piuttosto che un'iterazione diretta dell'oggetto range . Per spiegare la logica utilizzata:

  1. Verificare che il numero sia compreso tra start e stop e
  2. Verifica che il valore del passo non "passi" sul nostro numero.

Ad esempio, 994 è range(4, 1000, 2) perché:

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

Di seguito è incluso il codice C completo, che è un po 'più dettagliato a causa della gestione della memoria e dei dettagli del conteggio dei riferimenti, ma l'idea di base è lì:

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" dell'idea è menzionata nella riga :

/* result = ((int(ob) - start) % step) == 0 */ 

Come nota finale, osserva la funzione range_contains nella parte inferiore dello snippet di codice. Se l'esatto controllo del tipo fallisce, allora non usiamo l'algoritmo intelligente descritto, ma torniamo a una muta ricerca iterativa dell'intervallo usando _PySequence_IterSearch ! Puoi controllare questo comportamento nell'interprete (sto usando la v3.5.0 qui):

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




python-internals