並べ替え：キーとcmp

Python 2でソートする場合、このソートを「構成」する方法は少なくとも2つあります。これらはkey



とcmp



パラメーターです。 1つ目はPython 2.4でのみ追加され、2つ目はPython 3.0で削除されました。 これらの事実は、 key



本当に優れていることを示唆しているようです。 誰がこれに同意しないかわからない-私は猫を求めます。



最初に、すべてが乱雑に見えないように、ドキュメントを少し調べます。



Pythonは通常、組み込みの `sorted`または` list.sort`をソートに使用します。 実際に電話する

 sorted(iterable, **kwargs)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コードと同等

 lst = list(iterable); lst.sort(**kwargs); lst
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そのため、 `list.sort`に焦点を当てます。



`list.sort`は3つのオプションパラメータを取ります。`key`はリスト項目を取り、元のリスト項目の代わりにソート中に比較するときに使用されるオブジェクトを返す関数（実際には呼び出し可能なオブジェクト）です。 `cmp`はリストの2つの要素を取り、渡されたパラメーター間の関係に応じて-1、0、または1を返す関数です。 `reversed`-if` True`の場合、リストは逆順にソートされます。



それで、例えば、オブジェクトのリストを `id`フィールドでソートする必要がある場合、何を使うべきでしょうか？ `cmp`と` key`アプローチを見てみましょう：

 lst.sort(cmp=lambda x, y: cmp(x['id'], y['id'])) #    
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 lst.sort(key=lambda x: x['id']) # , , 
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それは速度を犠牲にして根拠のないことではありません、いくつかのテスト：

 >>> lst = [{'id': x, 'name': 'test'} for x in xrange(1000)] >>> random.shuffle(lst) >>> def with_cmp(lst): ... lst.sort(cmp=lambda x, y: cmp(x['id'], y['id'])) ... >>> def with_key(lst): ... lst.sort(key=lambda x: x['id']) ... >>> timeit.timeit('with_cmp(lst[:])', setup='from __main__ import with_cmp, lst', number=1000) 2.7731389999389648 >>> timeit.timeit('with_key(lst[:])', setup='from __main__ import with_key, lst', number=1000) 0.55310797691345215
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

なぜそんなに大きな違いがあるのですか？ 実際には、 `key`パラメータが存在する場合、その値はソートの最初（ sorts ）に一度だけリストのすべての要素に適用されますが、` cmp`値は各比較に使用されます！ Pythonで使用されるチームソート（ アルゴリズム解析 ）の平均評価はnlog（n）であると考えると、この例では、 `cmp`のラムダが数回呼び出されたと想定できます。



実際、遅いPython関数ではなく、Cで書かれたネイティブな関数を使用して、さらに高速に実行できます（実行する必要があります）。 operator.itemgetterを使用した場合の結果は次のとおりです （まだdocs.python.org/library/operator.html#operator.attrgetter、methodcalled、およびはるかにおいしい）：

 >>> from operator import itemgetter >>> def with_op(lst): ... lst.sort(key=itemgetter('id')) ... >>> timeit.timeit('with_op(lst[:])', setup='from __main__ import with_op, lst, itemgetter', number=1000) 0.4054520057716877
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

合計、最初のオプションと比較して20 7倍の速度向上-悪くないでしょう？



明快さについて、スピードで理解しました。 `key` \` cmp`を使うことは好みの問題ではないと思います。後者は流れる抽象化の素晴らしい例だからです。 組み込みの `cmp`が` cmp`パラメータのvalue関数で使用されている限り、すべては問題ありません。これにより、ソートメカニズムの詳細が隠されますが、次のコードの出力を予測するように求められたらどうしますか：

 >>> def numeric_compare(x, y): return x - y >>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

あなたは確かに、 `cmp`が-1、0、または1を返すべきであることを覚えていますが、正確には何ですか？ 「x」が「y」よりも大きい場合、1または-1にすべきですか？ 2を返した場合、エラーが発生しますか、2は1として解釈されますか？ もちろん、30分で質問の質問への回答を見つけることができますが、なぜ見るのですか？ より良い抽象化、つまり `key`パラメータを使用する方が良いと思います。



警告の質問、「キー」では不十分なタスクのまれな例があることに同意します。 ただし、これらはまさに例外であり、レシピもあります（たとえば、これはSorting Mini-HOW TO：cmp_to_key ）。



ご清聴ありがとうございました。

---

PS挑戦。 次のコードが非常に奇妙に動作する理由：

 >>> ls = [(1,2,3), (2,1,3), (2,3,1)] >>> ls.sort(key=reversed) >>> ls [(1, 2, 3), (2, 3, 1), (2, 1, 3)] >>> ls.sort(key=reversed) >>> ls [(2, 1, 3), (1, 2, 3), (2, 3, 1)]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

答えは：

`reversed`は、リッチ比較メソッドが定義されていないタイプ` <type 'reversed'> `のオブジェクトを返します。 したがって、 `list.sort`は比較のために` id`オブジェクトを使用しますが、これらは常に変化しています。 「reversed」の代わりに「operator.itemgetter（slice（None、None、-1））」を使用します。