比较优化如何使 Python 排序更快-黔优网

在本文中，术语 python 和 cpython（该语言的参考实现）可以互换使用。本文专门讨论 cpython，不涉及 python 的任何其他实现。

python 是一种美丽的语言，它允许程序员用简单的术语表达他们的想法，而将实际实现的复杂性抛在脑后。

它抽象出来的东西之一就是排序。

你可以轻松找到“python中排序是如何实现的？”这个问题的答案。这几乎总是回答另一个问题：“python 使用什么排序算法？”。

然而，这常常会留下一些有趣的实现细节。

有一个实现细节我认为讨论得还不够，尽管它是七年前在 python 3.7 中引入的：

立即学习“Python免费学习笔记（深入）”；

sorted() 和 list.sort() 已针对常见情况进行了优化，速度提高了 40-75%。（由 elliot gorokhovsky 在 bpo-28685 中贡献。）

但是在我们开始之前...

简要重新介绍 python 中的排序

当你需要在python中对列表进行排序时，你有两种选择：

列表方法：list.sort（*，key=none，reverse=false），它对给定列表进行就地排序

内置函数：sorted(iterable, /, *, key=none, reverse=false)，它返回一个排序列表而不修改其参数

如果需要对任何其他内置可迭代对象进行排序，则无论作为参数传递的可迭代对象或生成器的类型如何，都只能使用已排序。

sorted 总是返回一个列表，因为它内部使用了 list.sort。

这是用纯 python 重写的 cpython 排序 c 实现的大致等效项：

def sorted(iterable: iterable[any], key=none, reverse=false):
    new_list = list(iterable)
    new_list.sort(key=key, reverse=reverse)
    return new_list

是的，就这么简单。

python 如何使排序更快

正如 python 内部排序文档所说：

有时可以用更快的特定类型比较来代替较慢的通用 pyobject_richcomparebool

简而言之，这个优化可以描述如下：

当列表是同质的时，python 使用特定于类型的比较函数

什么是同质列表？

同构列表是仅包含一种类型的元素的列表。

例如：

homogeneous = [1, 2, 3, 4]

另一方面，这不是一个同质列表：

heterogeneous = [1, "2", (3, ), {'4': 4}]

有趣的是，python 官方教程指出：

列表是可变的，并且它们的元素通常是同质的并且可以通过迭代列表来访问

关于元组的旁注

同一个教程指出：

元组是不可变的，并且通常包含异构序列元素

因此，如果您想知道何时使用元组或列表，这里有一条经验法则：

如果元素类型相同，则使用列表，否则使用元组

等等，那么数组呢？

python 为数值实现了同构数组容器对象。

但是，从 python 3.12 开始，数组没有实现自己的排序方法。

对它们进行排序的唯一方法是使用排序，它在内部从数组中创建一个列表，并在此过程中删除任何与类型相关的信息。

为什么使用特定于类型的比较函数有帮助？

python 中的比较成本很高，因为 python 在进行任何实际比较之前会执行各种检查。

以下是在 python 中比较两个值时在幕后发生的情况的简化解释：

python 检查传递给比较函数的值不为 null

如果值的类型不同，但右操作数是左操作数的子类型，python 使用右操作数的比较函数，但相反（例如，它将使用）

如果值属于相同类型或不同类型但都不是另一个的子类型：

python 将首先尝试左操作数的比较函数

如果失败，它将尝试右操作数的比较函数，但相反。

如果也失败，并且比较是相等或不等，它将返回身份比较（对于引用内存中同一对象的值，则为 true）

否则，它会引发 typeerror

除此之外，每种类型自己的比较函数都会实现额外的检查。

例如，在比较字符串时，python 会检查字符串字符是否占用超过一个字节的内存，而 float 比较会以不同的方式比较一对 float 和一个 float 与一个 int 。

更详细的解释和图表可以在这里找到：adding data-aware sort optimizations to cpython

在引入此优化之前，每次在排序过程中比较两个值时，python 都必须执行所有这些各种特定类型和非特定类型的检查。

提前检查列表元素的类型

除了迭代列表并检查每个元素之外，没有什么神奇的方法可以知道列表中的所有元素是否属于同一类型。

python 几乎完全做到了这一点 - 检查传递给 list.sort 或作为参数排序的 key 函数生成的排序键的类型

构建键列表

如果提供了 key 函数，python 使用它来构造键列表，否则它使用列表自己的值作为排序键。

以一种过于简单的方式，键的构造可以表示为以下python代码。

if key is none:
    keys = list_items
else:
    keys = [key(list_item) for list_item in list_item]

注意，cpython 内部使用的键是 cpython 对象引用的 c 数组，而不是 python 列表

一旦构造了键，python 就会检查它们的类型。

检查密钥类型

在检查键的类型时，python 的排序算法会尝试确定键数组中的所有元素是否都是 str、int、float 或 tuple，或者只是同一类型，但对基本类型有一些限制。

值得注意的是，检查键的类型会预先增加一些额外的工作。 python 这样做是因为它通常可以通过加快实际排序速度来获得回报，特别是对于较长的列表。

整型约束

int 应该不是bignum

实际上，这意味着要使此优化发挥作用，整数应小于 2^30 - 1（这可能因平台而异）

顺便说一句，这里有一篇很棒的文章，解释了 python 如何处理大整数：# how python implements super long integers?

强度约束

字符串中的所有字符应占用小于 1 个字节的内存，这意味着它们应由 0-255 范围内的整数值表示

实际上，这意味着字符串应该只包含拉丁字符、空格和 ascii 表中的一些特殊字符。

浮动约束

为了使此优化发挥作用，浮动没有任何限制。

元组约束

仅检查第一个元素的类型

这个元素本身不应该是一个元组

如果所有元组的第一个元素共享相同的类型，则比较优化将应用于它们

所有其他元素都照常进行比较

我如何应用这些知识？

首先，知道是不是很有趣？

其次，在 python 开发者面试中提及这些知识可能是一个很好的接触。

对于实际的代码开发来说，了解这个优化可以帮助你提高排序性能。

通过明智地选择值类型进行优化

根据引入此优化的 pr 中的基准，对仅包含浮点数的列表进行排序，而不是对末尾带有单个整数的浮点数列表进行排序，速度几乎是前者的两倍。

所以当需要优化时，像这样转换列表

floats_and_int = [1.0, -1.0, -0.5, 3]

进入看起来像这样的列表

just_floats = [1.0, -1.0, -0.5, 3.0] # note that 3.0 is a float now

可能会提高性能。

使用对象列表的键进行优化

虽然 python 的排序优化适用于内置类型，但了解它如何与自定义类交互也很重要。

在对自定义类的对象进行排序时，python 依赖于您定义的比较方法，例如 __lt__（小于）或 __gt__（大于）。

但是，特定于类型的优化不适用于自定义类。

python 将始终使用这些对象的通用比较方法。

这是一个例子：

class myclass:
    def __init__(self, value): 
        self.value = value 

    def __lt__(self, other): 
        return self.value 



<p>在这种情况下，python 将使用 __lt__ 方法进行比较，但它不会从特定于类型的优化中受益。排序仍然可以正常工作，但可能不如排序内置类型那么快。</p>

<p>如果在对自定义对象进行排序时性能至关重要，请考虑使用返回内置类型的关键函数：<br></p>

<pre class="brush:php;toolbar:false">sorted_list = sorted(my_list, key=lambda x: x.value)