CODEWITHSUNDEEP
pythonslicereverse
jerrypy
jerrypy

Reputation: 139

How does Python implement str[::-1]?

Consider a python line:

str[::-1]

I see it's very fast, and way more faster than some O(n) solution and also memory saving. What algorithm does Python use in this case?

Upvotes: 2

Views: 337

Answers (2)

Daniel
Daniel

Reputation: 2469

You can use Python's dis.dis module to disassemble str[::-1]:

>>> import dis
>>> def reverse_(str_):
...     return str_[::-1]
...
>>> dis.dis(reverse_)
  6           0 LOAD_FAST                0 (str_)
              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

You can see what each instruction means in the documentation. For LOAD_FAST the docs say:

Pushes a reference to the local co_varnames[var_num] onto the stack.

co_varnames is a structure that is always present with a code object. In this case, it is str_:

>>> reverse_.__code__.co_varnames
('str_',)

The next instruction, LOAD_CONST, is described like this:

Pushes co_consts[consti] onto the stack.

The value that was pushed onto the stack is None (dis is helpful and looked it up for you). The next two instructions are LOAD_CONST instructions that push the values None and -1 onto the stack.

The next instruction, BUILD_SLICE, is described as:

Pushes a slice object on the stack. argc must be 2 or 3. If it is 2, slice(TOS1, TOS) is pushed; if it is 3, slice(TOS2, TOS1, TOS) is pushed. See the slice() built-in function for more information.

TOS2, TOS1, TOS represent the values on the stack None, None, -1, which are pushed to the slice() object from the stack (the object becomes slice(None, None, -1)).

BINARY_SUBSCR is described as:

Implements TOS = TOS1[TOS].

This means that Python computes str_[sli] where sli is the slice() object pushed to the stack in the previous instruction. It's the equivalent of

>>> str_[slice(None, None, -1)]

Finally, RETURN_VALUE:

Returns with TOS to the caller of the function.

The last instruction returns the result of the previous step, which is the reversed str_.

Summary

I see it's very fast, and way more faster than some O(n) solution and also memory saving.

In fact, reversing a list by slicing involves more memory overhead than some other reversal methods in Python. Long story short (and without going down a long rabbit hole), the greater memory overhead occurs because the slicing operation returns a whole list.

One alternative method might be: generating an iterator using reversed(), which is usually more performant for memory and time (although, generating a list from this iterator is time-consuming).

What algorithm does Python use in this case?

To make a long story short: Python loads the variable str, builds a slice(None, None, -1) object, implements str[slice(None, None, -1)] (source code), and returns the reversed str.

Upvotes: 2

juanpa.arrivillaga
juanpa.arrivillaga

Reputation: 96172

Hmm, have you tried any quick-and-dirty tests? Here is a first-pass:

In [1]: import time

In [2]: def reverse_list_time(my_list):
   ...:     start  = time.time()
   ...:     reversed = my_list[::-1]
   ...:     stop = time.time()
   ...:     return stop - start
   ...: 

In [3]: reverse_list_time(list(range(1000)))
Out[3]: 1.33514404296875e-05

In [4]: testing_lists = (list(range(n)) for n in range(1000,100000,500))

In [5]: testing_lists
Out[5]: <generator object <genexpr> at 0x7f7786bd97d8>

In [6]: results = list(map(reverse_list_time,testing_lists))

And here are my results

enter image description here

That looks roughly O(n) to me.

If that doesn't convince you, here is the implementation. It looks like a pretty straight forward O(n) solution to me. This is the meat of it:

    else {
        result = PyList_New(slicelength);
        if (!result) return NULL;

        src = self->ob_item;
        dest = ((PyListObject *)result)->ob_item;
        for (cur = start, i = 0; i < slicelength;
             cur += step, i++) {
            it = src[cur];
            Py_INCREF(it);
            dest[i] = it;
        }

        return result;

Upvotes: 3

Related Questions