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

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

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

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

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

但是，这通常会留下一些有趣的实现细节。

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

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

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

For example, when comparing strings, Python will check if the string characters take more than one byte of memory, and float comparison will compare a pair of float's and a float and an int differently.

A more detailed explanation and diagram can be found here: Adding Data-Aware Sort Optimizations to CPython

Before this optimization was introduced, Python had to execute all this various type-specific and non-type-specific checks every time two values were compared during sorting.

Checking List Element's Types in Advance

There's no magical way to know if all the elements of a list are of the same type other than to iterate over the list and check each element.

Python does almost exactly that — checking the types of sorting keys generated by key function passed to list.sort or sorted as a parameter

Constructing a List of Keys

If a key function is provided, Python uses it to construct a list of keys, otherwise it uses the list's own values as sorting keys.

In an oversimplified manner, keys construction can be expressed as the following python code.

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

Note, that keys used internally in CPython are a C array of CPython object references, and not a Python list

Once the keys are constructed, Python checks their types.

Checking Key's Type

When checking the types of keys, Python's sorting algorithm tries to determine if all elements in the keys array are either str, int, float or tuple, or simply of the same type, with some constraints for base types.

It's worth noting that checking the types of the keys adds some extra work up front. Python does this because it usually pays off by making the actual sorting faster, especially for longer lists.

int constraints

int should not be a bignum

Practically this means that for this optimization to work, integer should be less than 2^30 - 1 (this may vary depending on the platform)

As a side note, here is a great article which explains how Python handles big integers: # How python implements super long integers?

str constraints

All characters of a string should take less than 1 byte of memory, meaning that they should be represented by integer values in the range of 0-255

In practice, this means that strings should consist only of Latin characters, spaces, and some special characters found in the ASCII table.

float constraints

There are no constraints for floats in order for this optimization to work.

tuple constraints

• Only the first element's type is checked
• This element itself should not be a tuple itself
• If all tuples share the same type for their first element, the comparison optimization is applied to them
• All other elements are compared as usual

How Can I Apply This Knowledge?

First of all, isn’t it fascinating to know?

Secondly, mentioning this knowledge could be a nice touch in a Python Developer interview.

As for actual code development, understanding this optimization can help you improve sorting performance.

Optimize by Selecting the Type of Values Wisely

According to the benchmark in the PR that introduced this optimization, sorting a list that consists only of floats rather than a list of floats with even a single integer at the end is almost twice as fast.

So when it's time to optimize, transforming list like this

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

Into list that looks like this

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

might improve performance.

Optimize by Using Keys for Lists of Objects

While Python's sorting optimization works well with built-in types, it's important to understand how it interacts with custom classes.

When sorting objects of custom classes, Python relies on the comparison methods you define, such as __lt__ (less than) or __gt__ (greater than).

However, the type-specific optimization doesn't apply to custom classes.
Python will always use the general comparison method for these objects.

Here's an example:

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

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

my_list = [MyClass(3), MyClass(1), MyClass(2)] 
sorted_list = sorted(my_list)

In this case, Python will use the __lt__ method for comparisons, but it won't benefit from the type-specific optimization. The sorting will still work correctly, but it may not be as fast as sorting built-in types.

If performance is critical when sorting custom objects, consider using a key function that returns a built-in type:

sorted_list = sorted(my_list, key=lambda x: x.value)

Afterword

Premature optimization, especially in Python, is evil.

您不应该围绕 CPython 中的特定优化来设计整个应用程序，但了解这些优化是有好处的：充分了解您的工具是成为更熟练的开发人员的一种方式。

留意这些优化可以让你在情况需要时利用它们，特别是当性能变得至关重要时：

考虑一个基于时间戳进行排序的场景：使用同构整数列表（Unix 时间戳）而不是日期时间对象可以有效地利用此优化。

但是，重要的是要记住，代码的可读性和可维护性应优先于此类优化。

虽然了解这些底层细节很重要，但欣赏 Python 的高级抽象也同样重要，正是这些抽象使其成为一种高效的语言。

Python 是一门令人惊叹的语言，探索其深度可以帮助您更好地理解它并成为一名更好的 Python 程序员。

以上是比较优化如何使 Python 排序更快的详细内容。更多信息请关注PHP中文网其他相关文章！