ソート HOW TO
*************

Author:
   Andrew Dalke and Raymond Hettinger

Release:
   0.1

Python のリストにはリストをインプレースに変更する、組み込みメソッド
"list.sort()" があります。他にもイテラブルからソートしたリストを作成す
る組み込み関数 "sorted()" があります。

このドキュメントでは Python を使った様々なソートのテクニックを探索しま
す。


ソートの基本
============

単純な昇順のソートはとても簡単です: "sorted()" 関数を呼ぶだけです。そ
うすれば、新たにソートされたリストが返されます:

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

You can also use the "list.sort()" method of a list. It modifies the
list in-place (and returns "None" to avoid confusion). Usually it’s
less convenient than "sorted()" - but if you don’t need the original
list, it’s slightly more efficient.

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

違いは他にもあります、 "list.sort()" メソッドはリストにのみ定義されて
います。一方 "sorted()" 関数は任意のイテラブルを受け付けます。

>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]


Key 関数
========

Starting with Python 2.4, both "list.sort()" and "sorted()" added a
*key* parameter to specify a function to be called on each list
element prior to making comparisons.

例えば、大文字小文字を区別しない文字列比較の例:

>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

*key* パラメータは単一の引数をとり、ソートに利用される key を返さなけ
ればいけません。この制約によりソートを高速に行えます、キー関数は各入力
レコードに対してきっちり一回だけ呼び出されるからです。

よくある利用パターンはいくつかの要素から成る対象をインデクスのどれかを
キーとしてソートすることです。例えば:

>>> 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)]

同じテクニックは名前づけされた属性 (named attributes) を使うことでオブ
ジェクトに対しても動作します。例えば:

>>> 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)]


operator モジュール関数
=======================

The key-function patterns shown above are very common, so Python
provides convenience functions to make accessor functions easier and
faster. The operator module has "operator.itemgetter()",
"operator.attrgetter()", and starting in Python 2.5 an
"operator.methodcaller()" function.

これらの関数を利用すると、上の例はもっと簡単で高速になります:

>>> 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)]

operator モジュールの関数は複数の段階でのソートを可能にします。例えば
、 *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)]

The "operator.methodcaller()" function makes method calls with fixed
parameters for each object being sorted.  For example, the
"str.count()" method could be used to compute message priority by
counting the number of exclamation marks in a message:

>>> from operator import methodcaller
>>> messages = ['critical!!!', 'hurry!', 'standby', 'immediate!!']
>>> sorted(messages, key=methodcaller('count', '!'))
['standby', 'hurry!', 'immediate!!', 'critical!!!']


昇順と降順
==========

"list.sort()" と "sorted()" の両方とも *reverse* パラメータを 真偽値と
して受け付けます。このパラメータは降順ソートを行うかどうかの フラグと
して利用されます。 例えば、学生のデータを *age* の逆順で得たい場合:

>>> 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)]


ソートの安定性と複合的なソート
==============================

Starting with Python 2.2, sorts are guaranteed to be stable. That
means that when multiple records have the same key, their original
order is preserved.

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

二つの *blue* のレコートが元々の順序を維持して、 "('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)]

このイディオムはタブルが辞書編集的に比較されるため正しく動作します; 最
初の要素が比較され、同じ場合には第二の要素が比較され、以下も同様に動き
ます。

デコレートしたリストのインデクス *i* は全ての場合で含まれる必要はあり
ませんが、そうすることで二つの利点があります:

* ソートが安定になります – もし二つの要素が同じキーを持つ場合、それ
  ら の順序がソートされたリストでも維持されます。

* 元々の要素が比較可能な要素を持つとは限りません、なぜならデコレート
  さ れたタブルの順序は多くの場合、最初の二つの要素で決定されるからで
  す。 例として元のリストは直接比較できない複素数を含むことができます
  。

このイディオムの別名に Schwartzian transform があります。これは Perl
プログラマの間で有名な Randal L. Schwartz にちなんでいます。

For large lists and lists where the comparison information is
expensive to calculate, and Python versions before 2.4, DSU is likely
to be the fastest way to sort the list. For 2.4 and later, key
functions provide the same functionality.


*cmp* パラメータを利用した古い方法
==================================

この HOWTO の内容の多くは Python 2.4 以降を仮定しています。それ以前で
は組み込み関数 "sorted()" と "list.sort()" はキーワード引数をとりませ
んでした。その代わりに Py2.x バージョンの全ては、ユーザが比較関数を指
定するための *cmp* パラメーターをサポートしました。

In Python 3, the *cmp* parameter was removed entirely (as part of a
larger effort to simplify and unify the language, eliminating the
conflict between rich comparisons and the "__cmp__()" magic method).

In Python 2, "sort()" allowed an optional function which can be called
for doing the comparisons. That function should take two arguments to
be compared and then return a negative value for less-than, return
zero if they are equal, or return a positive value for greater-than.
For example, we can do:

>>> def numeric_compare(x, y):
...     return x - y
>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare) # doctest: +SKIP
[1, 2, 3, 4, 5]

また、比較順を逆にすることもできます:

>>> def reverse_numeric(x, y):
...     return y - x
>>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric) # doctest: +SKIP
[5, 4, 3, 2, 1]

Python 2.x から 3.x にコードを移植する場合、比較関数を持っている場合に
は key 関数に比較しなければならないような状況に陥るかもしれません。以
下のラッパーがそれを簡単にしてくれるでしょう:

   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

key 関数を変換するには、古い比較関数をラップするだけです:

   >>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))
   [5, 4, 3, 2, 1]

In Python 2.7, the "functools.cmp_to_key()" function was added to the
functools module.


残りいくつかとまとめ
====================

* ロケールに配慮したソートをするには、キー関数 "locale.strxfrm()" を
  利 用するか、比較関数に "locale.strcoll()" を利用します。

* The *reverse* parameter still maintains sort stability (so that
  records with equal keys retain their original order). Interestingly,
  that effect can be simulated without the parameter by using the
  builtin "reversed()" function twice:

  >>> 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)]

* To create a standard sort order for a class, just add the
  appropriate rich comparison methods:

  >>> 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)]

  For general purpose comparisons, the recommended approach is to
  define all six rich comparison operators.  The
  "functools.total_ordering()" class decorator makes this easy to
  implement.

* key 関数はソートするオブジェクトに依存する必要はありません。 key
  関 数は外部リソースにアクセスすることもできます。例えば学生の成績が
  辞書 に保存されている場合、それを利用して別の学生の名前のリストをソ
  ートす ることができます:

  >>> students = ['dave', 'john', 'jane']
  >>> grades = {'john': 'F', 'jane':'A', 'dave': 'C'}
  >>> sorted(students, key=grades.__getitem__)
  ['jane', 'dave', 'john']
