Coder Perfect

What is the best way to reverse a list?

Problem

In Python, how can I perform the following?

array = [0, 10, 20, 40]
for (i = array.length() - 1; i >= 0; i--)

I need all of the items of an array, but from beginning to end.

Asked by Leo.peis

Solution #1

You can make use of the reversed function for this as:

>>> array=[0,10,20,40]
>>> for i in reversed(array):
...     print(i)

It’s worth noting that reversed(…) does not provide a list. list(reversed(array)) can be used to create a reversed list.

Answered by codaddict

Solution #2

>>> L = [0,10,20,40]
>>> L[::-1]
[40, 20, 10, 0]

The Python What’s new entry for release 2.3.5 explains extended slice syntax in detail.

This is the most recent slice documentation, as requested in a remark.

Answered by mechanical_meat

Solution #3

>>> L = [0,10,20,40]
>>> L.reverse()
>>> L
[40, 20, 10, 0]

Or

>>> L[::-1]
[40, 20, 10, 0]

Answered by ghostdog74

Solution #4

There are three built-in options for reversing a list. Which strategy is best is determined by whether you must:

When reversing a list, it’s recommended to use the built-in functions mentioned above. When compared to a manually generated loop or generator, they are 2 to 8 times faster on short lists (10 items) and up to 300 times faster on long lists. This makes sense because they’re written in a native language (i.e. C), they’re created by specialists, and they’re scrutinized and optimized. They’re also less prone to errors and better at dealing with edge and corner instances.

Combine all of the code snippets in this answer to create a script that will do the various methods of reversing a list explained below. Each method will be timed and executed 100,000 times. The findings for lists of lengths of 2, 10, and 1000 items are provided in the last section.

from timeit import timeit
from copy import copy

def time_str_ms(t):
    return '{0:8.2f} ms'.format(t * 1000)

Use the list> if all you want to do is reverse the order of items in an existing list without looping through them or creating a copy to work with. reverse() is a function that reverses the direction of an object. If you run this on a list object directly, the order of all entries will be reversed:

It’s worth noting that the following will reverse the original variable, even if it also returns the reversed list. Using the output of this function, you can make a copy. Normally, you wouldn’t create a function for something like this, but the timing script does.

We compare the performance of two methods: first, reversing a list in place (which affects the original list), and then copying and reversing the list afterward to see which is the fastest approach to make a reversed copy.

def rev_in_place(mylist):
    mylist.reverse()
    return mylist

def rev_copy_reverse(mylist):
    a = copy(mylist)
    a.reverse()
    return a

You can duplicate a portion of any indexed object using the built-in index slicing technique.

Object>[first index:last index:step] is the generic syntax. Use the following syntax to build a simple reversed list using slicing: list> [::-1]. When you leave an option blank, it defaults to the first and last elements of the object’s first and last elements (reversed if the step size is negative).

Negative numbers can be used in indexing since they count backwards from the end of the object’s index (i.e. -2 is the second to last item). When the step size is negative, it will index backward by that amount, starting with the last item.

def rev_slice(mylist):
    a = mylist[::-1]
    return a

There is a function called reversed(indexed object):

Test with a raw iterator as well as a list created from the iterator.

def reversed_iterator(mylist):
    a = reversed(mylist)
    return a

def reversed_with_list(mylist):
    a = list(reversed(mylist))
    return a

Creating your own indexing methods is a bad idea, as the timeframe demonstrates. Unless you have a specific requirement for something custom, use the built-in techniques. This merely entails becoming familiar with the built-in procedures.

With lesser list sizes, the penalty isn’t as severe, but as the list size grows, the penalty becomes much more severe. I’m sure the code below could be improved, but it’ll never be able to match the built-in methods because they’re implemented in a native language.

def rev_manual_pos_gen(mylist):
    max_index = len(mylist) - 1
    return [ mylist[max_index - index] for index in range(len(mylist)) ]

def rev_manual_neg_gen(mylist):
    ## index is 0 to 9, but we need -1 to -10
    return [ mylist[-index-1] for index in range(len(mylist)) ]

def rev_manual_index_loop(mylist):
    a = []
    reverse_index = len(mylist) - 1
    for index in range(len(mylist)):
        a.append(mylist[reverse_index - index])
    return a

def rev_manual_loop(mylist):
    a = []
    reverse_index = len(mylist)
    for index, _ in enumerate(mylist):
        reverse_index -= 1
        a.append(mylist[reverse_index])
    return a

The rest of the script to time each technique of reversing is as follows. It demonstrates that reversing in place with obj.reverse() and producing the reversed(obj) iterator are always the slowest, although creating a copy with slices is the fastest.

It also shows that you shouldn’t try to figure it out on your own unless you absolutely have to!

loops_to_test = 100000
number_of_items = 10
list_to_reverse = list(range(number_of_items))
if number_of_items < 15:
    print("a: {}".format(list_to_reverse))
print('Loops: {:,}'.format(loops_to_test))
# List of the functions we want to test with the timer, in print order
fcns = [rev_in_place, reversed_iterator, rev_slice, rev_copy_reverse,
        reversed_with_list, rev_manual_pos_gen, rev_manual_neg_gen,
        rev_manual_index_loop, rev_manual_loop]
max_name_string = max([ len(fcn.__name__) for fcn in fcns ])
for fcn in fcns:
    a = copy(list_to_reverse) # copy to start fresh each loop
    out_str = ' | out = {}'.format(fcn(a)) if number_of_items < 15 else ''
    # Time in ms for the given # of loops on this fcn
    time_str = time_str_ms(timeit(lambda: fcn(a), number=loops_to_test))
    # Get the output string for this function
    fcn_str = '{}(a):'.format(fcn.__name__)
    # Add the correct string length to accommodate the maximum fcn name
    format_str = '{{fx:{}s}} {{time}}{{rev}}'.format(max_name_string + 4)
    print(format_str.format(fx=fcn_str, time=time_str, rev=out_str))

Scaling works better with built-in mechanisms that are most suited for a specific sort of reversing, according to the findings. To put it another way, when the number of object elements grows, the built-in techniques outperform the other ways even more.

Stringing things together is better than using the built-in function that directly does what you require. If you need a copy of the reversed list, slicing is optimal – it’s faster than constructing a duplicate list from the list(reversed(obj)) method, and faster than making a copy of the list and then doing an in-place obj.reverse(), but never by more than twice as fast. Meanwhile, with big lists, specialized techniques can take orders of magnitude longer.

For scaling, with a 1000 item list, the reversed() function call takes ~30 ms to setup the iterator, reversing in-place takes just ~55 ms, using the slice method takes ~210 ms to create a copy of the full reversed list, but the quickest manual method I made took ~8400 ms.

There are two items on the list:

a: [0, 1]
Loops: 100,000
rev_in_place(a):             24.70 ms | out = [1, 0]
reversed_iterator(a):        30.48 ms | out = <list_reverseiterator object at 0x0000020242580408>
rev_slice(a):                31.65 ms | out = [1, 0]
rev_copy_reverse(a):         63.42 ms | out = [1, 0]
reversed_with_list(a):       48.65 ms | out = [1, 0]
rev_manual_pos_gen(a):       98.94 ms | out = [1, 0]
rev_manual_neg_gen(a):       88.11 ms | out = [1, 0]
rev_manual_index_loop(a):    87.23 ms | out = [1, 0]
rev_manual_loop(a):          79.24 ms | out = [1, 0]

There are ten entries on the list:

rev_in_place(a):             23.39 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
reversed_iterator(a):        30.23 ms | out = <list_reverseiterator object at 0x00000290A3CB0388>
rev_slice(a):                36.01 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_copy_reverse(a):         64.67 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
reversed_with_list(a):       50.77 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_manual_pos_gen(a):      162.83 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_manual_neg_gen(a):      167.43 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_manual_index_loop(a):   152.04 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_manual_loop(a):         183.01 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

And here’s what the list looks like with 1000 things on it:

rev_in_place(a):             56.37 ms
reversed_iterator(a):        30.47 ms
rev_slice(a):               211.42 ms
rev_copy_reverse(a):        295.74 ms
reversed_with_list(a):      418.45 ms
rev_manual_pos_gen(a):     8410.01 ms
rev_manual_neg_gen(a):    11054.84 ms
rev_manual_index_loop(a): 10543.11 ms
rev_manual_loop(a):       15472.66 ms

Answered by LightCC

Solution #5

Using slicing, such as array = array[::-1], is a useful trick that is extremely Pythonic, although it may be a little confusing for newcomers. Because it is easily legible, using the reverse() function is a nice way to go in day-to-day code.

However, you won’t be able to use built-in methods like these if you need to reverse a list in situ, such as in an interview question. An algorithmic approach is necessary, as the interviewer will be looking at how you approach the problem rather than your depth of Python knowledge. One method to achieve it is to use the following example, which uses a classic swap:-

def reverse_in_place(lst):      # Declare a function
    size = len(lst)             # Get the length of the sequence
    hiindex = size - 1
    its = size/2                # Number of iterations required
    for i in xrange(0, its):    # i is the low index pointer
        temp = lst[hiindex]     # Perform a classic swap
        lst[hiindex] = lst[i]
        lst[i] = temp
        hiindex -= 1            # Decrement the high index pointer
    print "Done!"

# Now test it!!
array = [2, 5, 8, 9, 12, 19, 25, 27, 32, 60, 65, 1, 7, 24, 124, 654]

print array                    # Print the original sequence
reverse_in_place(array)        # Call the function passing the list
print array                    # Print reversed list


**The result:**
[2, 5, 8, 9, 12, 19, 25, 27, 32, 60, 65, 1, 7, 24, 124, 654]
Done!
[654, 124, 24, 7, 1, 65, 60, 32, 27, 25, 19, 12, 9, 8, 5, 2]

Note that this will not work on Tuples or string sequences, because strings and tuples are immutable, i.e., you cannot write into them to change elements.

Answered by SimonM

Post is based on https://stackoverflow.com/questions/3940128/how-to-reverse-a-list