sort
前回のこれで
http://d.hatena.ne.jp/lolstep/20080621/1214043186
$a, $bが定義されてないのにエラーが出ないのは謎いと書いたところ、いつもみてるid:perlcodesampleさんからコメントで教えてもらったのでおさらい。
http://perldoc.jp/docs/perl/5.8.4/perlfunc.pod
use strict している場合、$a と $b をレキシカルとして宣言しては いけません。これはパッケージグローバルです。つまり、main パッケージで以下のように書いた場合:
@articles = sort {$b <=> $a} @files;
$a と $b は $main::a と $main::b (または $::a と $::b) を意味しますが、FooPack パッケージ内の場合、これは以下と同じになります:
@articles = sort {$FooPack::b <=> $FooPack::a} @files;
というわけで使うなと。
sortの書き方は以下の3つ。
- sort SUBNAME LIST
- sort BLOCK LIST
- sort LIST
sort LIST
SUBNAME や BLOCK を省略すると、標準の文字列比較の順番でソートが行なわれます。
#!/usr/bin/perl use strict; use warnings; # 配列定義 my @array = ( "1", 2, 3, 4, "5", 10, "11", "A" ); # sort my @result = sort @array; for (my $i = 0; $i < @result; $i++) { print $result[$i] . "\n"; }
C:\MyWorks\Perl\sort>perl sort1.pl 1 10 11 2 3 4 5 A
配列の個数取得がわからなくて2分はまったがこれみて把握。
http://d.hatena.ne.jp/perlcodesample/20080114/1200305034
こんな方法もあるようだが
http://www.ksknet.net/cat34/post_12.html
配列の個数を参照するには$#変数名を参照すればよい。
$#array;
なんかしっくりこないので$num = @arrayのほうを使うことにする。
sort SUBNAME LIST
SUBNAME を指定すると、それは、リストの要素をどのような順番に並べるかに応じて、負、ゼロ、正の整数を返すサブルーチンの名前であると解釈されます。
いまいち意味がわからないんだけども、どう解釈したらいいのかが不明すぎる。
サンプルみると
http://chaichan.web.infoseek.co.jp/src/perl07.htm
sub number {
if ($a < $b) {
return -1;
} elsif ($a == $b) {
return 0;
} elsif ($a > $b) {
return 1;
}
}
こう書いてあるが、確かに負、ゼロ、正の整数を返すサブルーチンであることは理解できるけども、これって要素を1個づつ隣に進むイメージになってるんだろうか。
サブルーチンのプロトタイプが ($$)の場合、比較する要素は通常のサブルーチンと同じように @_ の中にリファレンスとして渡されます。これはプロトタイプなしのサブルーチンより遅いです。この場合は比較のためサブルーチンに渡される 2 つの要素は、パッケージのグローバル変数 $a と $b で渡されます (次の例を参照してください)。後者の場合、レキシカルに $a と $b を宣言するのは普通逆効果になります。
プロトタイプが$$ってのをググると、要はスカラーが2個の引数ってことみたいなんだけども、どうなってんのかなあ。
てことで、意味がよくわからないのでprint文をはさんでみる。
#!/usr/bin/perl use strict; use warnings; # 配列定義 my @array = ( "1", 2, 3, 4, "5", 10, "11", "20" ); # sort my @result = sort number @array; sub number { if ($a < $b) { print "$a < $b\n"; return -1; } elsif ($a == $b) { print "$a = $b\n"; return 0; } elsif ($a > $b) { print "$a > $b\n"; return 1; } } print "\nresult\n"; for (my $i = 0; $i < @result; $i++) { print $result[$i] . "\n"; }
C:\MyWorks\Perl\sort>perl sort2.pl 1 < 2 3 < 4 5 < 10 11 < 20 1 < 3 3 > 2 5 < 11 11 > 10 1 < 5 5 > 2 5 > 3 5 > 4 result 1 2 3 4 5 10 11 20
なるほどね、これでよくわかった。ソートもマージソートを使ってる模様。
Perl 5.6 以前ではソートの実装にクイックソートアルゴリズムを使っていました。このアルゴリズムは安定せず、2 乗の時間が掛かる 可能性があります 。 (安定した ソートは、比較した時に同じ要素の入力順が保存されます。クイックソートの実行時間は、長さ N の全ての配列の平均では O(NlogN) ですが、入力によっては O(N**2) という 2 乗の 振る舞いをすることがあります。) 5.7 では、クイックソートによる実装は、最悪の場合の振る舞いも O(NlogN) である、安定したマージソートアルゴリズムに置き換えられました。しかし、入力とプラットフォームによっては、ベンチマークはクイックソートの方が速くなります。 5.8 ではソートを限定的に制御できる sort プラグマがあります。この、アルゴリズムの直接的な制御方法は将来の perl では引き継がれないかもしれませんが、実装に依存しない形で入力や出力を性格付ける機能はおそらくあります。 sort を参照してください。
マージソートといえば、今日はてブでこれみたがすごい良いタイミング。
http://labs.cybozu.co.jp/blog/akky/archives/2008/06/animated-sorting-algorithm-demo.html
というわけで、これでは長いので
となるわけだね。
てことで書き換える。
#!/usr/bin/perl use strict; use warnings; # 配列定義 my @array = ( "1", 2, 3, 4, "5", 10, "11", "20" ); # sort my @result = sort number @array; sub number { print "$a <=> $b\n"; $a <=> $b; } print "\nresult\n"; for (my $i = 0; $i < @result; $i++) { print $result[$i] . "\n"; }
C:\MyWorks\Perl\sort>perl sort3.pl 1 <=> 2 3 <=> 4 5 <=> 10 11 <=> 20 1 <=> 3 3 <=> 2 5 <=> 11 11 <=> 10 1 <=> 5 5 <=> 2 5 <=> 3 5 <=> 4 result 1 2 3 4 5 10 11 20
sort BLOCK LIST
SUBNAME の代わりに、無名のインラインソートルーチンとして、BLOCK を書くことができます。
というわけで、どこみてもsortで探すと書いてある一般的?な構文のこれに行き着くわけか。
http://d.hatena.ne.jp/perlcodesample/20080114/1200305034
#----- 昇順に並べ替える --------------
my @ascend = sort { $a <=> $b } @numbers;
print "昇順に並べ替え : @ascend\n";
書き換えてみる。
#!/usr/bin/perl use strict; use warnings; # 配列定義 my @array = ( "1", 2, 3, 4, "5", 10, "11", "20" ); # sort my @result = sort { $a <=> $b } @array; for (my $i = 0; $i < @result; $i++) { print $result[$i] . "\n"; }
C:\MyWorks\Perl\sort>perl sort4.pl 1 2 3 4 5 10 11 20
文字列比較をしたい場合は<=>じゃなくてcmpを使いなさいよってことで、とりあえずsortは大体把握した、と思う。
しかし、残業後にするとさすがに眠くなるな。