Day 99 of Python Practice: Essential Techniques for Optimizing Sorting Performance!

Original link: https://dev.to/tilalis/optimize-python-sorting-with-one-little-trick-2gbAuthor: TilalisTranslator: Stubborn Bronze Three

Introduction

Hello everyone, I am Stubborn Bronze Three. Welcome to follow me on WeChat public account: Stubborn Bronze Three. Please like, bookmark, and follow, a triple click!!!

Welcome to Day 99 of Python Practice!

The sorting functionality in Python is very powerful and easy to use. However, many may not know that starting from Python 3.7, <span>sorted()</span> and <span>list.sort()</span> have been optimized in common cases, with speed improvements of 40% to 75%. This article will delve into the principles behind this optimization and how to leverage it in practical development to enhance sorting performance.

Introduction to Python Sorting

In Python, there are two main ways to sort:

• List Method: <span>list.sort(*, key=None, reverse=False)</span>, which sorts the given list in place.
• Built-in Function: <span>sorted(iterable, /, *, key=None, reverse=False)</span>, which returns a sorted list without modifying the original parameter.

For other built-in iterable objects, only <span>sorted</span> can be used. <span>sorted</span> always returns a list because it internally uses <span>list.sort</span>. Here is the pure Python equivalent code of the C implementation of <span>sorted</span> in CPython:

def sorted(iterable: Iterable[Any], key=None, reverse=False):
    new_list = list(iterable)
    new_list.sort(key=key, reverse=reverse)
    return new_list

How Python Speeds Up Sorting

The internal sorting documentation of Python mentions:

Sometimes a faster type-specific comparison function can replace a slower generic <span>PyObject_RichCompareBool</span>.

In short, when the list is homogeneous, Python uses type-specific comparison functions.

What is a Homogeneous List?

A homogeneous list is one where all elements are of the same type. For example:

homogeneous = [1, 2, 3, 4]

Whereas the following list is not homogeneous:

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

The official Python tutorial also mentions that lists are typically homogeneous, while tuples are usually heterogeneous. If the element types are the same, it is recommended to use lists; otherwise, use tuples.

Why Can Type-Specific Comparison Functions Improve Performance?

In Python, comparison operations are costly because Python performs various checks before the actual comparison. Here is a simplified process of comparison operations:

• Check if the values passed to the comparison function are <span>NULL</span>.
• If the types of the values are different, but the right operand is a subtype of the left operand, Python will use the comparison function of the right operand, but in reverse order (for example, using <span><</span> for <span>></span>).
• If the types of the values are the same, or different but neither is a subtype of the other:
• Python first tries to use the comparison function of the left operand.
• If it fails, it tries the comparison function of the right operand, but in reverse order.
• If it still fails, and the comparison is for equality or inequality, it will return an identity comparison (returning <span>True</span> for values that reference the same object in memory).
• Otherwise, it raises a <span>TypeError</span>.

Additionally, each type’s comparison function performs extra checks. For example, when comparing strings, Python checks if the string characters occupy more than one byte of memory, while floating-point comparisons handle <span>float</span> and <span>int</span> differently.

Pre-checking List Element Types

Python achieves this by checking the types of the sorting keys generated by the <span>key</span> function passed to <span>list.sort</span> or <span>sorted</span>. If a <span>key</span> function is provided, Python uses it to build a list of keys; otherwise, it uses the values of the list itself as sorting keys. Here is a simplified key construction code:

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

After constructing the keys, Python checks the types of these keys.

Checking Key Types

Python’s sorting algorithm attempts to determine whether all elements in the key array are <span>str</span>, <span>int</span>, <span>float</span>, or <span>tuple</span>, or whether they are of the same type, and imposes some constraints on the base types. Checking the types of the keys adds some extra work, but it can usually be offset by speeding up the actual sorting, especially for longer lists.

Constraints on <span>int</span>

<span>int</span> should not be large integers. This means that for the optimization to be effective, integers should be less than _2^30 – 1_ (the specific value may vary by platform).

Constraints on <span>str</span>

All characters in the string should occupy less than 1 byte of memory, meaning they should be represented by integer values in the range of 0-255. This means that strings can only contain Latin characters, spaces, and some special characters from the ASCII table.

Constraints on <span>float</span>

There are no additional constraints on floating-point numbers.

Constraints on <span>tuple</span>

• Only the type of the first element is checked.
• This element itself should not be a tuple.
• If all tuples have the same type for the first element, comparison optimizations are applied to them.
• Other elements are compared in the usual way.

How to Apply This Knowledge

First, understanding these optimizations is interesting in itself. Secondly, mentioning this knowledge in Python developer interviews can be a highlight.

In actual code development, understanding these optimizations can help you enhance sorting performance.

Optimizing Performance by Choosing the Right Data Types

According to the benchmarks in the PR that introduced this optimization, sorting a list containing only floating-point numbers is nearly twice as fast as sorting a list containing both floating-point numbers and a single integer. Therefore, when optimization is needed, you can convert a list like the following:

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

To:

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

This may improve performance.

Using Key Functions to Optimize Sorting of Object Lists

While Python’s sorting optimizations work well for built-in types, it is also important to understand how they interact with custom classes. When sorting objects of custom classes, Python relies on the comparison methods you define, such as <span>__lt__</span> (less than) or <span>__gt__</span> (greater than). However, type-specific optimizations do not apply to custom classes. Python will always use the generic comparison methods to handle these objects.

For 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 <span>__lt__</span> method for comparison, but will not benefit from type-specific optimizations. 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 built-in types:

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

Conclusion

Premature optimization, especially in Python, is evil. You should not design your entire application around specific optimizations in CPython, but understanding these optimizations is one way to become a more skilled developer.

Knowing these optimizations allows you to leverage them when necessary, especially when performance becomes critical. For example, if sorting is based on timestamps, using a homogeneous list of integers (Unix timestamps) instead of <span>datetime</span> objects can effectively utilize this optimization.

However, code readability and maintainability should take precedence over these optimizations. While understanding these underlying details is important, it is equally important to appreciate Python’s high-level abstractions that make it such an efficient language.

Thank you for reading! Please follow me on WeChat public account: Stubborn Bronze Three.Like, bookmark, and follow, a triple click!! Welcome to click the [👍 Like Author] button to donate💰💰, treat me to a cup of coffee☕️!

Day 98 of Python Practice: 10 Clever Tips to Improve Python Performance2025 Django Developer Survey Report