sort( )について少し詳しく

python

デフォルトでは、文字列なら文字コード順、数値なら値の小さい順に並び替えます。リストやタプルの場合は、0番目の要素で並び替えを行います。

>>> list = [94, 25, 9, 67]
>>> list.sort()
>>> list
[9, 25, 67, 94]
>>>
>>> list = ["banana", "grape", "orange", "apple"]
>>> list.sort()
>>> list
['apple', 'banana', 'grape', 'orange']
o>>>
>>> list = [(3, 99), (4, 95), (1, 123), (2, 14)]
>>> list.sort()
>>> list
[(1, 123), (2, 14), (3, 99), (4, 95)]

cmpキーワード

>>> list = ["98", "101", "100", "99"]
>>> list.sort()
>>> list
['100', '101', '98', '99']

数値文字列はあくまで文字列ですので、"101"は"99"より先に来ます。


数値文字列を数値としての大小で並び替えるには、sort( )の第一引数もしくはcmpキーワードに比較関数を指定します。比較関数は二つの引数を比較した結果に応じて、負の数、0、正の数のいずれかを返す必要があります。sort( )は先頭から順に二つの要素を比較関数に渡し、その結果が正の数であれば、それらの要素の位置を入れ替えます。

>>> list = ["98", "101", "100", "99"]
>>> list.sort(cmp=lambda x,y: cmp(int(x), int(y)))
>>> list
['98', '99', '100', '101']

cmp( )はaとbの二つの引数を取り、a < bなら-1、a == bなら0、a > bなら1を返します。ちなみにデフォルトの動作はsort(cmp=cmp)と同じです。

keyキーワード

keyキーワードを使って同じことができます。keyにはリストの各要素から比較関数に渡すキーを取り出すための関数を指定します。

>>> list = ["98", "101", "100", "99"]
>>> list.sort(key=int)
>>> list
['98', '99', '100', '101']

cmpの場合は比較関数の中で各要素を数値へ変換しますが、keyの場合は比較関数に渡す前に数値へ変換します。

降順に並び替える

reverseにTrueを指定します。

 list = [94, 25, 9, 67]
>>> list.sort(reverse=True)
>>> list
[94, 67, 25, 9]
>>>
>>> list = ["banana", "grape", "orange", "apple"]
>>> list.sort(reverse=True)
>>> list
['orange', 'grape', 'banana', 'apple']

cmpとkeyの比較

同じように動作するなら、keyを指定した方が速いです。

# cmp_sort.py
for i in xrange(10000):
    list = ["99", "129", "92", "116", "43", "75", "219", "8", "68"]
    list.sort(cmp=lambda x,y: cmp(int(x), int(y)))
print list

# key_sort.py
for i in xrange(10000):
    list = ["99", "129", "92", "116", "43", "75", "219", "8", "68"]
    list.sort(key=int)
print list

$ time python cmp_sort.py
['8', '43', '68', '75', '92', '99', '116', '129', '219']

real    0m8.624s
user    0m0.000s
sys     0m0.000s
$
$ time python key_sort.py
['8', '43', '68', '75', '92', '99', '116', '129', '219']

real    0m2.278s
user    0m0.000s
sys     0m0.000s


これはint( )の呼び出し回数に差があるからです。key関数で各要素からキーを取り出すのは一度だけですが、比較関数の中で呼び出されるint( )は当然、各要素につき複数回呼び出されることになります。

count = 0
def _int(str):
    global count
    count += 1
    return int(str)

cmp_list = key_list = \
    ["99", "129", "92", "116", "43", "75", "219", "8", "68"]

cmp_list.sort(cmp=lambda x,y: cmp(_int(x), _int(y)))
cmp_count = count

count = 0
key_list.sort(key=_int)
key_count = count

print "cmp_list =", cmp_list
print "key_list =", key_list
print "cmp_count =", cmp_count
print "key_count =", key_count

cmp_list = ['8', '43', '68', '75', '92', '99', '116', '129', '219']
key_list = ['8', '43', '68', '75', '92', '99', '116', '129', '219']
cmp_count = 40
key_count = 9


降順に並び替える場合、reverse=Trueを指定するかどうかで、どれぐらいの差が出るのかも調べてみます。

# key_sort.py
for i in xrange(10000):
    list = ["99", "129", "92", "116", "43", "75", "219", "8", "68"]
    list.sort(key=lambda x: -int(x))

# key-reverse_sort.py
for i in xrange(10000):
    list = ["99", "129", "92", "116", "43", "75", "219", "8", "68"]
    list.sort(key=int, reverse=True)

$ time python key_sort.py

real    0m2.931s
user    0m0.000s
sys     0m0.000s
$
$ time python key-reverse_sort.py

real    0m2.228s
user    0m0.000s
sys     0m0.000s

cmpとkeyほどではないですが、reverse=Tureを指定した方が速いようです。