オブジェクトをソートするには以下の２通りのどちらかで実現できる。
- オブジェクト自身が比較の方法を知っている
- オブジェクトの比較方法を表す関数(オブジェクト)を渡す
2.の例を見てみよう。リストのsort()メソッドに比較用の関数(cmpの特性を持つ関数)を渡している。
>>> L = range(5)
>>> L
[0, 1, 2, 3, 4]
>>> L.sort(lambda x, y: cmp(y, x))
>>> L
[4, 3, 2, 1, 0]
cmpの特性を持っていれば、呼び出し可能オブジェクトを渡しても良い。
>>> class AttrCmp:
... def __init__(self, attr):
... self.attr = attr
... def __call__(self, x, y):
... return cmp(getattr(x, self.attr), getattr(y, self.attr))
...
>>> class Foo:
... def __init__(self, n, s):
... self.n, self.s = n, s
... def __repr__(self):
... return 'Foo(%d, %s)' % (self.n, self.s)
...
>>> L = [Foo(3, 'b'), Foo(2, 'c'), Foo(1, 'd'), Foo(4, 'a')]
>>> L.sort(AttrCmp('s'))
>>> L
[Foo(4, a), Foo(3, b), Foo(2, c), Foo(1, d)]
>>> L.sort(AttrCmp('n'))
>>> L
[Foo(1, d), Foo(2, c), Foo(3, b), Foo(4, a)]
但し、比較関数を渡す方法は、オブジェクトの比較の度に比較関数が呼び出されるので
キーx、yを取り出すのが、それぞれ O(n log(n)) 回かかり、キーの比較自体も O(n log(n)) 回かかる。
以下のように、先に(key, obj)のリストを作りソートすれば
キーの取り出しが O(n) 回、比較が O(n log(n)) となり、キーの取り出しに時間がかかる
ケースではかなり早くなる。
>>> def sortby(seq, n):
... seq2 = [(obj[n], obj) for obj in seq]
... seq2.sort()
... return [obj for (key, obj) in seq2]
...
>>> seq = [(1, 'cd'), (2, 'ef'), (3, 'ab')]
>>> sortby(seq, 1)
[(3, 'ab'), (1, 'cd'), (2, 'ef')]
これは、 DecorateSortUndecorate (DSU) と呼ばれているテクニックである。
タプル(リスト)のソートの特性を利用して、(key, obj)のタプルを作り
ソートしている。但し、気をつけなければならないのは、第１要素のキーの値が同じ値だった場合に
第２要素が比較されてしまうので、重複のキーが存在する場合は、第２要素にobjのインデックス番号
を追加する必要がある。
Python 2.4からsort()メソッドやsorted()関数で、DSUをネイティブにサポートしている。
キーワード引数 key を使用し、キーを取得する関数(オブジェクト)を指定できる。
すると内部でDSUが使用される。使い方は以下の通り。
>>> import operator
>>> seq = [(1, 'cd'), (2, 'ef'), (3, 'ab')]
>>> sorted(seq, key=operator.itemgetter(1))
[(3, 'ab'), (1, 'cd'), (2, 'ef')]
オブジェクトの属性をキーにする事もできる。
>>> import operator
>>> class Foo:
... def __init__(self, n, s):
... self.n, self.s = n, s
... def __repr__(self):
... return 'Foo(%d, %s)' % (self.n, self.s)
...
>>> L = [Foo(3, 'b'), Foo(2, 'c'), Foo(1, 'd'), Foo(4, 'a')]
>>> L.sort(key=operator.attrgetter('s'))
>>> L
[Foo(4, a), Foo(3, b), Foo(2, c), Foo(1, d)]
つまり、sort()やsorted()に指定する関数(オブジェクト)は、
シーケンスの要素を引数に1つ取り、キーの値を返値とする
という特性を持っていれば良い。
以下は、大文字小文字を区別せずに文字列をソートする。
>>> 'This is how to sort words by case insensitive.'.split()
['This', 'is', 'how', 'to', 'sort', 'words', 'by', 'case', 'insensitive.']
>>> sorted(_, key=str.lower)
['by', 'case', 'how', 'insensitive.', 'is', 'sort', 'This', 'to', 'words']