Space python 中 split() 函数的复杂性

Question

我有一个问题，如果下面的代码是就地执行还是有额外的 space 复杂性。鉴于该句子最初是一个字符串。感谢感谢帮助

sentence = "hello world"

sentence = sentence.split()

Answer 1

如评论中所述，操作不能是 "in-place"，因为这意味着在同一数据结构中，但您显然是从字符串创建新的数据结构（列表）。我假设您的实际问题是 split 返回的子字符串是否将使用与原始不可变字符串相同的字符支持数组。¹⁾

一个快速实验似乎表明他们没有。

In [1]: s = (("A" * 100000) + " ") * 50000

In [2]: len(s)
Out[2]: 5000050000

In [3]: l = s.split()

在第一步之后，top 显示 ipython 进程使用了 ~30% 的内存，在 split 之后它使用了 ~60%，所以后备数组, 占用了大部分内存，没有被重用。当然，这可能是特定于实现的。我使用的是 IPython 5.5.0（基于 Python 3.6.8），但使用 Python 2.7.15 也得到了相同的结果。这似乎也适用于字符串切片。

¹⁾ 正是因为字符串是不可变的，所以这是可能的，据我所知，其他语言，如 Java，这样做，虽然我目前无法测试。）

注意：sys.getsizeof 的使用在这里有点误导，因为它似乎只测量实际数据结构的大小，而不是其中包含的元素。

In [4]: sys.getsizeof(s)
Out[4]: 5000050049

In [5]: sys.getsizeof(l)
Out[5]: 433816

据此，列表仅占原始拆分字符串space的一小部分，但如上所述，实际内存消耗增加了一倍。

Answer 2

在 python 中，字符串是不可变对象，这意味着它们根本无法更改 "in-place"。对它们的所有操作本质上都会占用新内存 space，希望旧的未使用的内存被 python 的垃圾收集过程删除（如果没有更多对这些对象的引用）。一种亲自查看的方法是：

>>> a = 'hello world'
>>> id(a)
1838856511920
>>> b = a
>>> id(b)
1838856511920
>>> a += '!'
>>> id(a)
1838856512944
>>> id(b)
1838856511920

如你所见，当b和a指的是相同的底层对象时，它们在内存中的id是相同的，但是一旦其中一个发生变化，它现在在内存中有一个新的 id - 一个新的 space。保持不变的对象 (b) 仍然具有相同的地点 ID。

要在您的示例中进行检查：

>>> sentence = "hello world"
>>> id(sentence)
1838856521584
>>> sentence = sentence.split()
>>> id(sentence)
1838853280840

我们可以再次看到这些对象没有占用相同的内存。我们可以进一步探索它们占用了多少 space：

>>> import sys
>>> sentence = "hello world"
>>> sys.getsizeof(sentence)
60
>>> sentence = sentence.split()
>>> sys.getsizeof(sentence)
160

Space python 中 split() 函数的复杂性

Space complexity of split() function in python

python

split

space-complexity