メソッドと関数

第1章ではリスト l をソートする方法として以下の2つを紹介しました。改めて整理しておきます:

• l.sort() としてリスト l の中身を昇順(値の小さい順)に並び変える
• l2 = sorted(l) として l の中身を昇順に並べた新たなリスト l2 を作る (l の中身はそのまま)

やり方によって l の中身が変わるのかどうかが異なるので注意してください。特に、

l2 = l.sort()

のように記述しても l2 はリストにはなりません¹。

理解の確認のために以下を例を参照してください:

l = [5,4,1,3,2]
l2 = sorted(l)
print(l, l2) # l は変わっていない, l2 はソートされたリスト
l3 = l.sort()
print(l3, l) # l はソートされる, l3 は None

実行結果

[5, 4, 1, 3, 2] [1, 2, 3, 4, 5]
None [1, 2, 3, 4, 5]

数値以外をソート

リストの中身は比較可能なものであれば数値でなくてもよいです。
次の例では、文字列/タプル/リスト をそれぞれ要素にもつリストをソートしています。

l = ["ba", "ac", "a", "abc"]
l2 = [(1, 1), (0, 1), (1, 0)]
l3 = [[1, 1], [0, 1], [1, 0]]
print(l)
print(l2)
print(l2)

実行結果

['a', 'abc', 'ac', 'ba']
[(0, 1), (1, 0), (1, 1)]
[[0, 1], [1, 0], [1, 1]]

文字列は辞書順に、タプルやリストは要素の先頭から順に見ていき、最初に現れる異なる要素を比較した結果になります。

文字列と数値の比較はできない(エラーになる)ことに注意してください。

l = ["ba", 0]
print(sorted(l))
# TypeError: '<' not supported between instances of 'int' and 'str'

リスト以外をソート

sorted 関数には引数として文字列やタプルなど、リスト以外を与えることが可能です。

# 文字列 -> 各文字が辞書順でソートされ、1文字ずつのリストになる
s = "atcoder"
print(sorted(s))

# タプル -> 要素がソートされ、リストになる
a = (3, 1, 4, 1, 5)
print(sorted(a))

実行結果

['a', 'c', 'd', 'e', 'o', 'r', 't']
[1, 1, 3, 4, 5]

降順にソート

以下のように reverse=True 引数を与えることで降順(値の大きい順)にソートすることができます:

l = [1,2,3,4]
l2 = sorted(l, reverse=True)
print(l2) # [4, 3, 2, 1]

この引数は sort メソッド、sorted 関数のいずれにも与えることが可能です。

l = [1,2,3,4]
l.sort(reverse=True)
print(l) # [4, 3, 2, 1]

評価指標を与えてソート

要素の値そのものではなく、何らかの評価指標があり、それを基準としてソートをしたいときがしばしばあります。
例として、「整数値のリストを、各値の下1桁でソートする」という問題を考えましょう:

l = [2, 6, 11, 100]
# 何らかの処理を行って [100, 11, 2, 6] を得たい

このような場合、以下のいずれかの方法で実現可能です:

方法1: 評価値と元の要素からなるタプルのリストをソートする

一つ目の方法は、先ほど説明した「タプルのソート」を活用します。

1. 評価したい値と元の要素を並べたタプルのリストを作る
2. そのリストをソートする
3. 得られたリストから元の要素を抜き出す

という順で処理します。
「整数の下一桁の値」は「整数を10で割ったあまり」によって得られることに注意してください。

以下がコード例になります:

l = [2, 6, 11, 100]
l2 = [(v%10, v) for v in l] # (要素の下一桁, 要素) のリスト
print(l2) # [(2, 2), (6, 6), (1, 11), (0, 100)]
l2.sort()
print(l2) # [(0, 100), (1, 11), (2, 2), (6, 6)]
l = [item[1] for item in l2] # l2 の各要素から元の要素を抜き出す
print(l) # [100, 11, 2, 6]

方法2: ソートの引数に評価値を与える関数を渡す

ソートの関数は引数 key として関数を渡すことができます。この場合、各要素を関数の返り値が昇順になるようにソートが行われます。
今回の場合、以下のような手順になります。

1. 評価値(ここでは数値の下1桁 = 10 で割ったあまり)を計算する関数を実装
2. その関数を key 引数として渡してソートを行う

以下のような実装例になります:

l = [2, 6, 11, 100]
def func(x):
    return x % 10
l.sort(key = func)
print(l) # [100, 11, 2, 6]

# これは次のように 1 行で記述することも可能:
# l.sort(key = lambda x: x%10)

最後のコメントにあるように、前述のラムダ式を使うことで関数の名称をつけることなく評価指標を与えることも可能です。このようなラムダ式の使い方は競技プログラミングでしばしば出てくるので覚えておくとよいでしょう。
なお、引数 key は sorted 関数を用いる場合も同様に利用することができます。

この「方法2」に慣れるためにいくつかの例を出します。

# x の降順にソート : reverse 引数を使わずに以下のように書くことも可能
l = [2, 6, 11, 100]
print(sorted(l, key = lambda x: -x)) # [100, 11, 6, 2]

# タプルの2番目の要素でソート
l = [(3,1), (4,2), (0,1)]
print(sorted(l, key = lambda x: x[1])) # [(3, 1), (0, 1), (4, 2)]

補足 : 「引き分け」の場合のソート順について

上記の最後の例において、(3, 1) と (0, 1) は「タプルの2番目の要素」という評価基準では優劣が付きません。このような場合は元のリストにおける並び順を保ったままになります。上記の例では (3, 1) が (0, 1) よりも先にある、という関係が保たれていることを確認できます。
ソートがこのような性質を持つ場合、安定であるといいます。

比較基準を与えてソート

注意: 本節の内容はやや複雑ですので、飛ばして先に進んでも構いません。

前節の「評価基準を与えてソート」と少し似ていますが、2 つの要素の優劣のつけ方を指定してソートをしたいことがあります。
例として、「タプル (a,b) と (c,d) に対して、 a * d < b * c ならば (a,b) が先になるようにする」という問題を考えましょう。

l = [(3,5), (1,3), (2,4)]
# (3,5) と (1,3) の比較: 3*3 > 5*1 なので (3,5) が後
# (3,5) と (2,4) の比較: 3*4 > 5*2 なので (3,5) が後
# (1,3) と (2,4) の比較: 1*4 < 3*2 なので (1,3) が先
# 何らかの処理を行って [(1,3), (2,4), (3,5)] を得たい

この場合もソートに key 引数として関数を与えることで実現することができます。
ただし、以下の点が先ほどと異なります:

• 今回与える関数は 2 つの要素を受け取り大小比較の結果を返すように定義する必要があります。具体的には、以下を満たす必要があります:
  • 1つ目の要素が2つ目の要素よりも小さければ負の値を返す
  • 1つ目の要素と2つ目の要素が等しい場合は 0 を返す
  • 1つ目の要素が2つ目の要素よりも大きければ正の値を返す
• 比較関数関数を functools.cmp_to_key という関数でラップしておく必要があります。これは比較関数を評価関数に変換するためのラッパ関数です。なお、functools は標準モジュールのひとつで、import することで利用可能になります。

先の例は次のように記述することができます:

l = [(3,5), (1,3), (2,4)]
# 何らかの処理を行って [(1,3), (2,4), (3,5)] を得たい
def cmp(x,y):
    # x,y : 長さ2のタプル -> 書きやすさのためアンパックしておく
    a,b = x
    c,d = y
    if a*d < b*c:
        return -1
    elif a*d == b*c:
        return 0
    else:
        return 1
import functools
l.sort(key = functools.cmp_to_key(cmp)) # ↑で定義した cmp 関数を functools.cmp_to_key 関数に与える
print(l) # [(1, 3), (2, 4), (3, 5)]

少々複雑ではありますが、想定通りのソートをすることができました。

補足:この比較関数の意味

実はこの比較は (a,b) を分数 a/b で評価してソートすることに相当します。これは b,d が正のとき a/b < c/d と a*d < b*c が同値になることから従います。
そのため今回の例では l.sort(key=lambda x: x[0]/x[1]) としても同じソート結果を得ることができると思います。
しかしながら、割り算の結果として出てくる浮動小数点は実数を厳密に表現できないため、場合によっては正しいソート結果を得られない場合があります。
上記のように比較関数を用いると掛け算のみ(整数のみ)でソート処理を行うことができ、正確なソート結果を得られるようになります。

問題

リンク先の問題を解いてください。

EX22.2つ目の値でソート

ABCの問題

さらに練習問題として以下の AtCoder Beginner Contest の問題を挙げておきます。
この問題は少々意地が悪いですが、本節の内容だけで解くことが可能です。

ABC308C - Standings

前のページ | 次のページ