时间戳

首页 > 解决方案 > 为什么相同的键函数对 sorted 和 list.sort 产生不同的结果？

python - 为什么相同的键函数对 sorted 和 list.sort 产生不同的结果？

问题描述

我的任务是按列表中包含的数字的频率对列表进行排序。如果几个数字具有相同的频率 - 它们应该根据它们的自然顺序进行排序。
例如：[5, 2, 4, 1, 1, 1, 3]==>[1, 1, 1, 2, 3, 4, 5] 在解决问题的过程中，我写了一个函数如下：

lista = [3, 4, 11, 13, 11, 4, 4, 7, 3]
def func1(numbers: list):
    numbers.sort(key=lambda x:(-numbers.count(x), x))
    return numbers
    
result = func1(lista)
print(result)

但结果是[3, 3, 4, 4, 4, 7, 11, 11, 13]，然后我写了一个非常相似的函数

lista = [3, 4, 11, 13, 11, 4, 4, 7, 3]
def func2(numbers: list):
    return sorted(numbers,key=lambda x:(-numbers.count(x), x))

result = func2(lista)
print(result)

结果是[4, 4, 4, 3, 3, 11, 11, 7, 13]，这就是我想要的我的问题是：list.sort 函数和 sorted 函数有什么不同

这只是我整个作业的一小部分，请忽略我算法的时间复杂度。

标签： python

解决方案

因为list.sort是就地算法，所以列表中的内容.sort是任意的——算法可能对列表进行部分排序，独立地保持排序项，甚至根据“未排序性”表现出不同的行为。因此，不能保证key在其期间访问列表.sort会按预期工作。

具体来说，CPython 使列表在其期间显示为空.sort：

排序（*，键=无，反向=假）

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

相反，sorted保证产生一个新的list，使旧列表在排序过程中保持不变且外观一致。

您可以在使用之前通过观察密钥来检查此行为：

def observe(arg, *hint):
    """Helper to inspect a value during its usage"""
    print(repr(arg), *hint)
    return arg

numbers = [1, 2, 1]
numbers.sort(key=lambda x: observe(numbers.count(x), "is the key for", x))
# 0 is the key for 1
# 0 is the key for 2
# 0 is the key for 1
sorted(numbers, key=lambda x: observe(numbers.count(x), "is the key for", x))
# 2 is the key for 1
# 1 is the key for 2
# 2 is the key for 1

使用 key 函数意味着 keykey=lambda x: (-numbers.count(x), x)的.sort形式(0, x)——因为第一个 key-part0总是相等的，所以项目按第二个 key-part 排序，即它们的值。这相当于标准的排序键。

推荐阅读