続・はじめてのPerl 9章
9章 リファレンスを使った実践的なテクニック
9.1 ソートとは
sort演算子 デフォルトの動作は、テキスト本来の順序付け 現在のロケールと、文字セットで決まるソート順 詳細は、perllocale 他のソート順でソートしたい場合 ソートアルゴリズムを書く必要はない 2個のアイテムを処理するコードを書くだけでいい 2個のアイテムを処理するコード sortキーワードと対象配列の間にソートブロックを指定 ソートブロック内で、新しい比較方法を指定する ソートブロックの代わりに、名前付きサブルーチンを指定することも可能 ソートブロック内での比較方法 比較する2つのアイテムは、$aと$bに格納されて渡される ソートブロックは、ソート順を示す値を返さなければならない ・返す値が -1 $aが$bより前に配置されるようにしたい場合 ・返す値が +1 $bが$aより前に配置されるようにしたい場合 ・返す値が 0 どちらの順番でもかまわない場合 0が返された場合 最近のPerlでは、$aと$bの順番は、元のリストの順番が維持される これを安定ソートという 安定ソートかどうかは、バージョンに依存する 将来のPerlでは、安定ソートではないかもしれない
my @array = qw/ 4 3 2 43 53 13 1 /; my @new_array = (); # $aと$bを使ったソートブロック @new_array = sort { if ( $a < $b ) { -1; } elsif ( $a > $b ) { 1; } else { 0; } } @array; print "@new_array\n"; # 1 2 3 4 13 43 53 # スペースシップ演算子を使う @new_array = sort { $a <=> $b } @array; print "@new_array\n"; # 1 2 3 4 13 43 53 # 降順ソート @new_array = reverse sort { $a <=> $b } @array; print "@new_array\n"; # 53 43 13 4 3 2 1 # 降順ソート、もう一つのやり方 @new_array = sort { $b <=> $a } @array; print "@new_array\n"; # 53 43 13 4 3 2 1 # ソートブロックの代わりにサブルーチンを使う sub asc_order { $a <=> $b; } @new_array = sort asc_order @array; print "@new_array\n"; # 1 2 3 4 13 43 53
9.2 添え字を使ったソート
my @input = qw( Gilligan Skipper Professor Ginger Mary_Ann ); # @sorted_positions には、元の要素を指す添え字が入る # 並び順は、元の要素を文字列で昇順ソートしたときのもの my @sorted_positions = sort { $input[$a] cmp $input[$b] } 0 .. $#input; print "@sorted_positions\n"; # 0 3 4 2 1 print "@input[ @sorted_positions ]\n"; # Gilligan Ginger Mary_Ann Professor Skipper # @input の要素が、ソート後何番目に来るのかを求める my @rank = (); @rank[ @sorted_positions ] = ( 0 .. $#sorted_positions ); print "@rank\n"; # 0 4 3 1 2
9.3 効率のよいソート
my %age = ( myself => 26, brother => 20, mother => 50, father => 50, ); sub get_age { print "return $_ age\n"; return $age{$_}; } # 若い順に名前を並べる my @name = sort { get_age( $a ) <=> get_age( $b ) } keys %age; print "@name\n"; __END__ 実行すると以下のような出力が得られる return: father age return: brother age return: mother age return: myself age return: brother age return: myself age return: myself age return: father age return: father age return: mother age brother myself father mother
サブルーチンが何度も呼ばれているのが分かる
サブルーチンの処理コストが高い場合、これは問題となりえる
これを効率よく処理するためには、以下のように処理する
# 名前と年齢を値にもつ配列リファレンスの配列を作る my @name_and_age = map { [ $_, get_age( $_ ) ] } keys %age; # @name_and_age を使い若い順に並び替える my @asc_name_and_age = sort { $a->[1] <=> $b->[1] } @name_and_age; # @asc_name_and_age から名前を取り出す my @name = map { $_->[0] } @asc_name_and_age; print "@name\n"; __END__ 実行すると以下のような出力が得られる return: father age return: brother age return: mother age return: myself age brother myself father mother
サブルーチンの呼び出し回数が減ったことが確認できる
9.4 シュワルツ変換
「9.3 効率のよいソート」のコードにおける、
@name_and_age @asc_name_and_age は、@name を求めるための中間変数
以下のようにステップをまとめる事で、変数名を考える必要がなくなる
このようなものを一般に、「シュワルツ変換」と呼ぶ
my @name = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [ $_, get_age( $_ ) ] } keys %age;
9.5 シュワルツ変換を使ったマルチレベルソート
シュワルツ変換が役に立つ場合
複数の基準に基づいてソートしなければならない場合
my %age = ( myself => 26, brother => 20, mother => 50, father => 50, ); my %sex = ( myself => 'man', brother => 'man', mother => 'woman', father => 'man', ); my %sex_dv = ( woman => 1, man => 2, ); sub get_age { my $name = shift; return $age{$name}; } sub get_sex_dv { my $name = shift; return $sex_dv{ $sex{$name} }; } # sex_dvの値と、年齢で昇順ソート my @name = map { $_->[0] } sort { $a->[1] <=> $b->[1] || $a->[2] <=> $b->[2] } map { [ $_, get_sex_dv( $_ ), get_age( $_ ) ] } keys %age; print "@name\n"; # mother brother myself father
9.6 再帰的に定義されたデータ
再帰的なアルゴリズム 基本ケースからスタート その上に構造を積み重ねていく 基本ケースとは もっとも単純な条件で何をするか 例えば、 ・葉ノードが枝を持たないとき ・配列が空のとき ・カウンタが0のとき 基本ケースを持たない再帰アルゴリズムは無限ループとなる 再帰サブルーチン 自分自身を呼び出す部分と、基本ケースを呼び出す部分を持つ
# 階乗計算。最も単純な再帰関数の1つ sub factorial { my $num = shift; if ( $num <= 1 ) { return 1; } else { return $num * factorial( $num - 1 ); } } print factorial( 3 ), "\n"; # 6 print factorial( 5 ), "\n"; # 120
9.7 再帰的に定義されたデータの構築
# 指定したパスのディレクトリ構造をハッシュに落とし込むサンプル use Data::Dumper; sub data_for_path { my $path = shift; # ファイルまたは、シンボリックリンクの場合 if ( -f $path or -l $path ) { return undef; } if ( -d $path ) { my %directory = (); opendir my $dir, $path or die "Cannot opendir $path: $!"; my @names = readdir $dir; closedir $dir; for my $name ( @names ) { next if $name eq '.' or $name eq '..'; $directory{$name} = data_for_path( "$path/$name" ); } return \%directory; } warn "$path is neither a file not a directory\n"; return undef; } my $directory = data_for_path( '../' ); print Dumper $directory;
感想
頭の中で処理の流れを追えなくなるので再帰は苦手。
場数こなせば、得意になるのかな。
