Sorting Mini-HOWTO （和訳）

概要

この文書は、sort() 組み込みメソッドを使って、リストをソートする方法を紹介する、ちょっとしたチュートリアルです。

この文書の原文は、http://www.python.org/doc/howto/ の Python HOWTO ページから、PostScript、PDF、HTML、アスキーテキストを含む、各種フォーマットで入手できます。

目次

1. 基本的なデータ型のソート
2. クラスの比較
3. 翻訳について

Python のリスト型には、sort() という組み込み関数があります。 リストをソートするには様々な方法があって、色々なマニュアルがあるのですが、ひとつの集約的な文書はありません。 そこで、私が書くことにしました。

1 基本的なデータ型のソート

単純な昇順ソートは簡単です。 リスト・オブジェクトの sort() メソッドを呼び出せば事足ります。

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

sort() に対して、リスト内の要素を比較するときに呼び出す関数を指定することもできます。 デフォルトのソート処理は以下のものと同等です。

>>> a = [5, 2, 3, 1, 4]
>>> a.sort(cmp)
>>> print a
[1, 2, 3, 4, 5]

ここで cmp は、2つのオブジェクト x、y を比較する組み込み関数で、x < y、x == y、x > y のとき、戻り値はそれぞれ、-1、0、1 となります。 正確なソートのためには、最後までこの関係が同じでなければいけません。

比較のための関数を定義することもできます。 整数（数値一般）に対してなら、次のようになるでしょう。

>>> def numeric_compare(x, y):
>>>    return x - y
>>> 
>>> a = [5, 2, 3, 1, 4]
>>> a.sort(numeric_compare)
>>> print a
[1, 2, 3, 4, 5]

代入の結果が型が扱える範囲、つまり sys.maxint - (-1) を超える場合には、この関数は使えません。

また、新しく名前のついた関数を定義せずに、lambda を使って、名無しの関数を定義することもできます。

>>> a = [5, 2, 3, 1, 4]
>>> a.sort(lambda x, y: x - y)
>>> print a
[1, 2, 3, 4, 5]

次のようにすれば、逆順に数値をソートできます。

>>> a = [5, 2, 3, 1, 4]
>>> def reverse_numeric(x, y):
>>>     return y - x
>>> 
>>> a.sort(reverse_numeric)
>>> print a
[5, 4, 3, 2, 1]

（cmp(y, x) または -cmp(x, y)を返すように作るほうが一般的です）

しかし、Python は、比較の度に関数を呼び出さないほうが速く動作します。 ですから、リストを降順にソートしたいときには、まず昇順にソートしてから、reverse() メソッドを用いましょう。

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a.reverse()
>>> print a
[1, 2, 3, 4, 5]

次のプログラムは、lambda 関数を使って、大文字・小文字を区別せずに文字列を比較する方法です。

>>> import string
>>> a = string.split('This is a test string from Andrew.')
>>> a.sort(lambda x, y: cmp(string.lower(x), string.lower(y)))
>>> print a
['a', 'Andrew.', 'from', 'is', 'string', 'test', 'This']

この方法では、比較する度に文字列を小文字に変換することによって生じる、オーバーヘッドがかかります。 比較の回数が多いのなら、以下の例に示すように、1度だけ変換しておいて使い回すほうが早くなるかも知れません。

>>> words = string.split('This is a test string from Andrew.')
>>> offsets = []
>>> for i in range(len(words)):
>>>     offsets.append((string.lower(words[i]), i))
>>> 
>>> offsets.sort()
>>> new_words = []
>>> for dontcare, i in offsets:
>>>      new_words.append(words[i])
>>> 
>>> print new_words

offsets リストは、小文字の文字列と、words リスト内での位置のタプルで初期化されてからソートされます。 Python の sort() メソッドが、タプルをソートするときには、比較する項目 x と y に対して、まず x[0] と y[0] を比較し、次に x[1] と y[1] を比較し…、と、違った部分が出てくるまで繰り返します。

結果として、offsets リストは、最初の項目でソートされて、2つ目の項目は元のデータが（最初のリストの）何番目にあるかを見つけるのに使われます。 （for ループで、タプルの2項目を取り出すためにdontcare と i が指定されますが、必要なのはインデックスの値だけです。）

別な方法として、元のデータを offsets リストの2つ目の項目として保存することもできます。

>>> words = string.split('This is a test string from Andrew.')
>>> offsets = []
>>> for word in words:
>>>     offsets.append((string.lower(word), word))
>>> 
>>> offsets.sort()
>>> new_words = []
>>> for word in offsets:
>>>     new_words.append(word[1])
>>> 
>>> print new_words

これは常に適切に動作するとは限りません。 リストの1つ目の項目が同じだった場合、2つ目の項目（この例では、word）が比較されるからです。 これが頻繁に起これば、2つのオブジェクトを比較することによって、不必要に性能が低下します。 ほとんどの項目が同じで、オブジェクト独自の __cmp__ メソッドを定義していれば、これは大きな計算コストになり得ます。しかし、__cmp__ が定義されているかどうか確認するのにも、いくらかのオーバーヘッドがかかります。

それでも、大きなリストや、比較する情報を比較するのが時間をとるようなリストでは、後の2つの例が、最も高速にリストをソートする方法でしょう。 複素数のような、ソートしにくいデータには使えないのですが、これが何のことだか分からないのであれば、心配することはありません。

2 クラスの比較

整数と整数、文字列と文字列のような、基本的なデータ型の比較は、Python に組み込まれていますし、それでうまくいきます。 クラスのインスタンスを比較するためのデフォルトの方法がありますが、あまり役に立つ代物ではありません。 __cmp__ メソッドを使えば、比較方法を定義できます。

>>> class Spam:
>>>     def __init__(self, spam, eggs):
>>>         self.spam = spam
>>>         self.eggs = eggs
>>>     def __cmp__(self, other):
>>>         return cmp(self.spam + self.eggs, other.spam + other.eggs)
>>>     def __str__(self):
>>>         return str(self.spam + self.eggs)
>>> 
>>> a = [Spam(1, 4), Spam(9, 3), Spam(4, 6)]
>>> a.sort()
>>> for spam in a:
>>>   print str(spam)
5
10
12

場合によっては、クラスの特定の属性でソートしたいと思うかもしれません。 __cmp__ メソッドを定義して、これらの値を比較するべきです。 しかし、この方法では、その時々で、異なったの属性を比較するような場合には使えません。 その場合には、次に示すように、比較用の関数を受け渡すという方法に立ち返る必要があります。

>>> a = [Spam(1, 4), Spam(9, 3), Spam(4, 6)]
>>> a.sort(lambda x, y: cmp(x.eggs, y.eggs))
>>> for spam in a:
>>>   print spam.eggs, str(spam)
3 12
4 5
6 10

任意の2つの属性を比較したいなら（そして、パフォーマンスをあまり気にしないなら）、比較用の関数オブジェクトを定義することもできます。 この方法では、クラス・インスタンスに、関数をエミュレートさせられることを利用し、次のような __call__ メソッドを定義します。

>>> class CmpAttr:
>>>     def __init__(self, attr):
>>>         self.attr = attr
>>>     def __call__(self, x, y):
>>>         return cmp(getattr(x, self.attr), getattr(y, self.attr))
>>> 
>>> a = [Spam(1, 4), Spam(9, 3), Spam(4, 6)]
>>> a.sort(CmpAttr('spam'))  # sort by the 'spam' attribute
>>> for spam in a:
>>>    print spam.spam, spam.eggs, str(spam)
1 4 5
4 6 10
9 3 12

>>> a.sort(CmpAttr('eggs'))  # re-sort by the 'eggs' attribute
>>> for spam in a:
>>>    print spam.spam, spam.eggs, str(spam)
9 3 12
1 4 5
4 6 10

もちろん、より高速にソートするには、属性を作業用のリストに展開してから、ソートすることもできます。

というわけで、リストをソートするには、半ダースほどの異なった方法があるということです。

• デフォルトのメソッドを使ってソートする
• 比較用の関数を使ってソートする
• 比較用の関数を使って、逆順でソートする
• 中間リスト（2種類あります）を使ってソートする
• クラスの __cmp__ メソッドを使ってソートする
• 関数オブジェクトを使ってソートする

3 翻訳について

この文書は、Andrew Dalke 氏による Sorting Mini-HOWTO を和訳したものです。原文の数式画像は、テキストに書き換えてあります。また、PyJUG サイトに掲載するにあたり、HTML を一部変更しました。