使用list.count使用.sort（）就地对列表进行排序不起作用。为什么？

Question

我正在尝试按其元素的频率对列表进行排序。

>>> a = [5, 5, 4, 4, 4, 1, 2, 2]
>>> a.sort(key = a.count)
>>> a
[5, 5, 4, 4, 4, 1, 2, 2]

a不变。然而：

>>> sorted(a, key = a.count)
[1, 5, 5, 2, 2, 4, 4, 4]

为什么这种方法不起作用.sort()？

Answer 1

它不适用于该list.sort方法，因为 CPython 决定暂时“清空列表”（另一个答案已经提出了 this）。这在文档中作为实现细节提到：

CPython 实现细节：在对列表进行排序时，尝试改变甚至检查列表的效果是未定义的。Python 的 C 实现使列表在持续时间内显示为空，ValueError如果它可以检测到列表在排序期间发生了变异，则会引发。

该源代码包含多一点解释了类似的评论：

    /* The list is temporarily made empty, so that mutations performed
     * by comparison functions can't affect the slice of memory we're
     * sorting (allowing mutations during sorting is a core-dump
     * factory, since ob_item may change).
     */

解释不是直截了当的，但问题是键函数和比较可能会list在排序期间更改实例，这很可能导致 C 代码的未定义行为（这可能会使解释器崩溃）。防止列表在排序过程中被清空，这样即使有人更改了实例，也不会导致解释器崩溃。

这不会发生，sorted因为sorted 复制列表并简单地对副本进行排序。该副本在排序过程中仍被清空，但无法访问它，因此它不可见。

但是，您真的不应该这样排序以获得频率排序。那是因为对于每个项目，您调用该key函数一次。并list.count迭代每个项目，因此您可以有效地迭代每个元素的整个列表（所谓的O(n**2)复杂性）。更好的方法是为每个元素计算一次频率（可以在 中完成O(n)），然后在key.

然而，由于 CPython 有一个Counter类也支持most_common你真的可以使用它：

>>> from collections import Counter
>>> [item for item, count in reversed(Counter(a).most_common()) for _ in range(count)]
[1, 2, 2, 5, 5, 4, 4, 4]

这可能会改变具有相等计数的元素的顺序，但由于您正在执行一个无关紧要的频率计数。

Answer 2

您看到的是的某些CPython实现细节的结果list.sort。再试一次，但是先创建一个副本a：

a.sort(key=a.copy().count)
a
# [1, 5, 5, 2, 2, 4, 4, 4]

.sort在a内部进行修改，因此a.count将产生无法预测的结果。这被记录为实现细节。

什么copy电话确实是它创建的副本a用途和该列表的count的关键方法。您可以看到一些调试语句会发生什么：

def count(x):
    print(a)
    return a.count(x)

a.sort(key=count)
[]
[]
[]
...

a在内部访问时会显示为空列表.sort，并且[].count(anything)将是0。这解释了为什么输出与输入相同-谓词都相同（0）。

OTOH，sorted创建一个新列表，因此没有这个问题。

如果您真的想按频率计数排序，那么惯用的方法是使用Counter：

from collections import Counter

a.sort(key=Counter(a).get)
a
# [1, 5, 5, 2, 2, 4, 4, 4]