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;

Answer 2

可以使用Python的dis.dis模块反汇编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

您可以在 documentation. For LOAD_FAST 文档中查看每条指令的含义：

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

co_varnames 是一个总是与代码对象一起出现的结构。在这种情况下，它是 str_:

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

下一条指令，LOAD_CONST，描述如下：

Pushes co_consts[consti] onto the stack.

压入栈的值是None（dis有帮助，帮你查了下）。接下来的两条指令是 LOAD_CONST 指令，它们将值 None 和 -1 压入堆栈。

下一条指令，BUILD_SLICE，描述为：

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表示栈None, None, -1上的值，从栈中push到slice()对象（对象变为slice(None, None, -1)）。

BINARY_SUBSCR描述为：

Implements TOS = TOS1[TOS].

这意味着 Python 计算 str_[sli] 其中 sli 是在上一条指令中压入堆栈的 slice() 对象。相当于

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

最后，RETURN_VALUE：

Returns with TOS to the caller of the function.

最后一条指令returns上一步的结果，也就是反转的str_。

总结

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

事实上，通过切片反转列表比 Python 中的一些其他反转方法涉及更多的内存开销。长话短说（并且没有进入一个长长的兔子洞），更大的内存开销是因为切片操作 returns 整个列表。

另一种方法可能是：使用 reversed() 生成迭代器，这通常在内存和时间方面更高效（尽管从该迭代器生成列表很耗时）。

What algorithm does Python use in this case?

长话短说：Python 加载变量 str，构建一个 slice(None, None, -1) 对象，实现 str[slice(None, None, -1)] (source code)，然后returns 反转 str.

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

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

python

reverse

slice

总结