拙著『すぐわかるオブジェクト指向Perl』の中で、「歌で覚えるシュウォーツ変換」というコラムを書いている。
先日、ツイッターで、歌だけを紹介したら、そこそこバズった。



そこで、この歌で何をどう覚え込もうとしているのか、改めて紹介しよう。
以下のプログラムは、文字列を短い順にソートしている。
#! /usr/local/bin/perl
#
# sort.pl --- ソートのテスト

use 5.010;
use strict;
use warnings;
use utf8;
binmode STDOUT, ":utf8";

print sort {length($a) <=> length($b)} <DATA>;

__DATA__
教王護国寺
金剛峯寺
清荒神清澄寺
東寺
法隆寺
簡単に解説すると、<DATA>というのは__DATA__以降のデータ(お寺の名前が5行書いている)をリストで返す。
これをsort関数で並べ替えている。
{}で渡しているのは、ソートの順番を決めるコードブロックだ。
この中では、$a、$bというPerl組み込みの特殊変数を使い、$aが$bよりも小さい時は1、等しい時は0、大きい時は-1を返すコードを書く。
<=>というのは宇宙船演算子といい、スター・ウォーズの「ダース・ヴェイダー専用コアファイター」に似ているからそういう名前がついているそうだが、左の項と右の項を数値として比較し、左が右より小さい時は1、等しい時は0、大きい時は-1を返す。
length関数は引数の長さを返す関数である。
これで、__DATA__以降のレコードが短い順に表示される。

これ、5レコードしか並べ替えていないから一瞬で終わるけど、何万、何十万というお寺の名前をソートすると、そーとー時間が掛かる。
(スミマセン。)

ソートの早さを比較するというのはコンピューター好きを燃えさせる課題であって、いろいろな方法が提唱されている。
改善する方法の1つががシュウォーツ変換である。

上のプログラムの実行時間は、文字列の長さを定めるlength関数が、何回呼び出されているかによって変わる。
ちょっと調べてみよう。
#! /usr/local/bin/perl
#
# sort.pl --- ソートのテスト

use 5.010;
use strict;
use warnings;
use utf8;
binmode STDOUT, ":utf8";

our $i;
print sort {sub_length($a) <=> sub_length($b)} <DATA>;

sub sub_length {
   my $parm = shift;
   print ++$i, ": length called with $parm";
   return length $parm;
}

__DATA__
教王護国寺
金剛峯寺
清荒神清澄寺
東寺
法隆寺
組み込み関数lengthをサブルーチンsub_lengthで包んで、呼ばれた回数と引数を表示してみた。
実行。

[perl]$ ./sort.pl
1: length called with 教王護国寺
2: length called with 金剛峯寺
3: length called with 清荒神清澄寺
4: length called with 東寺
5: length called with 金剛峯寺
6: length called with 東寺
7: length called with 金剛峯寺
8: length called with 清荒神清澄寺
9: length called with 教王護国寺
10: length called with 清荒神清澄寺
11: length called with 東寺
12: length called with 法隆寺
13: length called with 法隆寺
14: length called with 金剛峯寺
東寺
法隆寺
金剛峯寺
教王護国寺
清荒神清澄寺
14回呼んでいる。
総当りだから仕方ないが、並びによってはこの数はさらに増える。

この回数を減らす方法に取り組む(sort関数自体を改善する)というのもいいが、ある文字列の長さを測るという、そこそこ手間の掛かりそうな関数lengthを呼ぶのを、最初に全部済ませればいいのではないだろうか。
つまり、__DATA__の全レコードについて、最初にlength関数を掛けてしまって、その戻り値をソートすればいいのではないだろうか。
#! /usr/local/bin/perl
#
# sort.pl --- ソートのテスト

use 5.010;
use strict;
use warnings;
use utf8;
binmode STDOUT, ":utf8";

our $i;
print sort {$a <=> $b} map { sub_length ($_) } <DATA>;

sub sub_length {
   my $parm = shift;
   print ++$i, ": length called with $parm";
   return length $parm;
}

__DATA__
教王護国寺
金剛峯寺
清荒神清澄寺
東寺
法隆寺

実行してみる。

[perl]$ ./sort.pl
1: length called with 教王護国寺
2: length called with 金剛峯寺
3: length called with 清荒神清澄寺
4: length called with 東寺
5: length called with 法隆寺
34567[perl]$
うん、あからさまにダメだ。

最後に「34567」とダダダッと表示しているのは、__DATA__の下のお寺の名前の文字数をソートして、改行なしに表示しているのだ。
ダメなりにプログラムを解説してみよう。

print sort {$a <=> $b} map { sub_length ($_) } <DATA>;

というのは、<DATA>というリストをmap関数に渡して、その出力をsort関数に渡して、その出力をprintしている。

map関数というのは、第2引数に渡されたリストに、第1引数で渡された操作を行って、その戻り値をリストとして返す。
第1引数はブレース({})で囲まれたコードブロックであって、第2引数のリストの各要素を$_に代入して渡す。
コードブロックの中で、リストの各要素は、Perlのデフォルト変数$_になる。
say map { sqrt($_) } (1, 2, 3, 4, 5);
というコードを実行すると
1
1.41421356
1.7320508
2
2.2340679
的な出力結果になると思われる。
なお、上のコードは、マジックインクリメント演算子「..」を使って
say map { sqrt($_) } (1 .. 5);
とも書ける。

sort.plの中のmapでは、<DATA>のリストの各要素をsub_lengthサブルーチンに渡し、その戻り値(<DATA>の各レコードの長さ)をリストにして返す。
で、そのリストは長さ(数値)であるから、それを{$a <=> $b}という論理でsortすると、「寺の名前の長さ」(数値)が短い順に出てくる。
寺の長さを数値化したものなんかソート出力されても仕方ないのだが、mapしてからソートしたので、sub_lengthが5回しか呼ばれていない点は注目しよう。

以上、間違ったプログラムを長々と説明したが、このプログラムを正しくするとこうなる。
#! /usr/local/bin/perl
#
# sort.pl --- ソートのテスト

use 5.010;
use strict;
use warnings;
use utf8;
binmode STDOUT, ":utf8";

our $i;
print map $_-> [0], sort {$a->[1] <=> $b->[1]} map [$_, sub_length($_)], <DATA>;

sub sub_length {
   my $parm = shift;
   print ++$i, ": length called with $parm";
   return length $parm;
}

__DATA__
教王護国寺
金剛峯寺
清荒神清澄寺
東寺
法隆寺
実行する。
[perl]$ ./sort.pl
1: length called with 教王護国寺
2: length called with 金剛峯寺
3: length called with 清荒神清澄寺
4: length called with 東寺
5: length called with 法隆寺
東寺
法隆寺
金剛峯寺
教王護国寺
清荒神清澄寺
[perl]$
できてるね。

この、もともとのソート関数
sort {sub_length($a) <=> sub_length($b)} <DATA>;

map $_-> [0], sort {$a->[1] <=> $b->[1]} map [$_, sub_length($_)], <DATA>;
という、map+sort+sortに変換して高速化を測るのがシュウォーツ変換だ。

これ、なかなか分かりにくいのだが、後ろから解読していこう。
map [$_, sub_length($_)] <DATA>
は、<DATA>というリストを、各要素と、その各要素をsub_lengthに渡した戻り値で出来た、2要素の無名配列というものにmapで変換している。
無名配列というのは[$_, sub_length($_)]の部分のことだが、($_, sub_length($_))という2要素のリストへのリファレンスのことだ。

なぜリストではなく、リストへのリファレンスというものにしたかというと、二重配列を作るためだ。
map $_-> [0], sort {$a->[1] <=> $b->[1]} map [$_, sub_length($_)], <DATA>;
は以下のものと同値である。
my @arr = map [$_, sub_length($_)], <DATA>;
map $_-> [0], sort {$a->[1] <=> $b->[1]} @arr;
ここで、<DATA>というリストは、上のプログラムでは、
("教王護国寺",
  "金剛峯寺",
  "清荒神清澄寺",
  "東寺",
  "法隆寺")
という5要素のリストであるが、これが@arrには、map関数によって以下のように変換されたものがセットされる。
(["教王護国寺", 5],
  ["金剛峯寺", 4],
  ["清荒神清澄寺", 6],
  ["東寺", 2],
  ["法隆寺", 3])
リストの各要素は、["寺の名前(文字列)", 寺の名前の長さ(数値)]という無名配列がセットされているのである。

このリストをsort関数によって、長さ、つまり、無名配列の2要素目によってソートする。これが
sort {$a->[1] <=> $b->[1]} @arr
の部分である。
@arrの各要素から、インデックス1の部分(配列のインデックスはゼロ始まりだから2要素目のインデックスが1になる)を取り出し、それをキーにソートする。

ある配列へのリファレンスが$xというスカラーに入っている場合、その配列の2要素目を返す式は$x->[1]と書く。
だから、上のsort関数によって、@arrが各要素の2要素目で昇順(小さい順)にソートされる。
(["東寺", 2],
  ["法隆寺", 3],
  ["金剛峯寺", 4],
  ["教王護国寺", 5],
  ["清荒神清澄寺", 6])
で、このリファレンスから、printするときは1要素目を取り出す。
これにもう1回mapを使う。
map $_-> [0], sort {$a->[1] <=> $b->[1]} @arr;
ここで $_->[0] は、$_に無名配列が入っているとき、その1要素目を抽出する式である。

ということで、注釈をめいっぱい入れてシュウォーツ変換を書いてみる。
# 注釈は下から読む
map $_-> [0],         # 1要素目に再マップする
 sort {$a->[1] <=> $b->[1]}  # 配列を無名配列の1要素目でソートして
 map            # マップする
 [$_, sub_length($_)],     # 各要素と、それをソート関数に渡した戻り値で出来た2要素の無名配列に
 <DATA>;          # 配列を

map関数、sort関数、map関数を数珠つなぎにしているのを、後ろから理解する。

注釈を逆に書くと
配列を各要素と、それをソート関数に渡した戻り値で出来た
2要素の無名配列にマップする
配列を無名配列の1要素目でソートして、
1要素目に再マップする
ということになる。

これを、著作権に関係ないところでベートーヴェンの第9のテーマ(喜びの歌)に変換したのが上記の歌詞である。
♪配列を各要素とソート関数値で出来た
♪2要素の無名配列リファレンスにマップ
♪配列の2要素目でソートした後で
♪1要素目に再マップでシュウォーツ変換
意外とわかりやすくないですか。

ちなみにヴォーカロイドUTAUで音声化した音声がコチラ

本にはもっともっと分かりやすく書いてある。
(ここにきて宣伝かよ!)