並べ替え方法
- 著者
- アンドリュー・ダルケとレイモンド・ヘッティンガー
- リリース
- 0.1
Pythonリストには、リストをインプレースで変更する組み込みのlist.sort()
メソッドがあります。 反復可能オブジェクトから新しいソート済みリストを作成する sorted()組み込み関数もあります。
このドキュメントでは、Pythonを使用してデータを並べ替えるためのさまざまな手法について説明します。
並べ替えの基本
単純な昇順ソートは非常に簡単です。 sorted()関数を呼び出すだけです。 新しいソート済みリストを返します。
>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]
リストのlist.sort()
メソッドを使用することもできます。 リストをインプレースで変更します(混乱を避けるためにNone
を返します)。 通常は sorted()よりも便利ではありませんが、元のリストが必要ない場合は、少し効率的です。
>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]
もう1つの違いは、list.sort()
メソッドはリストに対してのみ定義されていることです。 対照的に、 sorted()関数は任意の反復可能関数を受け入れます。
>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]
主な機能
Python 2.4以降、list.sort()
と sorted()の両方に key パラメーターが追加され、比較を行う前に各リスト要素で呼び出される関数を指定しました。
たとえば、大文字と小文字を区別しない文字列の比較を次に示します。
>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
key パラメーターの値は、単一の引数を取り、ソートの目的で使用するキーを返す関数である必要があります。 キー関数は入力レコードごとに1回だけ呼び出されるため、この手法は高速です。
一般的なパターンは、オブジェクトのインデックスの一部をキーとして使用して、複雑なオブジェクトを並べ替えることです。 例えば:
>>> student_tuples = [
... ('john', 'A', 15),
... ('jane', 'B', 12),
... ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2]) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
同じ手法が、名前付き属性を持つオブジェクトに対しても機能します。 例えば:
>>> class Student:
... def __init__(self, name, grade, age):
... self.name = name
... self.grade = grade
... self.age = age
... def __repr__(self):
... return repr((self.name, self.grade, self.age))
>>> student_objects = [
... Student('john', 'A', 15),
... Student('jane', 'B', 12),
... Student('dave', 'B', 10),
... ]
>>> sorted(student_objects, key=lambda student: student.age) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
オペレータモジュールの機能
上記のキー関数パターンは非常に一般的であるため、Pythonには、アクセサー関数をより簡単かつ高速にする便利な関数が用意されています。 オペレーターモジュールには operator.itemgetter()、 operator.attrgetter()があり、Python2.5以降では operator.methodcaller()関数があります。
これらの関数を使用すると、上記の例はより単純で高速になります。
>>> from operator import itemgetter, attrgetter
>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
オペレータモジュール機能により、複数レベルのソートが可能です。 たとえば、 grade で並べ替えてから、 age で並べ替えるには、次のようにします。
>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
operator.methodcaller()関数は、並べ替えられる各オブジェクトの固定パラメーターを使用してメソッド呼び出しを行います。 たとえば、 str.count()メソッドを使用して、メッセージ内の感嘆符の数をカウントすることにより、メッセージの優先度を計算できます。
>>> from operator import methodcaller
>>> messages = ['critical!!!', 'hurry!', 'standby', 'immediate!!']
>>> sorted(messages, key=methodcaller('count', '!'))
['standby', 'hurry!', 'immediate!!', 'critical!!!']
上昇と下降
list.sort()
と sorted()はどちらも、ブール値を持つ reverse パラメーターを受け入れます。 これは、降順のソートにフラグを立てるために使用されます。 たとえば、学生データを年齢の逆の順序で取得するには、次のようにします。
>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
ソートの安定性と複雑なソート
Python 2.2以降、並べ替えは安定であることが保証されています。 つまり、複数のレコードが同じキーを持っている場合、元の順序が保持されます。
>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]
blue の2つのレコードが元の順序を保持しているため、('blue', 1)
が('blue', 2)
に先行することが保証されていることに注意してください。
この素晴らしいプロパティを使用すると、一連の並べ替え手順で複雑な並べ替えを作成できます。 たとえば、 grade を降順で age を昇順で並べ替えるには、最初に age 並べ替えを実行してから、 grade を使用してもう一度並べ替えます。 ]:
>>> s = sorted(student_objects, key=attrgetter('age')) # sort on secondary key
>>> sorted(s, key=attrgetter('grade'), reverse=True) # now sort on primary key, descending
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
Pythonで使用される Timsort アルゴリズムは、データセットにすでに存在する任意の順序を利用できるため、複数の並べ替えを効率的に実行します。
デコレート-ソート-アンデコレートを使用した古い方法
このイディオムは、次の3つのステップの後で、Decorate-Sort-Undecorateと呼ばれます。
- まず、初期リストは、ソート順を制御する新しい値で装飾されます。
- 次に、装飾されたリストがソートされます。
- 最後に、装飾が削除され、新しい順序の初期値のみを含むリストが作成されます。
たとえば、DSUアプローチを使用して、学生データを grade で並べ替えるには次のようにします。
>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated] # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
タプルは辞書式に比較されるため、このイディオムは機能します。 最初の項目が比較されます。 それらが同じである場合、2番目の項目が比較されます。
すべての場合に、装飾リストにインデックス i を含める必要はありませんが、含めると2つの利点があります。
- 並べ替えは安定しています– 2つのアイテムが同じキーを持っている場合、それらの順序は並べ替えられたリストに保持されます。
- 装飾されたタプルの順序は最大で最初の2つのアイテムによって決定されるため、元のアイテムは比較可能である必要はありません。 したがって、たとえば、元のリストには、直接ソートできない複素数が含まれている可能性があります。
このイディオムの別名は、RandalLにちなんでシュワルツ変換です。 Perlプログラマーの間でそれを普及させたSchwartz。
大きなリストや比較情報の計算に費用がかかるリスト、および2.4より前のPythonバージョンの場合、DSUがリストを並べ替える最速の方法である可能性があります。 2.4以降では、主要な機能が同じ機能を提供します。
cmp パラメータを使用した古い方法
このHOWTOに記載されている多くの構成は、Python2.4以降を想定しています。 それ以前は、 sorted()が組み込まれておらず、list.sort()
はキーワード引数を取りませんでした。 代わりに、すべてのPy2.xバージョンは、ユーザー指定の比較関数を処理するために cmp パラメーターをサポートしていました。
Python 3では、 cmp パラメーターが完全に削除されました(言語を単純化および統合するためのより大きな努力の一環として、豊富な比較と__cmp__()
マジックメソッドの間の競合を排除しました)。
Python 2では、sort()
は、比較を行うために呼び出すことができるオプションの関数を許可していました。 この関数は、比較する2つの引数を取り、より小さい場合は負の値を返すか、等しい場合はゼロを返すか、より大きい場合は正の値を返す必要があります。 たとえば、次のことができます。
>>> def numeric_compare(x, y):
... return x - y
>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare)
[1, 2, 3, 4, 5]
または、次の方法で比較の順序を逆にすることもできます。
>>> def reverse_numeric(x, y):
... return y - x
>>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric)
[5, 4, 3, 2, 1]
Python 2.xから3.xにコードを移植する場合、ユーザーが比較関数を提供し、それをキー関数に変換する必要がある場合に状況が発生する可能性があります。 次のラッパーを使用すると、これを簡単に実行できます。
def cmp_to_key(mycmp):
'Convert a cmp= function into a key= function'
class K(object):
def __init__(self, obj, *args):
self.obj = obj
def __lt__(self, other):
return mycmp(self.obj, other.obj) < 0
def __gt__(self, other):
return mycmp(self.obj, other.obj) > 0
def __eq__(self, other):
return mycmp(self.obj, other.obj) == 0
def __le__(self, other):
return mycmp(self.obj, other.obj) <= 0
def __ge__(self, other):
return mycmp(self.obj, other.obj) >= 0
def __ne__(self, other):
return mycmp(self.obj, other.obj) != 0
return K
キー関数に変換するには、古い比較関数をラップするだけです。
>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))
[5, 4, 3, 2, 1]
Python 2.7では、 functools.cmp_to_key()関数がfunctoolsモジュールに追加されました。
奇数と終わり
ロケール対応の並べ替えの場合、キー関数には locale.strxfrm()を使用し、比較関数には locale.strcoll()を使用します。
reverse パラメーターは、ソートの安定性を維持します(したがって、同じキーを持つレコードは元の順序を保持します)。 興味深いことに、その効果は、組み込みの reverse()関数を2回使用することにより、パラメーターなしでシミュレートできます。
>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)] >>> standard_way = sorted(data, key=itemgetter(0), reverse=True) >>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0)))) >>> assert standard_way == double_reversed >>> standard_way [('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]
クラスの標準の並べ替え順序を作成するには、適切な豊富な比較メソッドを追加するだけです。
>>> Student.__eq__ = lambda self, other: self.age == other.age >>> Student.__ne__ = lambda self, other: self.age != other.age >>> Student.__lt__ = lambda self, other: self.age < other.age >>> Student.__le__ = lambda self, other: self.age <= other.age >>> Student.__gt__ = lambda self, other: self.age > other.age >>> Student.__ge__ = lambda self, other: self.age >= other.age >>> sorted(student_objects) [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
汎用比較の場合、推奨されるアプローチは、6つの豊富な比較演算子すべてを定義することです。 functools.total_ordering()クラスデコレータを使用すると、これを簡単に実装できます。
主要な機能は、ソートされるオブジェクトに直接依存する必要はありません。 キー機能は外部リソースにもアクセスできます。 たとえば、学生の成績が辞書に保存されている場合、それらを使用して、学生名の個別のリストを並べ替えることができます。
>>> students = ['dave', 'john', 'jane'] >>> grades = {'john': 'F', 'jane':'A', 'dave': 'C'} >>> sorted(students, key=grades.__getitem__) ['jane', 'dave', 'john']