Perché è invertire una lista con slicing più lento di iteratore inverso

Question

Ci sono almeno due modi per invertire una lista in Python, ma l'approccio iteratore è molto più veloce (almeno in Python 2.7.x). Voglio capire cosa contribuisce a questa differenza di velocità.

>>> x = range(1000) 
>>> %timeit x[::-1] 
100000 loops, best of 3: 2.99 us per loop 
>>> %timeit reversed(x) 
10000000 loops, best of 3: 169 ns per loop 

ho il sospetto la differenza di velocità è dovuta almeno i seguenti:

1. reversed è scritto in C
2. reversed è un iteratore, quindi meno overhead di memoria

I ho provato ad usare il modulo dis per avere una visione migliore di queste operazioni, ma non è stato di grande aiuto. Ho dovuto mettere queste operazioni in una funzione per smontarle.

>> def reverselist(_list): 
...  return _list[::-1] 
... 
>>> dis.dis(reverselist) 
    2   0 LOAD_FAST    0 (_list) 
       3 LOAD_CONST    0 (None) 
       6 LOAD_CONST    0 (None) 
       9 LOAD_CONST    1 (-1) 
      12 BUILD_SLICE    3 
      15 BINARY_SUBSCR  
      16 RETURN_VALUE 
>>> def reversed_iter(_list): 
...  return reversed(_list) 
... 
>>> dis.dis(reversed_iter) 
    2   0 LOAD_GLOBAL    0 (reversed) 
       3 LOAD_FAST    0 (_list) 
       6 CALL_FUNCTION   1 
       9 RETURN_VALUE   

Che cosa tutto accade esattamente durante un'operazione di affettamento, c'è un sacco di overhead di memoria? Forse slicing è implementato in puro Python?

Answer 1

Questo perché reversed restituisce un iterator mentre l'affettatura restituisce un intero elenco.

>>> lis = range(10) 
>>> lis[::-1] 
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 
>>> reversed(lis) 
<listreverseiterator object at 0x909dd0c> 

hai utilizzare per convertire list() che iteratore in un intero elenco:

>>> lis = range(10**5) 
>>> %timeit lis[::-1] 
100 loops, best of 3: 2.8 ms per loop 
>>> %timeit list(reversed(lis)) 
100 loops, best of 3: 3.13 ms per loop 

Aiuto su reversed:

>>> reversed? 
Type:  type 
String Form:<type 'reversed'> 
Namespace: Python builtin 
Docstring: 
reversed(sequence) -> reverse iterator over values of the sequence 

Return a reverse iterator 

Answer 2

reversed() restituisce un iteratore. Non è in realtà invertire nulla finché non si esegue il ciclo su di esso. Dal documentation:

ritorno un inverso iterator.

è necessario confrontare il tempo necessario per trasformare il risultato di reversed() in una lista di nuovo:

%timeit list(reversed(x)) 

Creazione solo l'iteratore (che non è altro che un riferimento alla lista originale e una voce puntatore inizializzato alla lunghezza dell'elenco) non richiede assolutamente alcun tempo.

dover girare reversed() di nuovo in un elenco rende un molto più lento:

>>> import timeit 
>>> x = range(1000) 
>>> timeit.timeit('x[::-1]', 'from __main__ import x') 
4.623600006103516 
>>> timeit.timeit('list(reversed(x))', 'from __main__ import x') 
16.647125005722046 

Answer 3

reversed() in realtà non invertire nulla, è semplicemente restituisce un oggetto che può essere utilizzato per iterare gli elementi del contenitore in ordine inverso. Questo è il motivo per cui è più veloce di invertire effettivamente gli elementi.

Nota che hai anche reverse() che sta facendo lo stesso di slicing operator.

reverse() funziona sul posto. l'operatore slicing restituisce un oggetto lista.