Hatena::ブログ(Diary)

Pashango’s Blog このページをアンテナに追加 RSSフィード

2009-06-14

多重キーでのソート

多次元リストのソートってよく使う機能だと思うんですが、pythonのソートってよく考えて作ってあるなぁと関心しました。

例えば、次のような「生徒の成績リスト」があったとします。

# 配列の並び順 [名前],[国語],[算数]
a = [
   ['Tim',     55, 46 ],
   ['Jack',    55, 70 ],
   ['Mathhew', 23, 80 ],
]

そこで、リスト2番目の値である「国語」を、点数が高い順にソートするしたい場合は、以下の用になります。

>>> sorted(a, key=lambda x:x[1], reverse=True)
[['Tim', 55, 46], ['Jack', 55, 70], ['Mathhew', 23, 80]]

ちなみにcmpパラメータではなくkeyパラメータを上書きしたのは高速化のためです、念のため・・・

結果を見ると「Tim」と「Jack」は、国語は55点で同点ですが、算数は「Jack」の方が上です。でも、国語が同点だった場合は、算数の高い方が上にソートしたい場合がありますよね。

つまり、第1キー(国語)と第2キー(算数)による多重キーのソートです。

結論から言いますと、多重キーのソートは以下のとおりです。

>>> sorted(a, key=lambda x:(x[1],x[2]), reverse=True)
[['Jack', 55, 70], ['Tim', 55, 46], ['Mathhew', 23, 80]]

変わった箇所はkeyパラメータに、キーの優先順位順に要素を並べただけです、もの凄い簡単です。

なんでこうなるかと言いますと、標準の比較関数であるcmp()に秘密があります。

cmp(x,y)とは、x>yだと正の数、x=yだと0、x<yだと負の数を返すビルトイン関数です。

>>> cmp(0,1)
-1
>>> cmp(1,1)
0
>>> cmp(1,0)
1

このcmp()って、実は引数としてリストも受け付けてくれるんです。

リストの若い要素順に値を比較していき、決着が着くまで比較してくれます。

つまり、こういう事ですね。

cmp([第1キー,第2キー,...],[第1キー,第2キー,...])

ですからkeyパラメータを、キーの優先順位に要素が並んだリスト(タプル)を返す関数を与えれば、多重キーのソートができるのです。

でもデフォルトのkeyパラメータは、多重リストを与えられた場合はリストを返すようになっています。

つまり、キーの優先順位で並べられたリストを与えれば、特別な設定をしなくても、多重キーでのソートになっているのです。

>>> #[第1キー],[第2キー]で並んでいるリスト
... a = [
...     [1,4],
...     [1,3],
...     [1,2],
...     [2,2],
...     [2,1],
... ]
>>> 
>>> #特に設定をせずにソートすれば多重キーのソートとなる
... sorted(a)
[[1, 2], [1, 3], [1, 4], [2, 1], [2, 2]]

ほぉぉ〜、pythonってよくできていますね。

他の言語はどうなっているんでしょうねぇ?

少なくとも、PHPのarray_multisort()は面倒臭いという事だけは知っています(笑)

追記

第1キーは昇順、第2キーは降順にしたい場合があると思います。

そんな時は以下のように、キーに-をつければ降順になります(数値限定です)

>>> #[順位],[点数]
... a = [
...     [1,80],
...     [1,90],
...     [1,20],
...     [2,100],
... ]
>>> 
>>> #第2キーの点数を降順にしたい場合、-をつける
... sorted(a, key=lambda x:(x[0],-x[1]))
[[1, 90], [1, 80], [1, 20], [2, 100]]

MakotoMakoto 2016/05/08 03:14 第一キーで昇順,第二キーで降順の場合の書き方非常に参考になりました!

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/pashango_p/20090614/1244984058