「【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 が使用される。使い方は以下の通り。
http://morchin.sakura.ne.jp/effective_python/sort.html
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 オプションによって数値的に比較している。
*1
: 人口のデータは「都道府県の人口一覧 - Wikipedia」より得た。
*2
: ちなみに、ここで使われている $a、$b はグローバル変数であり、my 演算子による宣言は必要ない。又、その中身を sort ブロックの中で変更すると何が起こるが予測できないので注意。
*3
: 今回の例で言えば、テキストから人口を表す整数を取り出す population 関数（13 行目～ 17 行目）。
*4
: sort 関数で使われるブロックは要素数より遙かに多く呼び出されるため、その度に属性値を計算しているといつまで経ってもソートが終わらない。
*5
: こちらの世界では DSU と呼ぶのが一般的なようだ。
- Newer: 【Python 事始め】404 エラーを補足する
- Older: 【Perl, Python】map、grep、sort の比較
Comments:0
Trackbacks:0
- TrackBack URL for this entry
- http://blog.remora.cx/mt/mt-tb.fcgi/322
- Listed below are links to weblogs that reference
- 【Perl, Python】シュワルツ変換あるいは優雅なる DSU from blog.remora.cx
