memo: sort

ソートに関する簡単なメモ (Perl)
うまくいかなかったソート (旧) 
 1: my $by_rule = "by_$sort_key$sort_order";
 2: @files = sort $by_rule @files;
 3: # 昇順 - N:ファイル名  M:更新日時  S:サイズ  T:種類
 4: sub by_NA { uc($a) cmp uc($b); }
 5: sub by_MA { (-M "$img_dir/$b") <=> (-M "$img_dir/$a"); }
 6: sub by_SA { (-s "$img_dir/$a") <=> (-s "$img_dir/$b"); }
 7: sub by_TA { tof($a) cmp tof($b); }
 8: # 降順
 9: sub by_ND { uc($b) cmp uc($a); }
10: sub by_MD { (-M "$img_dir/$a") <=> (-M "$img_dir/$b"); }
11: sub by_SD { (-s "$img_dir/$b") <=> (-s "$img_dir/$a"); }
12: sub by_TD { tof($b) cmp tof($a); }
13: # FoldersFirst -always
14: @files = sort {(-d "$img_dir/$b") cmp (-d "$img_dir/$a")} @files;

ここにおいて期待されているのは、指定されたキーと向きでファイルリストをソート(Line 2)した後に、その結果は生かしたままリスト内のディレクトリだけを上位にまとめる(L.14)ということ。sort 関数がその比較基準による順番の入替え以外には手をつけないとすると そうなるのが自然なように思える。

が、このやり方では FoldersFirst のためのソートを行ったとき(L.14)に、先行する by_XX のソート(L.2)で整えられた順番は微妙に(部分的に)崩れてしまう。

またこの両方のソートに先立って(ファイルリスト @files を取得する際に) {lc($a) cmp lc($b)} で初期ソートが行われているのだが、その順番もこの2度のソートの後では期待どおり保たれていない(たとえばファイルの種類でソートした場合、同じ種類のファイルは名前昇順でならんでいてほしいと思うのだけれど、ほぼそのようにならんでいるように見えて、一部が崩れてしまっている)。

というわけで「後続するソートはその比較基準のみによって順番の入替えを行い、先行するソートが整えた順番は――そこにセカンダリキーの姿が正確に見えるように――生かされる」だろうという考えは間違っていたことがわかる。つまり名前順でならんでいたあるメンバーのリストをいま年齢でソートしたとき、同じ年齢のメンバーは名前順にならんでいるはずだということは期待できないわけ。

このソートを当初の期待どおりに行うための単純な方法は、ファイルリスト取得時にディレクトリを @files に含めず、別の配列 @dirs に分けておいて、それぞれを by_XX でソートした後 @dirs を上位(前方)にして配列をまとめるというもの。でもできればソートは一つの配列だけですませたい。気分的にも。

うまくいったソート (新) 
 1: my $by_rule = "by_$sort_key$sort_order";
 2: @files = sort $by_rule @files;
 3: # FoldersFirst
 4: sub folder { (-d "$img_dir/$b") cmp (-d "$img_dir/$a"); }
 5: # 昇順 - N:ファイル名  M:更新日時  S:サイズ  T:種類
 6: sub NameA { uc($a) cmp uc($b); } # secondary key: N,A (always)
 7: sub by_NA { folder or NameA; }
 8: sub by_MA { folder or (-M "$img_dir/$b") <=> (-M "$img_dir/$a") or NameA; }
 9: sub by_SA { folder or (-s "$img_dir/$a") <=> (-s "$img_dir/$b") or NameA; }
10: sub by_TA { folder or tof($a) cmp tof($b) or NameA; }
11: # 降順
12: sub by_ND { folder or uc($b) cmp uc($a); }
13: sub by_MD { folder or (-M "$img_dir/$a") <=> (-M "$img_dir/$b") or NameA; } # not NameD
14: sub by_SD { folder or (-s "$img_dir/$b") <=> (-s "$img_dir/$a") or NameA; }
15: sub by_TD { folder or tof($b) cmp tof($a) or NameA; }

念のため、何行もあるけど実質的な処理は @files = sort $by_rule @files; (L.2)だけ。旧い方法では2度(正確には3度)に分けてやっていたものを1度にまとめ、それによって暗に期待していながら齎されなかった結果を陽に獲得した次第。

たとえばサイズの昇順でソートする by_SA (L.9)では、まずディレクトリであること、次にサイズが小さいこと、最後に名前のアルファベットが若いこと、という基準でソートが行われている。

考えてみれば初めからそうすればよかったという、きわめて当たり前な方法かもしれない。考えの整理がついたところでお終い。間違ってないことを願いつつ。

なお sub folder {(-d ...) cmp (-d ...)} (L.4)において <=> ではなく cmp としているのは、 -d の返す値が 1, '' or undef であるため。

$img_dir をグローバルにしているのはソート用のサブルーチン内から容易にアクセスできるようにするため。