Re: [問題] 關於list排序

看板Python作者sbrhsieh (偶爾想擺爛一下)時間15年前 (2009/11/20 14:44)推噓2(2推 0噓 2→)

留言4則, 3人參與討論串5/5 (看更多)

※ 引述《KSJ (阿真)》之銘言： : 也參考過回文的文章跟參考文章 : 對於以下的解釋還是不解(雖然會使用了) : 想請板友們幫個忙： : : " : key 的使用方式比前面 cmp 的方式來的直覺，而且速度較快， : 因為排序的時候，只要需要比較的動作就會呼叫 cmp， : 而 key 只會被呼叫 n 次，n 是序列的長度，所以 key 的速度較快。 : " : : 我的想法是 : 比方有三個數 [小 ,大 ,中] : cmp感覺是先抓小大二個比把小放在第一位 : 再抓大中二個比 : 再抓小中二個比把中放在第二位 : 把大放在第三位 : 二個疑問： : 1. 對於key的比法(還是說應該稱作 "準則") 是類似cmp這樣嗎?怎麼比的呢？直接拿 key 與 cmp 參數來比較是不太適當的，因為兩者負責的工作(任務)不同，且二者不是互斥的。 cmp 參數的責任是指出任兩個 element(a, b) 的大小： -1 for a < b 0 for a == b 1 for a > b 如果 list element 本身就是 comparable(有 natural order)，而你想要 list 排序的順序就是依照 natural order，你可以不需要提供 cmp 參數。如果你想要依照 natural order 以外的規則來排序，或者是 list element 本身不是 comparable(比如 element 是一種複合的結構)，那麼就需要提供 cmp 參數。以 element 為複合的結構為例，自行提供的 cmp function 依照某種邏輯來決定大小關係。比如說 list element 為 tuple，這些 tuple 皆是升冪排列的整數數列，我希望將這些 tuple 依照其 maximum 來升冪排序。 A=[(2, 4, 6, 8), (1, 3, 5), (1, 2, 4)] A.sort(cmp=lambda a, b: cmp(a[-1], b[-1])) print A # [(1, 2, 4), (1, 3, 5), (2, 4, 6, 8)] 在不搭配 key 參數的情況下，cmp 參數帶進來的 function 在面對複合型態的物件時，通常要做兩件事： 1.從兩個 object 中擷取主導排序的數據 2.決定擷取出來的數據的大小在 list.sort 執行過程中(不論 list.sort 實際上是使用哪一種排序演算法)，當有需要比較某兩個 element 時，cmp 參數帶進來的 function 都會被執行一次。 key 參數負責的任務是從 element 擷取出主導 element 順序的關鍵數據，取出來的關鍵數據必須是 comparable。延續前面的例子： A=[(2, 4, 6, 8), (1, 3, 5), (1, 2, 4)] A.sort(key=lambda s: s[-1]) print A # [(1, 2, 4), (1, 3, 5), (2, 4, 6, 8)] 這種作法是先把一個 object sequence 經過一個 mapping 變成另一個 object sequence(兩個 object sequence 對應的 element 有關連)，然後以後者來做 sorting。 [2 4 6 8] [1 3 5] [1 2 4] <=== A | | | | | | <== map(lambda s:s[-1], A) | | | 8 5 4 <=== B ↓ sort B 4 5 8 <=== sorted B | | | [1 2 4] [1 3 5] [2 4 6 8] <=== sorted A 所以在這種排序複合元素的情況下，通常指定 key 參數會比較有效率，因為 cmp 參數指定的 function 每次在決定元素大小前都要做一次擷取關鍵數據的動作，而 key 參數指定的 function 是一開始拿來將每個元素的關鍵數據取出，之後進行排序時就不再使用到。如果 key 參數(function)擷取的數據的 natural order 不同你想要的順序，可再搭配 cmp 參數。 : 2. 又對於最原本的sort()方法是用最佳化的比法還是最簡單的比法呢?? 有沒有客製 cmp or key function，list.sort 使用的排序演算法都是一樣的。我猜 list.sort 應該是使用 quicksort 變化而來的演算法，可能在 list size 夠小時是使用其他的排序演算法，size 大時使用 quicksort。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.173.137.110 ※ 編輯: sbrhsieh 來自: 218.173.137.110 (11/20 15:05)