「【Perl, Python】map、grep、sort の比較」に続き、map、sort を使って高速なソート手法であるシュワルツ変換を書いてみよう。
シャチ泳ぎとシュワルツ変換 – perl-mongers.org
http://perl-mongers.org/2008/05/schwartzian_transform_and_orcish_maneuver.htmlSchwartzian transform – Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Schwartzian_transform
シュワルツ変換とは、ある配列の要素をそれぞれの属性値に従ってソートする場合、一度属性値を全て計算した配列を作ることでソートを高速化することを言う。
……と、言葉で説明してもアレだし、例を挙げてみよう。次のように、九州の各県の人口を表したテキストファイルがあるとする1。
kyushu.txt
エンコーディングは UTF-8 とする。
長崎県 1,478,632 人 佐賀県 866,369 人 福岡県 5,049,908 人 熊本県 1,842,233 人 大分県 1,209,571 人 宮崎県 1,153,042 人 鹿児島県 1,753,179 人 沖縄県 1,361,594 人
これを人口の少ない順に並べ直し、次のような出力を得たい。
佐賀県 866,369 人 宮崎県 1,153,042 人 大分県 1,209,571 人 沖縄県 1,361,594 人 長崎県 1,478,632 人 鹿児島県 1,753,179 人 熊本県 1,842,233 人 福岡県 5,049,908 人
Perl の場合
schwartz.pl
#!/usr/bin/perl
use strict;
use warnings;
use utf8;
use Encode;
# Windows の場合
binmode STDOUT => ":encoding(cp932)";
# Mac や Linux 等の場合
# binmode STDOUT => ":utf8";
# コマンドライン引数に指定されたファイルから読み込む
my @ary1 = map decode_utf8( $_ ), <>;
# 各行から人口を表す整数を取り出す関数
sub population {
my $p = ( split /\s+/, shift )[1];
$p =~ s/,//g;
$p;
}
# シュワルツ変換開始
my @ary2 = map $_->[0],
sort { $a->[1] <=> $b->[1] }
map [ $_, population( $_ ) ], @ary1;
# 画面に表示する
print $_ for @ary2;
実行例
C:\> schwartz.pl kyushu.txt 佐賀県 866,369 人 宮崎県 1,153,042 人 大分県 1,209,571 人 沖縄県 1,361,594 人 長崎県 1,478,632 人 鹿児島県 1,753,179 人 熊本県 1,842,233 人 福岡県 5,049,908 人
肝となるのはハイライトした 22 行目～ 24 行目だ。これは後ろから順に読んでいくと分かり易い。
24 行目
map [ $_, population( $_ ) ], @ary1;
これは map を使って、@ary1 の各要素と、それに population 関数を適用したものの組を作成している。
# 元のテキスト "長崎県 1,478,632 人", "佐賀県 866,369 人", "福岡県 5,049,908 人", …… # 変換後 [ "長崎県 1,478,632 人", 1478632 ], [ "佐賀県 866,369 人", 866369 ], [ "福岡県 5,049,908 人", 5049908 ], ……
23 行目
sort { $a->[1] <=> $b->[1] }
ここでは、24 行目で求めた組の 2 つ目の要素（つまり人口を表す整数）に従ってソートを行っている2。この時点で、次のように並べ替えが完了している。
[ "佐賀県 866,369 人", 866369 ], [ "宮崎県 1,153,042 人", 1153042 ], [ "大分県 1,209,571 人", 1209571 ], ……
22 行目
my @ary2 = map $_->[0],
ここでは、組から 1 つ目の要素だけを取りだしている。つまり、23 行目で並べ替えられた元のテキストのみが @ary2 に入ることになる。
"佐賀県 866,369 人", "宮崎県 1,153,042 人", "大分県 1,209,571 人", ……
この map → sort → map の組み合わせがシュワルツ変換だ。今回のように要素数が少なく、又、要素の属性値を取り出すプロセス3のコストが大したことがない場合には、実はあまり効果がない。だが、これが重たい処理、例えば、ファイルシステム、データベース、Web 等へのアクセスを伴うようになると話は変わってくる4。覚えておいて損はないだろう。
Python の場合
Python では、このシュワルツ変換5をネイティブでサポートしている。
2 ネイティブ DSU
Python 2.4 から
sort()メソッドやsorted()関数で、DSU をネイティブにサポートしている。キーワード引数keyを使用し、キーを取得する関数（オブジェクト）を指定できる。すると内部で DSU が使用される。使い方は以下の通り。
schwartz.py
# /usr/bin/python
# coding=utf-8
import re
import codecs
import sys
# コマンドライン引数に指定されたファイルから読み込む
f = codecs.open( sys.argv[1], "r", "utf8" )
ary1 = f.readlines()
# 各行から人口を表す整数を取り出す関数
def population( s ):
p = s.split()[1]
p = re.sub( ",", "", p )
return int( p )
# シュワルツ変換開始
ary2 = sorted( ary1, key = population )
# 画面に表示する
for x in ary2:
print x,
これはスマートだ。さすが Python は後発だけあって、シンプルでエレガントな構文が用意されている。勿論、一時変数を使って無理矢理 Perl 的なシュワルツ変換を書くことも出来るが……読みにくいね。
# シュワルツ変換開始 tmp1 = map( lambda x: ( population( x ), x ), ary1 ) tmp1.sort() ary2 = map( lambda x: x[1], tmp1 )
最後におまけ
今回例として挙げたようなテキストの並べ替えは、Unix 系 OS の sort コマンドを使った方が断然簡単である。
$ cat kyushu.txt | sort -k2 -n 佐賀県 866,369 人 宮崎県 1,153,042 人 大分県 1,209,571 人 沖縄県 1,361,594 人 長崎県 1,478,632 人 鹿児島県 1,753,179 人 熊本県 1,842,233 人 福岡県 5,049,908 人
-k2 オプションによって 2 番目の列を並べ替え項目に指定し、それを -n オプションによって数値的に比較している。
はじめまして、
sub population {my $p = ( split /\s+/, shift )[1];
の部分が、 長崎県 1,478,632 を空白で区切って、2列目の数字を $p に入れようとしている意図と思いますが、split記述で、, shift )[1]; と書いている部分の shift と [1] の間に ) があるのに、2列目の数字が $p に入ってくれるもは なぜでしょうか？
初めまして。
少々わかりにくい書き方をしてしまいましたが、ココは以下のような処理をしています。
my $p = ( split /\s+/, shift )[1];populationサブルーチンには"長崎県 1,478,632 人"といった文字列が渡されるので、このshiftは"長崎県 1,478,632 人"に置き換えられます。よってこの
splitは以下のように処理されます。split /\s+/, "長崎県 1,478,632 人"=> ("長崎県", "1,478,632", "人")
そして
[1]で 2 つ目の要素を取り出してるわけですね。("長崎県", "1,478,632", "人")[1] => "1,478,632"()で括られた、split文の結果を別の配列に格納した方が分かりやすかったかもしれません。my @tmp = split /\s+/, shift;my $p = $tmp[1];
早速の返信ありがとうございました。