作者reizarc (零式札克)
看板perl
标题Re: 排序问题
时间Sun Oct 22 18:49:43 2006
※ 引述《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
1F：推 abliou:蛮有趣的!! 10/22 18:55
2F：推 KennyL:可以请教一下是哪本书吗? 谢谢:) 10/23 09:56
3F：推 Andor:Internet XD 10/23 11:23
4F：→ Andor:请辜狗"GRT Sort" GRT是比ST更好用的转换 ^^ 10/23 11:24
5F：推 reizarc:Effective Perl programming, 有中文版 :p 10/24 00:00
6F：→ reizarc:话说 GRT 真是太赞啦 更容易懂 而且更有效率 :p 10/24 00:00
7F：→ reizarc:感谢告知 ~ 10/24 00:11
8F：推 KennyL:感谢分享! 10/24 07:28