Why is reversing a list with slicing slower than reverse iterator

Question

There are at least two ways to reverse a list in Python, but the iterator approach is much faster (at least in Python 2.7.x). I want to understand what contributes to this speed difference.

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

I suspect the speed difference is due to at least the following:

1. reversed is written in C
2. reversed is an iterator, so less memory overhead

I tried to use the dis module to get a better view of these operations, but it wasn't too helpful. I had to put these operations in a function to disassemble them.

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

What all exactly happens during a slicing operation, is there a lot of memory overhead? Maybe slicing is implemented in pure Python?

Answer 1

That's because reversed returns an iterator while slicing returns a whole list.

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

You've to use list() to convert that iterator into a whole list:

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

Help on 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() returns an iterator. It doesn't actually reverse anything until you loop over it. From the documentation:

Return a reverse iterator.

You need to compare the time it takes to turn the result of reversed() into a list again:

%timeit list(reversed(x))

Creating just the iterator (which is nothing but a reference to the original list and a item pointer that is initialized to the length of the list) does't take any time at all.

Having to turn reversed() back into a list makes it a lot slower:

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