7

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?

durden2.0
  • 9,222
  • 9
  • 44
  • 57
  • As a side note, I didn't have to put these operations into a method in order to use the `dis` module. [This post](http://stackoverflow.com/questions/13270888/why-is-startswith-slower-than-slicing) has a nice little `lambda` than compiles the code string first (required) then passes it to `dis.dis`. – durden2.0 May 09 '13 at 15:17

3 Answers3

14

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
Ashwini Chaudhary
  • 244,495
  • 58
  • 464
  • 504
7

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
Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
0

reversed() doesn't actually reverse anything, it merely returns an object that can be used to iterate over the container's elements in reverse order. This is why it is faster than actually reversing the elements.

Note that you have also reverse() that is doing the same as slicing operator.

reverse() operates in place. slicing operator returns a list object.

kiriloff
  • 25,609
  • 37
  • 148
  • 229