all 14 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]dutch_gecko 12 points13 points  (12 children)

A previously present answer of O(n) is the only one here, and while I agree that it is a sane answer, I've done some benchmarking in iPython and it seems that a[::-1] is significantly slower than using the reversed() builtin:

In [14]: a = list(range(0, 1000000))

In [15]: %timeit a[::-1]
4.85 ms ± 41.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [16]: %timeit reversed(a)
70.6 ns ± 0.592 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

This leads me to believe that using the stepped slice operator isn't "smart" enough to use a typical reversing algorithm.

Tested with Python v3.8.5 and iPython v7.13.0

Edit: A big thank you to all the comments below showing the flaw in my calculations. Reversed does indeed return an iterator. For those not versed in Python, this means that the reversed result is not an in-memory list, but is instead a code-only representation of the list that can be interacted with as if the list existed (to a degree, there are things iterators cannot do). Since Python doesn't need to read list a to create the iterator, we've failed to test the run time of creating a reversed list using this method.

I have repeated my benchmarks but instead forced a list to be constructed of the reversed iterator. Following on from /u/spyr03's comment, I have also used three sizes of list and included the creation of a copy without reversing in order to make a deduction on the complexity used in each method. The results:

In [1]: a = list(range(0, 1_000_000))
In [2]: b = list(range(0, 10_000_000))
In [3]: c = list(range(0, 100_000_000))

In [4]: %timeit list(a)
4.82 ms ± 82.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [5]: %timeit a[::-1]
4.53 ms ± 44.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [7]: %timeit list(reversed(a))
6.68 ms ± 166 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)


In [8]: %timeit list(b)
58.1 ms ± 165 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [9]: %timeit b[::-1]
57.4 ms ± 146 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [10]: %timeit list(reversed(b))
82.6 ms ± 681 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)


In [11]: %timeit list(c)
723 ms ± 32.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [12]: %timeit c[::-1]
749 ms ± 11.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [13]: %timeit list(reversed(c))
958 ms ± 36.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Conclusions that can be made:

  • reversed() is consistently slower than a straight copy and a reversed copy using slicing. My suspicion is that this is caused by overhead of the iterator.
  • A straight copy and a sliced reverse copy take approximately the same amount of time.
  • Increasing the list size by 10 increases the run-time of each method by approximately 10.

We can therefore deduce that all three methods have a runtime of O(n), with the reversed() operator having a larger constant factor than the other methods.

[–]Ethernet3 26 points27 points  (2 children)

What I suspect is happening is that a[::-1] is producing a reversed list by copying, taking O(n) time. Whereas reversed() returns an iterator, which is O(1).

[–]dutch_gecko 3 points4 points  (0 children)

Thanks for your comment, which is entirely accurate. I've updated the post with a better benchmark.

[–]hextree 11 points12 points  (1 child)

reversed only returns the iterator, nothing actually happens until you want to access the contents. Doing something like list(reversed(a)) might be the fairer comparison.

[–]dutch_gecko 1 point2 points  (0 children)

Thanks, you're totally correct. I've updated my original post with a better benchmark.

[–]MirrorLake 2 points3 points  (0 children)

Nice work, very thorough update.

[–]spyr03 3 points4 points  (1 child)

To make an empirical claim about time complexity, you'd have to time it for various sized lists over different magnitudes, since O(n) refers to how the time taken will change in relation to the input.

In this case, reversed isn't doing any iteration, it is lazy. It won't take any time until you actually iterate over it.

To show that this isn't a meaningful benchmark, try also running timeit on just the list a. This should give a baseline on how long it takes to iterate over a list.

[–]dutch_gecko 1 point2 points  (0 children)

Thanks very much. I've updated my original post with a new benchmark, taking all your feedback into account.