python - Python是如何实现str[::-1]的？

Question

考虑一条 python 行:

str[::-1]

我发现它非常快，比某些O(n) 解决方案要快得多，而且还可以节省内存。 Python 在这种情况下使用什么算法？

Answer 1

嗯，你有没有尝试过任何快速和肮脏的测试？这是第一遍:

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))

这是我的结果

对我来说，这看起来大致是 O(n)。

如果这不能说服您，这里是 the implementation .对我来说，它看起来像是一个非常直接的 O(n) 解决方案。这是它的核心:

    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;