为什么排序后的列表比未排序的列表更大

Question

我有一个包含UTF8字符串的列表my_list:

>>> len(my_list)
8777
>>> getsizeof(my_list)                     #  <-- note the size
77848

由于某些原因，排序后的列表（my_sorted_list = sorted(my_list)）占用更多的内存：

>>> len(my_sorted_list)
8777
>>> getsizeof(my_sorted_list)              #  <-- note the size
79104

为什么sorted返回的列表在内存中占用的空间比初始未排序的列表还要大？

- jcuenod

---

正如@Jim的回答所指出的，sorted会创建新列表，你可以参考我的最近问题（list()使用比列表推导式更多的内存），这将为您提供一些Python见解。 - vishes_shell

@vishes_shell 或者 https://dev59.com/imw05IYBdhLWcg3wcRQj（2011年提问） - jcuenod

我真的很喜欢你在回答@vishes_shell问题时的图表 :-）。我看到这种类型的问题和答案唯一的问题是，由于我们正在处理实现细节，它们可能会在某些时候突然变得过时。 - Dimitris Fasarakis Hilliard

@JimFasarakis-Hilliard 这是真的，尽管这个特定的实现细节已经从Python2移植到了Python3。 - jcuenod

@jcuenod 是的，没错。不过看看 dict 的实现吧，它的实现一直存活到 在 3.6 中发生了相当大的变化 为止。;-) - Dimitris Fasarakis Hilliard

Answer 1

正如Ignacio所指出的, 这是由于Python分配了比所需更多的内存。这是为了在列表上执行O(1) .appends操作。

sorted创建一个新列表，并将提供的序列就地排序后返回。为了创建新列表，Python 使用传递的列表扩展一个空大小的列表；这导致观察到的过度分配（在调用list_resize之后发生）。您可以通过使用list.sort来证实排序不是罪魁祸首；相同的算法被使用而不会创建新列表（或者，正如它所知道的那样，在原地执行）。当然，那里的大小不会有所不同。

值得注意的是，这种差异主要存在于以下情况下：

• 原始列表是使用列表推导式创建的（如果有空间并且最后一个append不会触发调整大小，则大小较小）。

• 当使用列表字面量时。在那里，基于堆栈上的值的数量创建了一个PyList_New，并且没有进行任何附加。直接分配到底层数组中执行），这不会触发任何调整大小，并将大小保持到其最小值：

因此，使用列表推导：

l = [i for i in range(10)]

getsizeof(l)          # 192
getsizeof(sorted(l))  # 200

或者是列表字面量：

l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

getsizeof(l)          # 144
getsizeof(sorted(l))  # 200

这些尺寸更小（使用文字字面量会更加明显）。

当通过list创建时，内存总是被过度分配；Python 知道这些尺寸，并根据尺寸过度分配一点以预测未来的修改：

l = list(range(10))

getsizeof(l)          # 200
getsizeof(sorted(l))  # 200

所以，您没有观察到列表大小方面的差异。

---

作为最后说明，我必须指出这是Python的C实现即CPython的特定行为。这是语言实现的细节，因此您不应以任何奇怪的方式依赖它。 Jython、IronPython、PyPy和其他任何实现可能具有相同/不同的行为。

- Dimitris Fasarakis Hilliard

Answer 2

列表调整大小操作 采用过度分配的方式，以便在追加列表和使用编译器预分配列表之间进行摊销。

- Ignacio Vazquez-Abrams

---

感谢提供 Python 代码的链接！这太棒了……我本来会接受的，但是 @Jim 回答中的细节让我选择了他的答案。 - jcuenod