Jiang Jie Jiang Jie - 4 months ago 8
Python Question

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?

Answer

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;
Comments