比較特殊関数を実装していないオブジェクトに対する sort() の key パラメータを利用した並べ替え

比較特殊関数を実装していないオブジェクトに対する sort() の key パラメータを利用した並べ替え投稿一覧へ戻る

Published 2020年6月20日8:27 by T.Tsuyoshi

ご存知のように list タイプでは sort() が提供されていて、デフォルトでは要素が昇順に並べ替えられます。

numbers = [93, 86, 11, 68, 70]
numbers.sort()
print(numbers) # [11, 68, 70, 86, 93]

sort() はほぼ全ての組み込みタイプに適用可能です。

では、オブジェクトに対してはどのように機能するでしょう？

class Friend:
    def __init__(self, name: str, weight: float):
        self.name = name
        self.weight = weight

    def __repr__(self):
        return f"Friend({self.name!r}, {self.weight})"

friends = [
    Friend('Netaro', 45),
    Friend('Momotaro', 50),
    Friend('Kintaro', 88),
    Friend('Kitaro', 50),
]

friends.sort() # TypeError: '<' not supported between instances of 'Friend' and 'Friend'

エラーになりました。
これは、引数なしの sort() が Friend オブジェクトでは定義されていない比較特殊関数を必要としているからです。

ただ比較特殊関数を定義しなくても、オブジェクトが並べ替えの対象としたい属性を有している場合なら、
sort() の key パラメータにその属性値を返す関数を渡すことで通常の並べ替えを行うことができます。
当たり前ですがその返り値は比較可能なものでなければだめですよ。

print(f"並べ替え前: {friends}")

# 並べ替え前: [Friend('Netaro', 45), Friend('Momotaro', 50), Friend('Kintaro', 88), Friend('Kitaro', 50)]

friends.sort(key=lambda x: x.name)
print(f"名前で並べ替え後: {friends}")

# 名前で並べ替え後: [Friend('Kintaro', 88), Friend('Kitaro', 50), Friend('Momotaro', 50), Friend('Netaro', 45)]

もちろん key 提供関数が "weight" を与えるようにすれば体重順に並べ替えることもできます。

friends.sort(key=lambda x: x.weight)
print(f"体重で並べ替え後: {friends}")

# 体重で並べ替え後: [Friend('Netaro', 45), Friend('Kitaro', 50), Friend('Momotaro', 50), Friend('Kintaro', 88)]

では、複数の項目を対象に並べ替えをしたい場合はどうしましょうか？

最も簡単な方法はタプルを利用することかもしれません。

複数の要素から成るタプル同士の比較では、まずインデックス[0] の値の比較が行われ、もし等しければインデックス[1] で比較が行われます。

friends リストをまず体重で、続いて名前で並べ替えると次のように成ります。

friends.sort(key=lambda x: (x.weight, x.name))
print(friends)

# [Friend('Netaro', 45), Friend('Kitaro', 50), Friend('Momotaro', 50), Friend('Kintaro', 88)]

このタプルを利用した並べ替えの短所の１つは、並べ替えの順番 (昇順か降順か) が複数の比較要素すべてに同様に適用されてしまうことです。

friends.sort(key=lambda x: (x.weight, x.name), reverse=True)
print(friends)

# [Friend('Kintaro', 88), Friend('Momotaro', 50), Friend('Kitaro', 50), Friend('Netaro', 45)]

同じ体重の人 ('Momotaro' と 'Kitaro') では名前の順番も降順になってしまっています。

降順に並べ替えたい対象が数値である場合の対処は簡単です。
その値を -1 倍し、後はデフォルトの並べ替え順 (昇順) で出力するだけです。

friends.sort(key=lambda x: (-x.weight, x.name))
print(friends)

# [Friend('Kintaro', 88), Friend('Kitaro', 50), Friend('Momotaro', 50), Friend('Netaro', 45)]

体重は降順に、体重が同じ人では、名前で昇順にちゃんと並んでいます。

しかし、-1 をかけて降順にするこの方法は全てのタイプに適用できるわけではありません。
この例で name を降順にしたいからといって -x.name としても、String タイプの -1 倍はナンジャラホイ、ということでエラーになります。

このような状況を考慮して Python では stable sorting algorithm が採用されています。
これは、list タイプの sort() で並べ替えが行われる場合、対象となるリスト内の要素の順番は保持される、というものです。
つまり、比較結果が等しい場合は元々リストにセットされていた順番に値が並べられる、ということです。

このアルゴリズムを前提に、同じリストに対して異なる並べ替え基準を設定した sort() を複数回実行することで、目的とする並べ替え結果を得ることができます。

次のように並べ方の異なる sort() を２回実行して、weight はデフォルトの昇順、name は降順に並べ替えます。

friends.sort(key=lambda x: x.name, reverse=True)
friends.sort(key=lambda x: x.weight)
print(friends)

# [Friend('Netaro', 45), Friend('Momotaro', 50), Friend('Kitaro', 50), Friend('Kintaro', 88)]

全体は weight の昇順で並んでいますが、weight が等しい 'Momotaro' と 'Kitaro' は name の降順で並んでいます、大成功です！！

この方法を利用すると、比較要素数がどんなに多くても、それぞれの要素で並べ替え順序の異なる思い通りの結果を得ることができます。
大切なことは sort() をどの順番で実行するか、ということです。

ただし、おススメは key 関数からタプルを返し、-1 倍が許されているタイプに適用することで並べ替え順をリバースする方法です。
前出のようにコードもすっきりとして読解性も高くなります。
並べ替え順を指定した sort() を複数回実行する方法は、あくまでも -1 倍が許されていないタイプを対象にしなければいけないときに限りましょう。

この投稿をメールでシェアする

0 comments

コメントはまだありません。