sortのあれこれ

ABC308-CでPythonのsortで痛い目を見たので、これを機にまとめてみる。

公式ドキュメント：ソート HOW TO

キホン

引数なし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

A = 10, 13, 16, 19, 12, 15, 18, 11, 14, 17

# 0 1 2 3 4 5 6 7 8 9

L = sorted(range(10), key=lambda x: Ax)

print(L)

# → 0, 7, 4, 1, 8, 5, 2, 9, 6, 3

引数2reverse=True

Trueなら降順、Falseor省略で昇順に並び替える

困ること

複雑な比較が投げられない

key=funcで投げる関数は要素1つしか引数に渡せない→2者間の計算結果を元に比較ができなくて困る。

そんなときはfunctools.cmp_to_key この解説一番上

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 # 最大値

A = [randrange(X), randrange(X) for _ in range(500000)]

そのまま

code:sort.py

A.sort()

PyPy:1.4秒、Python:0.8秒

タプル

code:sorttuple.py

B = tuple(a) for a in A

B.sort()

PyPy:1.1秒、Python:0.4秒

整数

code:sortint.py

C = a*X+b for a, b in A

C.sort()

A = divmod(c, X) for c in C

ソート部：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秒

整数に変換できるなら変換しておいた方が無難。ソートするときの配列のサイズも考えつつ柔軟に