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

そこで、この歌で何をどう覚え込もうとしているのか、改めて紹介しよう。
先日、ツイッターで、歌だけを紹介したら、そこそこバズった。
そこで、この歌で何をどう覚え込もうとしているのか、改めて紹介しよう。
以下のプログラムは、文字列を短い順にソートしている。
これをsort関数で並べ替えている。
{}で渡しているのは、ソートの順番を決めるコードブロックだ。
この中では、$a、$bというPerl組み込みの特殊変数を使い、$aが$bよりも小さい時は1、等しい時は0、大きい時は-1を返すコードを書く。
<=>というのは宇宙船演算子といい、スター・ウォーズの「ダース・ヴェイダー専用コアファイター」に似ているからそういう名前がついているそうだが、左の項と右の項を数値として比較し、左が右より小さい時は1、等しい時は0、大きい時は-1を返す。
length関数は引数の長さを返す関数である。
これで、__DATA__以降のレコードが短い順に表示される。
これ、5レコードしか並べ替えていないから一瞬で終わるけど、何万、何十万というお寺の名前をソートすると、そーとー時間が掛かる。
(スミマセン。)
ソートの早さを比較するというのはコンピューター好きを燃えさせる課題であって、いろいろな方法が提唱されている。
改善する方法の1つががシュウォーツ変換である。
上のプログラムの実行時間は、文字列の長さを定めるlength関数が、何回呼び出されているかによって変わる。
ちょっと調べてみよう。
実行。
総当りだから仕方ないが、並びによってはこの数はさらに増える。
この回数を減らす方法に取り組む(sort関数自体を改善する)というのもいいが、ある文字列の長さを測るという、そこそこ手間の掛かりそうな関数lengthを呼ぶのを、最初に全部済ませればいいのではないだろうか。
つまり、__DATA__の全レコードについて、最初にlength関数を掛けてしまって、その戻り値をソートすればいいのではないだろうか。
実行してみる。
最後に「34567」とダダダッと表示しているのは、__DATA__の下のお寺の名前の文字数をソートして、改行なしに表示しているのだ。
ダメなりにプログラムを解説してみよう。
print sort {$a <=> $b} map { sub_length ($_) } <DATA>;
というのは、<DATA>というリストをmap関数に渡して、その出力をsort関数に渡して、その出力をprintしている。
map関数というのは、第2引数に渡されたリストに、第1引数で渡された操作を行って、その戻り値をリストとして返す。
第1引数はブレース({})で囲まれたコードブロックであって、第2引数のリストの各要素を$_に代入して渡す。
コードブロックの中で、リストの各要素は、Perlのデフォルト変数$_になる。
なお、上のコードは、マジックインクリメント演算子「..」を使って
sort.plの中のmapでは、<DATA>のリストの各要素をsub_lengthサブルーチンに渡し、その戻り値(<DATA>の各レコードの長さ)をリストにして返す。
で、そのリストは長さ(数値)であるから、それを{$a <=> $b}という論理でsortすると、「寺の名前の長さ」(数値)が短い順に出てくる。
寺の長さを数値化したものなんかソート出力されても仕方ないのだが、mapしてからソートしたので、sub_lengthが5回しか呼ばれていない点は注目しよう。
以上、間違ったプログラムを長々と説明したが、このプログラムを正しくするとこうなる。
この、もともとのソート関数
これ、なかなか分かりにくいのだが、後ろから解読していこう。
無名配列というのは[$_, sub_length($_)]の部分のことだが、($_, sub_length($_))という2要素のリストへのリファレンスのことだ。
なぜリストではなく、リストへのリファレンスというものにしたかというと、二重配列を作るためだ。
このリストをsort関数によって、長さ、つまり、無名配列の2要素目によってソートする。これが
@arrの各要素から、インデックス1の部分(配列のインデックスはゼロ始まりだから2要素目のインデックスが1になる)を取り出し、それをキーにソートする。
ある配列へのリファレンスが$xというスカラーに入っている場合、その配列の2要素目を返す式は$x->[1]と書く。
だから、上のsort関数によって、@arrが各要素の2要素目で昇順(小さい順)にソートされる。
これにもう1回mapを使う。
ということで、注釈をめいっぱい入れてシュウォーツ変換を書いてみる。
map関数、sort関数、map関数を数珠つなぎにしているのを、後ろから理解する。
注釈を逆に書くと
これを、著作権に関係ないところでベートーヴェンの第9のテーマ(喜びの歌)に変換したのが上記の歌詞である。
ちなみにヴォーカロイドUTAUで音声化した音声がコチラ。
本にはもっともっと分かりやすく書いてある。
(ここにきて宣伝かよ!)
#! /usr/local/bin/perl簡単に解説すると、<DATA>というのは__DATA__以降のデータ(お寺の名前が5行書いている)をリストで返す。
#
# sort.pl --- ソートのテスト
use 5.010;
use strict;
use warnings;
use utf8;
binmode STDOUT, ":utf8";
print sort {length($a) <=> length($b)} <DATA>;
__DATA__
教王護国寺
金剛峯寺
清荒神清澄寺
東寺
法隆寺
これをsort関数で並べ替えている。
{}で渡しているのは、ソートの順番を決めるコードブロックだ。
この中では、$a、$bというPerl組み込みの特殊変数を使い、$aが$bよりも小さい時は1、等しい時は0、大きい時は-1を返すコードを書く。
<=>というのは宇宙船演算子といい、スター・ウォーズの「ダース・ヴェイダー専用コアファイター」に似ているからそういう名前がついているそうだが、左の項と右の項を数値として比較し、左が右より小さい時は1、等しい時は0、大きい時は-1を返す。
length関数は引数の長さを返す関数である。
これで、__DATA__以降のレコードが短い順に表示される。
これ、5レコードしか並べ替えていないから一瞬で終わるけど、何万、何十万というお寺の名前をソートすると、そーとー時間が掛かる。
(スミマセン。)
ソートの早さを比較するというのはコンピューター好きを燃えさせる課題であって、いろいろな方法が提唱されている。
改善する方法の1つががシュウォーツ変換である。
上のプログラムの実行時間は、文字列の長さを定めるlength関数が、何回呼び出されているかによって変わる。
ちょっと調べてみよう。
#! /usr/local/bin/perl組み込み関数lengthをサブルーチンsub_lengthで包んで、呼ばれた回数と引数を表示してみた。
#
# 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__
教王護国寺
金剛峯寺
清荒神清澄寺
東寺
法隆寺
実行。
[perl]$ ./sort.pl14回呼んでいる。
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 金剛峯寺
東寺
法隆寺
金剛峯寺
教王護国寺
清荒神清澄寺
総当りだから仕方ないが、並びによってはこの数はさらに増える。
この回数を減らす方法に取り組む(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>;ここで、<DATA>というリストは、上のプログラムでは、
map $_-> [0], sort {$a->[1] <=> $b->[1]} @arr;
("教王護国寺",という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],で、このリファレンスから、printするときは1要素目を取り出す。
["法隆寺", 3],
["金剛峯寺", 4],
["教王護国寺", 5],
["清荒神清澄寺", 6])
これにもう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で音声化した音声がコチラ。
本にはもっともっと分かりやすく書いてある。
(ここにきて宣伝かよ!)