比較最適化により Python のソートが高速になる仕組み-Python チュートリアル-php.cn

このテキストでは、Python と言語の参照実装である CPython という用語が同じ意味で使用されます。この記事は特に CPython について扱い、Python の他の実装には関係しません。

Python は、プログラマーが実際の実装の複雑さを舞台裏で残しながら、自分のアイデアを簡単な言葉で表現できる美しい言語です。

抽象化されるものの 1 つは並べ替えです。

「Python でソートはどのように実装されますか?」という質問に対する答えは簡単に見つかります。これはほとんどの場合、「Python ではどのような並べ替えアルゴリズムが使用されていますか?」という別の質問の答えになります。

ただし、これにより、興味深い実装の詳細がいくつか残されることがよくあります。

7 年以上前の Python 3.7 で導入されたにもかかわらず、十分に議論されていないと思われる実装の詳細が 1 つあります。

sorted() と list.sort() は、一般的なケースに合わせて最適化されており、最大 40 ～ 75% 高速化されています。 (bpo-28685 で Elliot Gorokhovsky によって寄稿されました。)

しかし、始める前に...

Python でのソートの簡単な再紹介

Python でリストを並べ替える必要がある場合、2 つのオプションがあります:

リストメソッド: list.sort(*, key=None, reverse=False)。指定されたリストをその場で並べ替えます
組み込み関数:sorted(iterable,/,*,key=None,reverse= False)、引数を変更せずに並べ替えられたリストを返します

他の組み込み反復可能オブジェクトをソートする必要がある場合は、パラメーターとして渡された反復可能オブジェクトまたはジェネレーターのタイプに関係なく、sorted のみを使用できます。

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 は 型固有の比較関数
を使用します

同種リストとは何ですか?

同種リストは、1 つのタイプの要素のみを含むリストです。

例:

homogeneous = [1, 2, 3, 4]

ログイン後にコピー

一方、これは均一なリストではありません:

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

ログイン後にコピー

興味深いことに、公式の Python チュートリアルでは次のように述べられています。

リストは変更可能であり、その要素は通常は同種であり、リストを反復処理することによってアクセスされます

タプルについての補足

同じチュートリアルでは次のように述べられています。

タプルは不変であり、通常、要素の異種シーケンスが含まれます

タプルまたはリストをいつ使用するか迷った場合は、経験則を次に示します。
要素が同じ型の場合はリストを使用し、それ以外の場合はタプルを使用します

配列についてはどうでしょうか?

Python は、数値の同種配列コンテナオブジェクトを実装します。

ただし、Python 3.12 の時点では、配列には独自の並べ替えメソッドが実装されていません。

それらを並べ替える唯一の方法は、sorted を使用することです。これは内部的に配列からリストを作成し、その過程で型関連の情報を消去します。

型固有の比較関数を使用するとなぜ役立つのでしょうか?

Python は実際の比較を行う前にさまざまなチェックを実行するため、Python での比較にはコストがかかります。

Python で 2 つの値を比較するときに内部で何が起こるかを簡単に説明します。

Python は比較関数に渡された値が NULL でないことをチェックします
値の型が異なるが、右オペランドが左オペランドのサブタイプである場合、Python は右オペランドの比較関数を逆に使用します (例: < を > に使用します)
値が同じ型であるか、異なる型であるが、どちらも他方のサブタイプではない場合:
- Python は最初に左オペランドの比較関数を試みます
- これが失敗した場合は、右オペランドの比較関数が試行されますが、その逆が行われます。
- これも失敗し、比較が等価または不等の場合は、同一性比較が返されます (メモリ内の同じオブジェクトを参照する値の場合は True)
- それ以外の場合は、TypeError が発生します

How Comparison Optimization Makes Python Sorting Faster

これに加えて、各型独自の比較関数により追加のチェックが実装されます。

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 プログラマーになることができます。

以上が比較最適化により Python のソートが高速になる仕組みの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。