Python 2.3 以前でキーで並べ替えるには、パラメーターを使用できcmpます。ただし、keyスタイルの並べ替えの方が読みやすい場合もあります。いずれにせよ、関数は O(n) 回しか呼び出されないcmpのに対し、O(n log n) 回呼び出されるため、作業は少なくなります。key
それを念頭に置いて、key以降のバージョンの Python でパラメーターの動作を再現する方法を次に示します。これは、decorate-sort-undecorate イディオム、別名Schwartzian Transformを使用します。これはコピーを作成するため、スペース効率はそれほど高くありませんが、リストが大きい場合は、時間効率が向上する可能性があります。2.4 で追加されsortedた機能を大まかに再現しているため、この名前を付けました。sortedPython のバージョンを確認し、これを条件付きでインポートして、組み込みのsorted新しいバージョンを壊したり、名前を変更したりしないようにします。
def sorted(seq, key=lambda x: None, reverse=False):
seq = [(key(x), i, x) for i, x in enumerate(seq)]
seq.sort()
if reverse:
seq.reverse()
return [x for k, i, x in seq]
enumerate等しいキーを持つ等しくない値に対して安定した並べ替えを行うことに関心がある場合にのみ必要であることに注意してください。髪一本分の機能を低下させます。あなたのデータでテストされました：
>>> key=lambda x: (x.count('YES'), x.count('MAYBE'), x.count('NO'))
>>> my_sorted(mylist, key=key, reverse=True)
[['ITEM C', 'YES', 'YES', 'YES', 'YES', 'NO', 'NO', 'MAYBE', 'NO', 'MAYBE'],
['ITEM B', 'YES', 'NO', 'YES', 'YES', 'NO', 'NO', 'NO', 'NO', 'MAYBE'],
['ITEM A', 'YES', 'NO', 'YES', 'YES', 'NO', 'NO', 'NO', 'NO', 'NO']]
また、辞書を使用して数えることを検討することもできます。そうすれば、必要なパスは 1 つだけです。ただし、少なくとも私のマシンではcount、3 つのパスが 1 つの Python ループよりも高速であるように十分に最適化されています。forしたがって、多くの値をカウントする必要がある場合にのみ使用してください。後世のためにこれをここに残しておきます：
def my_key(inner_list):
counts = {'YES':0, 'MAYBE':0, 'NO':0}
for i in inner_list:
if i in counts:
counts[i] += 1
return (counts['YES'], counts['MAYBE'], counts['NO'])
私はいくつかのテストを行いました。長い投稿をお詫びします。以下は、好奇心旺盛で好奇心旺盛な方のみを対象としています。
私のテストでは、小さいリストでは、decorate、sort、undecorate が組み込みの sort + を使用するよりも高速cmpであることが示されています。より大きなリストでは、違いはより劇的になります。定義:
def key_count(x):
return (x.count('YES'), x.count('MAYBE'), x.count('NO'))
def key_dict(inner_list):
counts = {'YES':0, 'MAYBE':0, 'NO':0}
for i in inner_list:
if i in counts:
counts[i] += 1
return (counts['YES'], counts['MAYBE'], counts['NO'])
def decorate_sort(seq, key=lambda x: None, reverse=False):
seq = [(key(x), i, x) for i, x in enumerate(seq)]
seq.sort()
if reverse:
seq.reverse()
return [x for k, i, x in seq]
def builtin_sort(seq, key, reverse=False):
seq.sort(lambda p, q: cmp(key(p), key(q)))
if reverse:
seq.reverse()
テスト:
>>> mylist = [
... ['ITEM A', 'YES', 'NO', 'YES', 'YES', 'NO', 'NO', 'NO', 'NO', 'NO'],
... ['ITEM B', 'YES', 'NO', 'YES', 'YES', 'NO', 'NO', 'NO', 'NO', 'MAYBE'],
... ['ITEM C', 'YES', 'YES', 'YES', 'YES', 'NO', 'NO', 'MAYBE', 'NO', 'MAYBE']
... ]
>>> %timeit decorate_sort(mylist, key=key_count, reverse=True)
100000 loops, best of 3: 5.03 us per loop
>>> %timeit builtin_sort(mylist, key=key_count, reverse=True)
100000 loops, best of 3: 5.28 us per loop
組み込みバージョンはすでに遅いです！toが追加されているため、一般化されていないバージョンmylist.sort(lambda p, q: -cmp(key(p), key(q)))の方が、短いリストよりも優れています。それがなければ、より高速です (以前のテストではループあたり 4.28 us):enumeratedecorate_sortdecorate_sort
>>> %timeit mylist.sort(lambda p, q: -cmp(key_count(p), key_count(q)))
100000 loops, best of 3: 4.74 us per loop
ただし、この場合の使用key_dictは間違いです。
>>> %timeit decorate_sort(mylist, key=key_dict, reverse=True)
100000 loops, best of 3: 8.97 us per loop
>>> %timeit builtin_sort(mylist, key=key_dict, reverse=True)
100000 loops, best of 3: 11.4 us per loop
より大きなリストでテストすると、基本的に同じ結果が保持されます。
>>> import random
>>> mylist = [[random.choice(('YES', 'MAYBE', 'NO')) for _ in range(1000)]
for _ in range(100)]
>>> %timeit decorate_sort(mylist, key=key_count, reverse=True)
100 loops, best of 3: 6.93 ms per loop
>>> %timeit builtin_sort(mylist, key=key_count, reverse=True)
10 loops, best of 3: 34.5 ms per loop
一般化されていないバージョンは、 よりも遅くなりdecorate_sortました。
>>> %timeit mylist.sort(lambda p, q: -cmp(key_count(p), key_count(q)))
100 loops, best of 3: 13.5 ms per loop
そしてkey_dict、まだ遅いです。（しかし、より速いbuiltin_sort！）
>>> %timeit decorate_sort(mylist, key=key_dict, reverse=True)
10 loops, best of 3: 20.4 ms per loop
>>> %timeit builtin_sort(mylist, key=key_dict, reverse=True)
10 loops, best of 3: 103 ms per loop
つまり、シュワルツ変換は、より高速でより一般化されたソリューションを提供するということです。これは、まれで素晴らしい組み合わせです。