Is it cheaper to reverse an appended list or to prepend a list? - python

Question

Which is faster and more pythonic?

• reverse an appended list
• start prepending the list from the start
• using deque

E.g. here's ome made-up data to store into a new list

# Let's say my function outputs these output individually.
x = [12,34,44,346,345,876,123]

Reversing an appended list:

new_list = []
for i in x:
  new_list.append(i)
new_list = newlist[::-1]

Prepending to the list:

new_list = [] 
for i in x:
  new_list.insert(0,i)

Using deque:

from collections import deque
for i in x:
  x.appendleft(i)

Please note that my question is not how to reverse list. Please also assume that the list is of size ~20,000.

Fredenburg

Why not timeit and see? – Pudens

Any specific reason you don't want to use a deque? – Simp

Rather than a for loop, you could directly use new_list = x[::-1], or new_list = list(x)[::-1] if x isn't a list, or loop over reversed(list(x)) if you don't actually need a list out of this. – Fleta

@jonrsharpe, I have timeit but it's quite similar... – Fredenburg

list(reversed(x)) would be the fastest – Aglitter

@user2357112, because the function was yielding, i'm not sure whether realizing a list and reversing is faster than prepending. – Fredenburg

inserting is always going to be very slow, you have to repeatedly move all elements on each insertion – Aglitter

@alvas: You must have timed it wrong, then, because the difference is enormous. – Fleta

first example 1.69 ms second 128 ms list(reversed) 129 µs on 20k element list – Aglitter

@PadraicCunningham: You can't call reversed on arbitrary iterables, though. – Fleta

@user2357112, I don't get what you mean, list(reversed(x)) returns a reversed list – Aglitter

@PadraicCunningham: But x is a generator. You can't call reversed on that. – Fleta

@Fleta where does it say x is a generator? – Aglitter

@PadraicCunningham: One of alvas's comments says "because the function was yielding, i'm not sure whether realizing a list and reversing is faster than prepending." That seems to indicate it's a generator. For a list, x[::-1] outperforms list(reversed(x)). – Fleta

@user2357112, you are right, either way reversing would be considerably faster than inserting – Aglitter

The deque is going to be much faster than either of the alternatives; O(1) appendleft operations are pretty much the entire point of it existing... Of course, you don't say what you plan to do with this data structure after you build it. If accessing arbitrary elements by index is one of the things you want to be able to do easily, you'll lose the efficiency you got in building the thing while using it. – Simp

Answer 1

Your first method could be simplified to one line :

new_list = x[::-1]

Then, to check which method is faster than any other, just use timeit (tested with python 2.7.8) :

C:\>python -m timeit -s "x = [12,34,44,346,345,876,123]" "new_list = x[::-1]"
1000000 loops, best of 3: 0.215 usec per loop

C:\>python -m timeit -s "x = [12,34,44,346,345,876,123]; new_list = []" "for i in x:" "  new_list.insert(0,i)"
10000 loops, best of 3: 146 usec per loop

C:\>python -m timeit -s "from collections import deque; x = [12,34,44,346,345,876,123]; new_list = deque()" "for i in x:" "  new_list.appendleft(i)"
1000000 loops, best of 3: 0.713 usec per loop

C:\>python -m timeit -s "x = [12,34,44,346,345,876,123]" "new_list = list(reversed(x))"
1000000 loops, best of 3: 0.837 usec per loop

So new_list = x[::-1] is better than any other way.

You also have to ask yourself if you want to "reference" or "copy" elements into the new list structure.

Puiia

list(reverse(x)) is somewhere between method #1 and #3. – Madea

it's list(reversed(x)) I add it to the answer. – Paramedical

FYI, on my machine with python3 at least, deque is slightly faster than append and reverse (510nsec vs 674nsec). This answer short-circuits the append and reverse option (by doing a reversed copy, which is NOT the same thing in the general sense), and so does not give any timings for that scenario. – Guck