Re: 排序問題

[reizarc (零式札克)]

※ 引述《wawawa (哇哇哇○(￣﹏￣)○)》之銘言：
: ※ 引述《ncukcm (test)》之銘言：
: :  我有一筆資料每一行的格式為
: :    S(字串) X Y Z A B C (以上皆為數字)
: :  需要將這些資料重新排序然後再印出資料
: :  先依 Z 大小再依 X 大小再依 Y 大小
: :  想請教該如何寫比較好呢 ?
: 好久沒寫perl了...練習一下:p 應該沒寫錯（吧？）
: 在這裡假設你的資料檔名是test.txt...
: #!/usr/bin/perl
: sub by_order {
:   (split /\s+/, $a)[3] <=> (split /\s+/, $b)[3] or
:   (split /\s+/, $a)[1] <=> (split /\s+/, $b)[1] or
:   (split /\s+/, $a)[2] <=> (split /\s+/, $b)[2];
: }
: open TXT, "< test.txt";
: @content = <TXT>;
: close TXT;
: foreach ( sort by_order @content ) {
:   print;
: }

這個方法確實可行

但是最大的缺點在於 多次的 split 造成效率上的問題

( Perl 使用 qsort 演算法,
  NlogN 的複雜度下每次都要執行 sort function 做比較  )

正巧在書裡看到 "Perl設技師對於複雜排序問題的標準解法"

又稱 Schwartz 轉換, 解法很巧妙,

對於這個問題的寫法 我把它列在下面 :p

my @a = ( "abc 1 6 3 1 5 6",            # data input
          "def 2 5 5 1 8 3",
          "ghi 4 7 2 0 8 9",
          "jkl 4 5 5 1 8 2",
          "mno 2 7 5 1 8 9",
          "pqr 1 6 5 1 8 3" );

@a = map{ $_->[ 0 ] }                   # 轉回
     sort{ $a->[ 4 ] <=> $b->[ 4 ] or   # 排序
           $a->[ 2 ] <=> $b->[ 2 ] or
           $a->[ 3 ] <=> $b->[ 3 ] }
     map{ [ $_, split ] } @a;           # 轉換

像這樣, @a 的內容就排序完成了

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.216.170.17
推 abliou:蠻有趣的!!
推 KennyL:可以請教一下是哪本書嗎? 謝謝:)
推 Andor:Internet XD
→ Andor:請辜狗"GRT Sort" GRT是比ST更好用的轉換 ^^
推 reizarc:Effective Perl programming, 有中文版 :p
→ reizarc:話說 GRT 真是太讚啦 更容易懂 而且更有效率 :p
→ reizarc:感謝告知 ~
推 KennyL:感謝分享!