Python: オブジェクトのソートについて

Python のソートについてイマイチちゃんと理解していなかったので、ここで一旦まとめてみる。

すべての基本となる sorted() 関数

まず、ソートの基本となるのが組み込み関数の sorted() だ。 これはイテレータを引数に取って、内容を整列させたリストを返すように作られている。 例えば整数型のオブジェクトを詰め込んだリストをソートしてみよう。

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

デフォルトでは上記のように昇順でソートされるが、降順にしたい場合は reverse 引数を真にする。

>>> sorted([5, 2, 3, 1, 4], reverse=True)
[5, 4, 3, 2, 1]

引数はイテレータプロトコルが実装されているオブジェクトなら、なんでも受け取ることができるようだ。 例えば辞書型のオブジェクトを渡してみよう。

>>> sorted({15: 'f', 14: 'e', 13: 'd', 12: 'c', 11: 'b', 10: 'a'})
[10, 11, 12, 13, 14, 15]

辞書のキーとなるオブジェクトがソートされた状態で返ってきた。

これは辞書型をイテレータとして解釈すると、キーのオブジェクトが返ってくるためだろう。

>>> list(iter({15: 'f', 14: 'e', 13: 'd', 12: 'c', 11: 'b', 10: 'a'}))
[10, 11, 12, 13, 14, 15]

整数以外のソート

ソートはオブジェクトが整数でなくてもできる。

例えば文字列のリストをソートしてみよう。

>>> sorted(['e', 'b', 'c', 'a', 'd'])
['a', 'b', 'c', 'd', 'e']

ちゃんとアルファベット順でソートされた。

これは文字列が整数と同じように比較できるオブジェクトだから可能となっている。

>>> 1 < 2
True
>>> 'a' < 'b'
True

注意点としては、文字列の場合は大文字のほうが小さいものとして扱われるところだろう。

>>> sorted(['a1', 'b1', 'A2', 'B2'])
['A2', 'B2', 'a1', 'b1']

ソートのされ方をカスタマイズする

先ほどの例では大文字は小文字よりも小さいものとして扱われていた。 では、これを大文字と小文字の区別なくアルファベット順でソートできるようにしてみよう。 これには sorted() 関数の key 引数を使うと上手くいく。 この key 引数は、ひとつの引数を取ってひとつの返り値を返す関数を受け取る。

sorted() 関数の key 引数に str.lower() 関数を渡した状態でソートしてみよう。

>>> sorted(['a1', 'b1', 'A2', 'B2'], key=str.lower)
['a1', 'A2', 'b1', 'B2']

先ほどとはソートのされ方が変わった。 単純に比較すると大きいはずの小文字の要素が大文字の要素の前にきている。 つまり、大文字と小文字の区別なくアルファベット順にソートされている。

これは key 引数に渡された関数が各要素に適用された状態で大小比較が行われたためだ。 ようするに、次のような状態でソートが行われたと考えればいい。

>>> [str.lower(s) for s in ['a1', 'b1', 'A2', 'B2']]
['a1', 'b1', 'a2', 'b2']

ただし、ソートされた内容は key 引数に渡した関数が適用されていない元のオブジェクトのままになっている。 あくまでオブジェクトの大小を比較するタイミングで関数が適用されている点に注意しよう。

この key 引数には他にも色々な使い方がある。 例えば、次のようなタプルの入ったリストを、ふたつ目の要素 (インデックスでいえば 1) でソートしたい場合を考えてみよう。

>>> user_tuples = [
...     ('foo', 15),
...     ('bar', 10),
...     ('baz', 20),
... ]

この場合は key 引数にふたつ目の要素を返す関数を渡すと上手くいく。 これくらい単純なものであれば lambda 式を使って匿名関数で渡してしまうと楽だろう。

>>> sorted(user_tuples, key=lambda t: t[1])
[('bar', 10), ('foo', 15), ('baz', 20)]

結果を確認すると、ちゃんとふたつ目の要素で照準ソートされていることがわかる。 考え方としては先ほどと同様に、タプルのふたつ目の要素だけが抽出された状態でオブジェクトのソートが行われたようにイメージしよう。

このテクニックはクラスインスタンスにも適用できる。 例えば、次のように名前 (name) と年齢 (age) をもったクラス (User) があるとする。

>>> class User(object):
...     def __init__(self, name, age):
...         self.name = name
...         self.age = age
...     def __repr__(self):
...         return repr((self.name, self.age))
...

クラスをインスタンス化してリストに詰めておこう。 このリストを年齢 (age) でソートしたい。

>>> user_objs = [
...     User('foo', 15),
...     User('bar', 10),
...     User('baz', 20),
... ]

この場合も、先ほどと同じようにオブジェクトを受け取って、その中の要素 age を返すような関数を渡してやれば上手くいく。

>>> sorted(user_objs, key=lambda u: u.age)
[('bar', 10), ('foo', 15), ('baz', 20)]

先ほどの key 引数の使われ方はよく登場するようなので、それ用のユーティリティ関数が標準ライブラリの operator モジュールに存在するようだ。 例えばリストやタプルのふたつ目の要素をソートに使いたい、という場合には operator.itemgetter() 関数が使える。

>>> from operator import itemgetter
>>> sorted(user_tuples, key=itemgetter(1))
[('bar', 10), ('foo', 15), ('baz', 20)]

同様に、クラスインスタンスの特定の要素をソートに使いたい、という場合には operator.attrgetter() 関数の出番となる。

>>> from operator import attrgetter
>>> sorted(user_objs, key=attrgetter('age'))
[('bar', 10), ('foo', 15), ('baz', 20)]

このユーティリティ関数を使うと、ソートに使う要素を複数指定することもできる。 例えば年齢を第一キーとしてソートした後に、名前を第二キーとしてソートする、といった寸法だ。 次の例では年齢がすべての要素で同じため、結果として第二キーの名前を使ってソートが行われることになる。

>>> user_tuples2 = [
...     ('b', 10),
...     ('a', 10),
...     ('c', 10),
... ]
>>> sorted(user_tuples2, key=itemgetter(1, 0))
[('a', 10), ('b', 10), ('c', 10)]

使ってはいけない引数

ソートのされ方をカスタマイズする古いやり方として sorted() 関数に cmp 引数を渡すというものがある。 これは、ふたつのオブジェクトを受け取って大小関係を数値で表す関数を cmp 引数に渡すことでソートのされ方をカスタマイズする、というものだった。 大小関係を数値で表すというのは、ひとつ目の要素よりふたつ目の要素の方が大きい場合には 1 以上を、等しければ 0 を、小さい場合には 0 未満を返すというもの。

例えば次の例では cmp 引数に数値型の昇順ソートを実装した compare() 関数を渡している。

>>> def compare(x, y):
...     return x - y
... 
>>> sorted([5, 2, 3, 1, 4], cmp=compare)
[1, 2, 3, 4, 5]

しかし、このやり方はもはや古いので使ってはいけない。 Python 3.x では sorted() 関数から cmp 引数が廃止されているので、そもそも動かない。

ユーザ定義クラスのインスタンスをソートする

前述した sorted() 関数の key 引数を使うやり方でもユーザ定義クラスのインスタンスをソートすることはできた。 しかし、より複雑なソートのルールを書きたい場合、ソースコードが分かりづらくなってしまうだろう。 そんなときはクラス側でソートのされ方を定義することもできる。

次のサンプルコードを見てほしい。 今度の User クラスでは、特殊メソッドの __lt__() を実装している。 特殊メソッドの __lt__() というのは、ふたつのオブジェクトを '<' 演算子で比較する際に呼び出されるメソッドだ。 実は、Python ではユーザ定義クラスをソートする際には、この __lt__() メソッドが使われることが仕様となっている。 つまり、ユーザ定義クラスを sorted() 関数で何も指定せずソートしたい場合には、__lt__() メソッドを実装すれば良いということだ。

#!/usr/bin/env python
# -*- coding: utf-8 -*-


class User(object):

    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __lt__(self, other):
        # self < other
        return self.age < other.age

    def __repr__(self):
        return repr((self.name, self.age))


def main():
    users = [
        User('foo', 15),
        User('bar', 10),
        User('baz', 20),
    ]
    sorted_users = sorted(users)
    print(sorted_users)


if __name__ == '__main__':
    main()

上記のサンプルコードを実行してみよう。

$ python userclass.py 
[('bar', 10), ('foo', 15), ('baz', 20)]

ちゃんと 'age' の要素でソートされていることがわかる。

sorted() 関数を使わないやり方

ちなみに、使えるのはリスト型のオブジェクトに限られるものの sorted() 関数を使わずにソートするやり方もある。 それはリスト型に存在する sort() メソッドを使うというものだ。 こちらは sorted() 関数とは違って、ソートされた新しいリストを返すのではなく、今のリストを破壊的にインプレースでソートする。

>>> l = [5, 2, 3, 1, 4]
>>> l.sort()
>>> l
[1, 2, 3, 4, 5]

まとめ

• Python でオブジェクトをソートするには組み込み関数 sorted() を使う (リストであれば list#sort() も使える)
• sorted() 関数はイテレータプロトコルを実装したオブジェクトを受け取ってリストを返す
• 整数型以外のオブジェクトでもソートできる
• ソートを降順にしたいときは sorted() 関数の reverse 引数を真にする
• ソートのされ方をカスタマイズしたいときは sorted() 関数の key 引数を使うと良い
• 標準ライブラリの operator モジュールにあるユーティリティ関数が便利
• sorted() 関数の cmp 引数は Python 3.x にはないので使ってはいけない
• ユーザ定義クラスをソートできるようにするには、特殊メソッドの __lt__() を実装する

そんなかんじで。

スマートPythonプログラミング: Pythonのより良い書き方を学ぶ