In this text the terms Python and CPython, which is the reference implementation of the language, are used interchangeably. This article specifically addresses CPython and does not concern any other implementation of Python.
Python is a beautiful language that allows a programmer to express their ideas in simple terms leaving the complexity of the actual implementation behind the scenes.
One of the things it abstracts away is sorting.
You can easily find the answer to the question "how sorting is implemented in Python?" which almost always answers another question: "What sorting algorithm does Python use?".
However, this often leaves some interesting implementations details behind.
There is one implementation detail that I think isn't discussed enough, even though it was introduced over seven years ago in python 3.7:
sorted() and list.sort() have been optimized for common cases to be up to 40-75% faster. (Contributed by Elliot Gorokhovsky in bpo-28685.)
But before we start...
When you need to sort a list in python, you have two options:
If you need to sort any other built-in iterable, you can only use sorted regardless of the type of iterable or generator passed as a parameter.
sorted always returns a list because it uses list.sort internally.
Here is a rough equivalent of CPython's sorted C implementation rewritten in pure python:
def sorted(iterable: Iterable[Any], key=None, reverse=False): new_list = list(iterable) new_list.sort(key=key, reverse=reverse) return new_list
Yes, it's that simple.
As Python's internal documentation for sorting puts it:
It is sometimes possible to substitute faster type-specific comparisons for the slower, generic PyObject_RichCompareBool
And in short this optimization can be described as follows:
When a list is homogeneous, Python usestype-specific comparison function
A homogeneous list is a list that contains elements only of one type.
For example:
homogeneous = [1, 2, 3, 4]
On the other hand, this is not a homogeneous list:
heterogeneous = [1, "2", (3, ), {'4': 4}]
Interestingly, official Python tutorial states:
Lists are mutable, and their elements areusually homogeneousand are accessed by iterating over the list
That same tutorial states:
Tuples are immutable, andusually contain a heterogeneous sequenceof elements
So if you ever wonder when to use a tuple or a list here's a rule of thumb:
if elements are of the same type, use a list, otherwise use a tuple
Python implements a homogeneous array container object for numeric values.
However, as of python 3.12, arrays do not implement their own sort method.
The only way to sort them is by using sorted, which internally creates a list out of the array, erasing any type-related information in the process.
Comparisons in python are costly, because Python performs various checks before doing any actual comparison.
Here is a simplified explanation of what happens under the hood when you compare two values in python:
On top of this, each type's own comparison functions implement additional checks.
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.
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
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.
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 shouldnotbe a bignum
Practically this means that for this optimization to work, integer should be less than2^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?
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.
There are no constraints for floats in order for this optimization to work.
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.
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.
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)
Premature optimization, especially in Python, is evil.
CPython の特定の最適化を中心にアプリケーション全体を設計するべきではありませんが、これらの最適化を意識することは良いことです。ツールをよく理解することは、より熟練した開発者になる方法です。
次のような最適化に留意すると、状況に応じて最適化を活用できるようになります。特にパフォーマンスが重要になった場合に活用できます。
並べ替えがタイムスタンプに基づいているシナリオを考えてみましょう。日時オブジェクトの代わりに同種の整数リスト (Unix タイムスタンプ) を使用すると、この最適化を効果的に活用できます。
ただし、コードの可読性と保守性がそのような最適化よりも優先されるべきであることを覚えておくことが重要です。
これらの低レベルの詳細について知ることは重要ですが、Python を生産性の高い言語にしている高レベルの抽象化を理解することも同じくらい重要です。
Python は素晴らしい言語であり、その奥深くを探求すると、Python をより深く理解し、より優れた Python プログラマーになることができます。
The above is the detailed content of How Comparison Optimization Makes Python Sorting Faster. For more information, please follow other related articles on the PHP Chinese website!