Jiang Jie Jiang Jie - 2 months ago 6x
Python Question

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

Consider a python line:


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?


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];
            dest[i] = it;

        return result;