Python列表切片的空间复杂度

Question

我很难理解 Python 列表切片的空间复杂度。

对于像

arr[2:] = arr[2:][::-1]

新的空间是否为切片分配（就像在不可变字符串中所做的那样），还是在同一数组上执行操作？

对于像这样的内容：

ans = [i+1 for i in range(n)]

for i in range(k):
    ans[i:] = ans[i:][::-1]

空间复杂度会是什么？当答案是一个字符串时，它与答案是 ans = '12345...n' 时会不同吗？

- crazyy_photonn

---

回答你的第一个问题，这可能会有所帮助。 - Matthew Cassell

将切片分配给一个变量，检查并比较 id(...)。 - Patrick Artner

@Matos 很棒的发现，另一个问题的“简短回答”已经完全回答了这个问题。投票关闭。 - Patrick Artner

该链接的问题与空间复杂度或原地变异完全无关。请投票重新开放。 - MisterMiyagi

Answer 1

Python非常严格地遵守可能的副作用。就语言而言，在任何情况下，进行任何就地操作都是不正确的。

您的操作

 arr[2:] = arr[2:][::-1]

这里有三个单独的切片操作:

• arr[2:] 从arr中的所有元素(除了前两个)创建一个新列表。
• ...[::-1] 从...中的所有元素创建一个新的反转列表。
• arr[2:] = ... 用...替换arr中的所有元素(除了前两个)。

每个切片操作基本上都相当于原始的O(n)复制操作。由于只复制引用，因此元素的大小或类型并不重要。

在您的完整示例中，这相当于在O(k)循环中进行三个O(n)切片操作:

ans = [i+1 for i in range(n)]   # O(n)
for i in range(k):              # O(k)
    ans[i:] = ans[i:][::-1]     # O(n)

总的来说，时间复杂度为O(nk)，空间复杂度仅为O(n)，因为临时切片可以立即回收。您基本上会得到初始列表以及一些临时副本。

---

如果ans是一个字符串，例如ans = '12345 ... n'，那么结果会不同吗？

操作的复杂性不会改变-它们仍然是相同的原始操作。

在实践中，CPython实现使用某些对象进行欺骗。例如，对于只有引用计数为1的字符串，“+=”是“就地突变” ，尽管字符串是不可变的。但是，这不适用于您的切片使用。

总的来说，在Python中依赖内置优化是不明智的。

---

如果您担心空间问题，请从编写简洁的代码开始。例如，ans [i：] [::-1]应该简单地是ans [i :: -1]。这可以将所需的临时空间减少一半。

- MisterMiyagi

Answer 2

简而言之，每个列表切片操作都涉及到复制相关对象的引用（但不包括对象本身）。

在你的示例中：

- `arr[2:]` 复制了存储在 `arr` 中从索引 2 开始的对象引用，并将它们放入一个无名的新列表中（我将其称为 `L1`）。 - `[:: -1]` 复制了 `L1` 中的对象引用，并以相反的顺序将它们放入一个无名的新列表中（我将其称为 `L2`）。 - `arr[2:] = ...` 将存储在 `arr` 中的对象引用替换为存储在 `L2` 中的对象引用。

值得注意的是，这些并没有保证。这只是 CPython 目前的做法。

一些相关的函数包括：

- `list_slice` - 简单切片（没有步幅） - `list_subscript` - 下标，包括使用步幅的扩展切片 - `list_ass_slice` - 简单切片赋值（没有步幅） - `list_ass_subscript` - 下标赋值，包括使用扩展切片

看一下 `list` 的实现：https://github.com/python/cpython/blob/master/Objects/listobject.c

其中有些有趣的细节可供参考，比如防止 `a[::-1]=a` 的代码。

- NPE