sortのあれこれ
ABC308-CでPythonのsortで痛い目を見たので、これを機にまとめてみる。 キホン
引数なしl.sort()
lの各要素を昇順で並べる。
細かい部分について、
比較には__lt__()を使う。自作classでソートする場合、最低限__lt__()を実装すればいい。この解説 なお、他の比較演算子も全部実装するよう推奨されている。
安定ソート。=になる2つの値の出現順は、ソート前後で変わらない。
sortには2つ引数を設定できる。l.sort(key=func, reverse=True)
引数1key=func
「この値で比較しますよー」って感じ。
具体的には、リストの要素xについて、func(x)の返り値を元に比較していく。
よくあるのが、要素がタプルなリストで2つ目の要素を基準に並べ替えるやつ
→l.sort(key=lambda x: x[1])
別の配列を参照しながらソートなんてこともできる
code:idxsort.py
# 0 1 2 3 4 5 6 7 8 9
L = sorted(range(10), key=lambda x: Ax) print(L)
引数2reverse=True
Trueなら降順、Falseor省略で昇順に並び替える
困ること
複雑な比較が投げられない
key=funcで投げる関数は要素1つしか引数に渡せない→2者間の計算結果を元に比較ができなくて困る。
code:cmp.py
from functools import cmp_to_key
def cmp(a, b):
if a < b:
return -1
elif a > b:
return 1
else:
return 0
l.sort(key=cmp_to_key(cmp))
このcmpをいい感じに書き換えよう
リストの詰まったリストの並べ替えが遅い
整数だけの列と比べてリストの列はソートが非常に遅く、それだけでTLEの危険が高まる。
うまく整数に変換してからソートすると速い
code:sortinit.py
from random import randrange
import time
X = 10**9 # 最大値
そのまま
code:sort.py
A.sort()
PyPy:1.4秒、Python:0.8秒
タプル
code:sorttuple.py
B.sort()
PyPy:1.1秒、Python:0.4秒
整数
code:sortint.py
C.sort()
ソート部:PyPy:0.075秒、Python:0.19秒
変換込み:PyPy:0.12秒、Python:0.46秒
整数(X = 10**18、つまり多倍長整数の比較になる場合)
ソート部:PyPy:0.8秒、Python:0.19秒
変換込み:PyPy:1.3秒、Python:0.5秒
整数に変換できるなら変換しておいた方が無難。ソートするときの配列のサイズも考えつつ柔軟に