studies

いろいろ勉強用備忘録的な感じ

perlで順序を保つグルーピング ~優先度からの解放~

excelでちょっと複雑なソート - studies
perlでちょっと複雑なソート - studies
perlでちょっと複雑なソート2 - studies
perlでちょっと複雑なソート3 - studies
ワンライナーでちょっと複雑なソート - studies

今までタイトルに「ソート」と付けていたように、この問題を「ソート」の問題として解いてきた。
今回は別の視点でこの問題を解いてみよう。

「別の視点で」と書いたが、実は最初からこの問題は必ずしもソートの問題として定義されていたわけではない。
私の書いた問題文はこうだった。

これを、次の条件でソートするのが本日の課題であった。

 1.基本的な順番は変えない。

 2.同じ都道府県どうしをまとめる。

たとえば、上の例のデータでいえば、次のようにソートすることになる。

 1.第4行まではすべて異なる都道府県なので、とりあえずここまでは何もしない。

 2.第1行で京都府京都市がでてきたあと、第5行で京都府宮津市が出てくる。同じ都道府県同士をまとめるので、第1行と第2行との間に、この第5行目のデータを挿入する。

 3.そのあとさらに下を見ていくと、長野県諏訪市が出てくる。このデータを長野県松本市のすぐ下に移動する。

重要なのは2の「同じ都道府県同士をまとめる」というところだ。
つまり、この問題はソートの問題ではなくグルーピングの問題であると考えてもよい。
(正確に言えば、グルーピング+ソートの問題なのだが、どちらに重点を置くか、ということで少し解き方が変わってくるように思う)。

この問題は、グルーピングした結果を表示するときに、元の順序をできるだけ保つようにする、というだけなのだ。
ここでいう「順序を保つ」というのは、最初に出てきたグループを優先し、次にグループ内では最初に出てきたメンバを優先する、ということだ。

これまで、条件1の「基本的な順番は変えない」という点に注目していたが、今回は条件2に着目してみよう。
アルゴリズム的には「たとえば」以下で書かれた方法をほぼそのまま採用する。
このアルゴリズムは優先度を全く使っていないのが特徴だ。
優先度を設定して、その優先度順にソートするというのは、おそらくプログラム的には早いのだが、必ずしも人間にわかりやすいものとは言えない。
今回は、優先度を設定せずに書いたので、直観的なコードになったと思う。

次のようになる。

#! /usr/bin/perl -a

push @groups, $F[1] unless grep {$_ eq $F[1]} @groups;
push @{$members{$F[1]}}, $_;

END {
    print @{$members{$_}} for (@groups);
}

説明する。
最初に@groupsという配列に、第2フィールドの要素(つまり都道府県)をpushしている。
ただし、これを行うのは都道府県が最初に現れた時だけだ。
その判定を、unless grepで行っている。
次に、各都道府県の市区町村(本当は行)を、都道府県から決まる配列にpushしている。
ここで、配列のリファレンスに値を持つハッシュ%membersを使い、それを@でデリファレンスして使っているのがポイント。
リファレンスを使っているのでややこしいが、配列に値を持つハッシュを作っていると思えばOK。
最終的には、こんな感じのハッシュが作られるわけである。

%members = 
(
  京都府 => [ 京都市 京都府, 宮津市 京都府, 宇治市 京都府 ],
  東京都 => [ 千代田区 東京都, 渋谷区 東京都, 新宿区 東京都 ],
  .....
)

そして、groupごとに配列を展開してprintして終わり、というのが上のコードの意図するところである。

下のようにkeys関数でグループを求めたくなるが、「Perlでは、ハッシュの要素の順序が保存されない」(『初めてのPerl』, p142)ため、この方法だと、どの順序でグループが現れるかわからなくなってしまう。この方法は使えない。

#! /usr/bin/perl -a

push @{$members{$F[1]}}, $_;

END {
    print @{$members{$_}} for (keys %members);  # しまった!
}

また、毎回unless grepという条件判定を行うのは重いので、とりあえずpushして、最後に順序を保ちながら重複を取り除く、という考え方もできる。
そのときは、下のように"grep {!$seen{$_}++} @groups"という呪文を唱えることになる。
これは有名なイディオムだが、コード全体の直観性を重視した今回の方針から言えば、ちょっと避けたい書き方ではある。

#! /usr/bin/perl -a

push @groups, $F[1]; 
push @{$members{$F[1]}}, $_;

END {
    print @{$members{$_}} for (grep {!$seen{$_}++} @groups);
}

追記:
unless grepという条件判定が遅いことに対しては、exists関数を使って下のように対処するのが良さそう。
grepの計算時間はO(N)だが、ハッシュを使った下の書き方なら計算時間は定数時間O(1)になるハズ。

#! /usr/bin/perl -a

push @groups, $F[1] unless exists $members{$F[1]};
push @{$members{$F[1]}}, $_;

END {
    print @{$members{$_}} for (@groups);
}