このテキストでは、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 が発生します

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

たとえば、文字列を比較する場合、Python は文字列文字が 1 バイト以上のメモリを必要とするかどうかをチェックし、浮動小数点数の比較では、浮動小数点のペアと浮動小数点と整数を異なる方法で比較します。

より詳細な説明と図は、ここにあります: Adding Data-Aware Sort Optimizations to CPython

この最適化が導入される前は、Python は並べ替え中に 2 つの値が比較されるたびに、さまざまな型固有および非型固有のチェックをすべて実行する必要がありました。

リスト要素の型を事前に確認する

リストを反復処理して各要素をチェックする以外に、リストのすべての要素が同じ型であるかどうかを知る魔法の方法はありません。

Python はそれとほぼ同じことを行います。list.sort に渡された 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 制約

int は bignum であってはなりません

実際には、この最適化が機能するには、整数が

2^30 - 1 未満である必要があることを意味します (これはプラットフォームによって異なる場合があります)

余談ですが、Python が大きな整数をどのように処理するかを説明した素晴らしい記事があります: # How Pythonimplements superlong integers?

str 制約

文字列のすべての文字は 1 バイト未満のメモリを使用する必要があります。つまり、文字列は 0 ～ 255 の範囲の整数値で表される必要があります

実際には、これは文字列がラテン文字、スペース、および ASCII テーブルにある一部の特殊文字のみで構成されている必要があることを意味します。

フロート制約

この最適化が機能するために、浮動小数点数には制約はありません。

タプル制約

最初の要素のタイプのみがチェックされます
この要素自体はタプルそのものであってはなりません
すべてのタプルが最初の要素の型を共有している場合、比較の最適化がそれらに適用されます
他のすべての要素は通常どおり比較されます

この知識をどのように応用できますか?

まず、知るのはとても興味深いことではないでしょうか?

第二に、Python 開発者インタビューでこの知識について言及すると、良い印象を与える可能性があります。

実際のコード開発に関しては、この最適化を理解することでソートのパフォーマンスを向上させることができます。

値のタイプを賢く選択して最適化する

この最適化を導入した PR のベンチマークによると、最後に整数が 1 つでもある浮動小数点数のリストよりも、浮動小数点数のみで構成されるリストのソートの方が、ほぼ 2 倍高速になります。

最適化するときは、このようにリストを変換します

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

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

このようなリストに

just_floats = [1.0, -1.0, -0.5, 3.0] # 3.0 は浮動小数点であることに注意してください

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

パフォーマンスが向上する可能性があります。

オブジェクトのリストにキーを使用して最適化する

Python の並べ替えの最適化は組み込み型ではうまく機能しますが、カスタム クラスとどのように対話するかを理解することが重要です。

カスタム クラスのオブジェクトを並べ替える場合、Python は __lt__ (より小さい) や __gt__ (より大きい) など、定義された比較メソッドに依存します。

ただし、型固有の最適化はカスタム クラスには適用されません。

Python は常に、これらのオブジェクトに対して一般的な比較方法を使用します。

これが例です:

クラスMyClass: def __init__(self, value): self.value = 値 def __lt__(自分、その他): self.value floats_and_int = [1.0, -1.0, -0.5, 3] この場合、Python は比較に __lt__ メソッドを使用しますが、型固有の最適化の恩恵は受けられません。並べ替えは引き続き正しく機能しますが、組み込み型の並べ替えほど高速ではない可能性があります。

カスタム オブジェクトを並べ替えるときにパフォーマンスが重要な場合は、組み込み型を返すキー関数の使用を検討してください:

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

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

あとがき

特に Python において、時期尚早な最適化は悪です。

CPython の特定の最適化を中心にアプリケーション全体を設計するべきではありませんが、これらの最適化を意識することは良いことです。ツールをよく理解することは、より熟練した開発者になる方法です。

次のような最適化に留意すると、状況に応じて、特にパフォーマンスが重要になったときに最適化を活用できます。

並べ替えがタイムスタンプに基づいているシナリオを考えてみましょう。日時オブジェクトの代わりに同種の整数リスト (Unix タイムスタンプ) を使用すると、この最適化を効果的に活用できます。

ただし、コードの可読性と保守性がそのような最適化よりも優先されるべきであることを覚えておくことが重要です。

これらの低レベルの詳細を知ることは重要ですが、Python を生産性の高い言語にしている高レベルの抽象化を理解することも同じくらい重要です。

Python は素晴らしい言語であり、その奥深くを探求すると、Python をより深く理解し、より優れた Python プログラマーになることができます。