れっつ、そーと。

「Effective Perl」面白いですねっ！
「Perlクックブック」だと分厚すぎて、時間のある時に
読もうと思い持ち運びなんて使いしづらいですもんね。
その点、Effective Perlなら手ごろな厚さで内容
も濃厚で読んでいて楽しいことこの上なしです！


で、今日は14項の「数限りなきソート術を学ぼう」を読んだのですが…
変なのキター！
というわけで、これですこれkr。

@sorted_names =
　map { $_ -> [0] }
　sort { $a -> [1] <=> $b -> [1] }
　map { [$_, -M] } @files;

@filesに格納されているファイル名をファイル変更日付でソートかけてるわけです。
これだけだと何のことだかわけわかめなんで、順を追ってメモメモ。


まずは、sort関数と言うと…下記の通りですよね。
ソートされた関数 ＝ sort (ソート順の定義)?　ソート対象のリスト;

use strict;
use warnings;

my @before = qw(e c a d b);
my @after = sort @before;
print "@after\n";          #a b c d e

じゃ、数字をsortしようとすると…

use strict;
use warnings;

my @before = 1..10;
my @after = sort @before;
print "@after\n";          #1 10 2 3 4 5 6 7 8 9

もし、ASCII順に並べ替えたいのならばこれでよいですが
たいていの場合この結果を期待する人は少ないはずですよね　汗
そうなると次に登場するのがソートの定義です。
さきほどの、数字の並び替えを期待したとおりに行うには下記のように
スペースシップ演算子を使って数値的にソートを行う必要がありますね。

use strict;
use warnings;

my @before = 1..10;
my @after = sort { $a <=> $b } @before;
print "@after\n";          #1 2 3 4 5 6 7 8 9 10

今度は、期待した通りになりましたね！
では、最初のファイルを更新日順にソートする話に戻ります。
簡単に書くのであれば

use strict;
use warnings;

my @files = qw(file1.txt file2.txt file3.txt);
my @sorted = sort { -M $a <=> -M $b } @files;
print "@sorted\n";

一般的に、比較をベースとするソートアルゴリズムは、
１回のソートでn log n回(nはソートする要素数)と言われているそうです。
つまり、単純な数値比較だとn log n回の数値比較を行うのに対し
ファイルの更新日順に並べるソートの場合、n log n回分の
ファイル更新時間の取得とその比較を行っている為無駄の
多いソートになっているわけです。

例えば、初めて比較する時だけファイル更新時間の取得を行い
それをキャッシュしておき、2回目以降の比較の際はキャッシュを
参照した方が高速になります。
要は、n log n回分の比較と n回分のファイル更新時間の取得で済むので。
それをあらわしたコードが下記のようになります。

use strict;
use warnings;

my @files = qw(file1.txt file2.txt file3.txt);
my %m;
my @sorted = sort {
($m{$a} ||= -M $a) <=>
($m{$b} ||= -M $b)
} @files;
print "@sorted\n";

ちなみに、　$m{$a} ||= -M $a　は、
$a = $a + 10;　の省略形が $a += 10;　となるのと同様に
$m{$a} = $m{$a} || -M $a;　が $m{$a} ||= -M $a;
と、なっているだけです。


で、上の内容をPerlハカーな方々は、シュウォーツ変換を
活用して書くそうでそれが、一番最初に出てきたコードだったわけです。
本によると、シュウォーツ変換とは、mapで囲まれたsortである（？）となってます。

キューピー３分●ッキング♪
本日の●ッキングは、３つのファイルを更新順にソート致します。
まずは、材料を用意します。
今回は、my @names = qw(file1.txt file2.txt file3.txt);を使います。
まずは、ソートの条件を確認します。
比較対象→ファイル更新日
アウトプット→ファイル名
と、言うことでまずは、下準備から。
では、mapで名無しリストを作成します。

@names_and_ages = map { [$_, -M] } @names;

この時、@names_and_agesの各要素には、[$_, -M]という
ファイル名と更新日時の無名リストのリファレンスが格納されます。
@names_and_ages = [["file1.txt", file1.txtの更新日],
　　　　　　　　　　　　　　　 ["file2.txt", file2.txtの更新日],
　　　　　　　　　　　　　　　 ["file3.txt", file3.txtの更新日]
　　　　　　　　　　　　　　　];
こんな感じですね。
次が、この○ッキングのメインのソートです。

@sorted_names_and_ages = sort {
　$a->[1] <=> $b->[1]
} @names_and_ages;

$a <=> $bだと、リファレンスの比較になっちゃいますね　汗
比較したのは、更新日なので、リファレンスの第２要素を指定する為
$a->[1] <=> $b->[1]となってます。

調理が完成したら、@sorted_namesという皿に盛り付けるだけです！
@sorted_names = map { $_->[0] } @sorted_names_and_ages;

@sorted_names_and_agesには、更新日を元にリファレンスが並び替えられてます。
最終的に欲しいデータは、ファイル名なので…
ファイル名は、リファレンスの第１要素に格納されているので
mapで$_->[0]を抜き出してリストを作って完成っと。
同じ変数を代入していくと…

use strict;
use warnings;

my @files = qw(file1.txt file2.txt file3.txt);
my @sorted_names =
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [$_, -M] }
@files;
print "@sorted_names\n";

完成です＼(^o^)／
とっても、おいしい料理ができあがりましたね！！


では、もう一度本日のおさらいです。
１．並び変えるデータと並び変え判定に使うデータのリファレンスを作成。(map)
２．並び変え判定に使うデータで並び替え。（sort）
３．並び変えるデータと並び替え判定に使うデータから並び替えるデータを取り出す。（map）
以上！

で、sort関係に関連してネットをさまよっていたら楽しい
ページをいくつか見つけたのでメモ書きしておきますね。
あなたが一番好きなアルゴリズムを教えてください。
また、その理由やどんな点が好きなのかも教えてください。
はてなの質問です。
個人的にはエラトステネスの篩が好きです　笑


プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
弾さんの記事です。
こういう記事を見ない限りなかなかアルゴリズムの知識も
増えないので非常に為になりました。。

最後は、
いろいろなソートアルゴリズム
バブルソート/バケットソート/基数ソート/ヒープソート/マージソート/クイックソート
をJavaアプレットを駆使してわかりやすく解説してあります。
昔、おもれーって思って何度も眺めていた記憶が　笑