2017年の目論見
あけましておめでとう。
年は明けて2017年。
今年もよろしくお願いします。
年頭よろしく、今後の目論見なんかを作ってみる。
ブログの更新頻度向上
アウトプットの場としてのブログの利用価値を見直す。
応用情報技術者
4月の試験はこれ。
ネットワークスペシャリスト
10月の試験はこれかな。
正直ネットワークにはあまり興味がないのが辛いところ。
でもネットワーク知らないと、環境構築とかできないし。
機械学習
最近はやり。
やっぱりちょっと興味持っちゃうよね。
C++
結局かじっただけになっているオブジェクト指向言語。
たぶん今後も仕事で付き合うことになる。
コンピュータアーキテクチャ
基本だけど、表面的にしか理解していないことが多い分野という感じ。
今年の終わりには「実感」を持てるようになりたい。
perlで順序を保つグルーピング ～優先度からの解放～
excelでちょっと複雑なソート - studies
perlでちょっと複雑なソート - studies
perlでちょっと複雑なソート2 - studies
perlでちょっと複雑なソート3 - studies
ワンライナーでちょっと複雑なソート - studies
今までタイトルに「ソート」と付けていたように、この問題を「ソート」の問題として解いてきた。
今回は別の視点でこの問題を解いてみよう。
「別の視点で」と書いたが、実は最初からこの問題は必ずしもソートの問題として定義されていたわけではない。
私の書いた問題文はこうだった。
これを、次の条件でソートするのが本日の課題であった。
１．基本的な順番は変えない。
２．同じ都道府県どうしをまとめる。
たとえば、上の例のデータでいえば、次のようにソートすることになる。
１．第4行まではすべて異なる都道府県なので、とりあえずここまでは何もしない。
２．第1行で京都府京都市がでてきたあと、第5行で京都府宮津市が出てくる。同じ都道府県同士をまとめるので、第1行と第2行との間に、この第5行目のデータを挿入する。
重要なのは２の「同じ都道府県同士をまとめる」というところだ。
つまり、この問題はソートの問題ではなくグルーピングの問題であると考えてもよい。
（正確に言えば、グルーピング＋ソートの問題なのだが、どちらに重点を置くか、ということで少し解き方が変わってくるように思う）。
この問題は、グルーピングした結果を表示するときに、元の順序をできるだけ保つようにする、というだけなのだ。
ここでいう「順序を保つ」というのは、最初に出てきたグループを優先し、次にグループ内では最初に出てきたメンバを優先する、ということだ。
これまで、条件１の「基本的な順番は変えない」という点に注目していたが、今回は条件２に着目してみよう。
アルゴリズム的には「たとえば」以下で書かれた方法をほぼそのまま採用する。
このアルゴリズムは優先度を全く使っていないのが特徴だ。
優先度を設定して、その優先度順にソートするというのは、おそらくプログラム的には早いのだが、必ずしも人間にわかりやすいものとは言えない。
今回は、優先度を設定せずに書いたので、直観的なコードになったと思う。
次のようになる。
#! /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); }
ワンライナーでちょっと複雑なソート
早く目が覚めてしまった。
これは午後眠くなるぞー。
最後の仕上げ？として、perlを使わず、ワンライナーでやってみる。
（もしかしたらまだ続くかも）。
awk '{p[$2] || (p[$2]=NR); print p[$2], $0;}' city.txt | sort -snk1 | sed -E 's/^\S+\s+//'
まず、awkの連想配列を使って、優先度を頭につける。
そのあとsortでソート。
sオプションは、安定ソートにするオプション
（デフォルトはおそらくクイックソートで不安定）。
nオプションは、数値としてソートするオプション
（デフォルトは文字列としてソート）。
kオプションは、特定のフィールドをキーにするオプションで、ここでは第1フィールド、つまり、awkで設定した優先度を指定している。
最後にsedで優先度を削除する。
Eオプションは拡張正規表現を使うオプションで、ここでは1回以上の繰り返しを表す量指定子を\+ではなく単に+と書くために指定している。
個人的には、sortコマンドに、こんなにいろいろなオプションがつけられるというのが発見。
perlの宇宙船演算子<=>を使ったソートルールの指定も感心したけれど、sortコマンドでもこんなにいろいろできたとは。
perlでちょっと複雑なソート3
この問題、さらに改良してみる。
studies.hatenablog.com
#! /usr/bin/perl -a use 5.010; use sort 'stable'; push @lines, $_; $priority{$F[1]} //= $.; END { print (sort { $priority{(split /\s+/, $a)[1]} <=> $priority{(split /\s+/, $b)[1]} } @lines); }
awk風のループを仮定する-aオプションをつけて、フィールド変数@Fを使えるようにする。
@Fはawkでいうところの$1,$2,...と同じ（ただし添え字は0始まり）。
これを用いて優先度をハッシュで作成する。
$countの代わりに使っている$.はawkでいうところのNRで、行番号。
メインループで優先度の設定をした後、ENDブロックでソートして出力。
%prefというハッシュは今回は使わず、ソートの際に行そのものからsplitとリストスライスで要素を取り出している。
（ここでも@Fが使えればいいけれど…）。
これはほぼ、excelでやったのと同じアルゴリズムだ。
excelではC2に以下を書いて、これをオートフィル&C列をキーにして並び替えしたのだった。
=iferror(match($b2, $b$1:$b1, 0), row())
もちろんexcelでやったのと比べれば、計算量はだいぶ減っている。
ちなみに、私の環境ではデフォルトで安定ソートの模様なので、実は"use sort 'stable';"のくだりもいらないのではという気もしたが、ちゃんとperldocに以下の記述がある。
The default algorithm is mergesort, which will be stable even if you do not explicitly demand it. But the stability of the default sort is a side-effect that could change in later versions. If stability is important, be sure to say so with a
use sort 'stable';
デフォルトのアルゴリズムはマージソートなので、あなたが安定を望んでいることを明示しなくても、安定にソートされる（動くことは動く）。しかし、このデフォルトは後のバージョンで変更になるかもしれない。もし安定性が大切なら、use sort 'stable';と書くこと。
今回は安定性が大切なので、書かなければならない。
perlでちょっと複雑なソート2
昨日のエントリの最後で、use sortプラグマを使うことで、perlのソートに安定性を保証することができるという話を書いた。
そこで今回は、これを使って先日のソースを改良してみる。
#! /usr/bin/perl use 5.010; use sort 'stable'; while (<>) { push @lines, $_; $pref = (split)[1]; $pref{$_} = $pref; $priority{$pref} //= ++$count; } for (sort { $priority{$pref{$a}} <=> $priority{$pref{$b}} } @lines) { print; }
安定ソート（perldocによれば、マージソートのようだ）を使うことで、ソートのルールを一つ減らしている。
つまり、city_priorityがなくなり、pref_priorityだけになっている（この際だから名前はpriorityにする）。
実行結果は以下の通り。
今度は市区町村から都道府県へのハッシュではなく、行から都道府県へのハッシュにした。
それでprintfも使っていないので、表示もずれなくなった。OK。
$ cat city.txt 京都市 京都府 千代田区 東京都 高岡市 富山県 松本市 長野県 宮津市 京都府 川崎市 神奈川県 諏訪市 長野県 渋谷区 東京都 滑川市 富山県 新宿区 東京都 臼杵市 大分県 稚内市 北海道 氷見市 富山県 いわき市 福島県 長野市 長野県 横須賀市 神奈川県 宇治市 京都府 $ ./sort2.pl city.txt 京都市 京都府 宮津市 京都府 宇治市 京都府 千代田区 東京都 渋谷区 東京都 新宿区 東京都 高岡市 富山県 滑川市 富山県 氷見市 富山県 松本市 長野県 諏訪市 長野県 長野市 長野県 川崎市 神奈川県 横須賀市 神奈川県 臼杵市 大分県 稚内市 北海道 いわき市 福島県
perlでちょっと複雑なソート
まただいぶ間が空いてしまった。
その間に私は、基本情報技術者という資格試験を受けたり、引っ越したりしていた。
最近少し落ち着いてきたし、間が空きすぎるのもよくないので、余りネタはないものの何か書いてみようと思う。
数か月前、excelでちょっと複雑なソートをやってみた。
studies.hatenablog.com
今回は、これをperlでやってみよう。
#! /usr/bin/perl use 5.010; while (<>) { ($city, $pref) = split; $pref{$city} = $pref; $pref_priority{$pref} //= ++$count; $city_priority{$city} = ++$times{$pref}; } for (sort {$pref_priority{$pref{$a}} <=> $pref_priority{$pref{$b}} or $city_priority{$a} <=> $city_priority{$b}} keys(%pref)) { printf "%-15s%s\n", $_, $pref{$_}; }
市区町村から都道府県へのハッシュ、都道府県の優先度を表すハッシュ、同じ都道府県のとき市区町村の優先度を表すハッシュ、同じ都道府県が現れた回数を記録するハッシュの4つを用意する。
defined-or演算子を用いて、都道府県の優先度が設定されていない時（つまり一度だけ）優先度を設定する。
市区町村の優先度は、都道府県が現れた回数として設定する。
最後に、宇宙船演算子を用いてソートのルールを指定する。
複数のルールがあるときは、orでつなげばOK。
実行画面はこうなる。
$ cat city.txt 京都市 京都府 千代田区 東京都 高岡市 富山県 松本市 長野県 宮津市 京都府 川崎市 神奈川県 諏訪市 長野県 渋谷区 東京都 滑川市 富山県 新宿区 東京都 臼杵市 大分県 稚内市 北海道 氷見市 富山県 いわき市 福島県 長野市 長野県 横須賀市 神奈川県 宇治市 京都府 $ ./sort.pl city.txt 京都市 京都府 宮津市 京都府 宇治市 京都府 千代田区 東京都 渋谷区 東京都 新宿区 東京都 高岡市 富山県 滑川市 富山県 氷見市 富山県 松本市 長野県 諏訪市 長野県 長野市 長野県 川崎市 神奈川県 横須賀市 神奈川県 臼杵市 大分県 稚内市 北海道 いわき市 福島県
ありゃ、なんかズレた。
今回はちょっとおしゃれ（？）にハッシュを多用して書いてみた。
しかし、ちょっと調べたところによれば、
use 'stable';
などと書けば、perlでも安定ソートを使うこともできるようだ。
普通に1行ずつ配列に格納して、一気にバーンとソートしたほうがもっと短く（易しく）書けるだろう。
短いことは良いことだ（ほかの人に理解させるつもりがないのなら）
昨日本屋に行ってperlの本を買ってきた。
perlは文字列の処理が得意なプログラミング言語らしい。
Cみたいにコンパイルしたりせずに、シェルから直接起動することができるから便利そう。
最近はソースコードやスクリプトをいかに短く書くことができるか、ということを考えている。
if文もfor文も直感的でわかりやすいけど、長くなってしまいがちだ。
短く書けたらプロっぽい気がする。
たとえば、今までうるう年を判定する関数は、こんな感じに書いていた。
bool isLeapYear(int year) { if (year%4) { return false; } else if (year%100) { return true; } else if (year%400) { return false; } else { return true; } }
この関数を翻訳すると、こうなる。
4で割り切れないなら、うるう年でない。
4で割り切れて、100で割り切れないなら、うるう年だ。
4で割り切れて、100でも割り切れて、400で割り切れないなら、うるう年でない。
4で割り切れて、100でも割り切れて、400でも割り切れるなら、うるう年だ。
うーむ、わかりやすい。
けど、まあそこそこ長い。
そこで、これを一行で済ませてしまう書き方を考えるわけである。
次のようになる。
bool isLeapYear(int year) { return !( year%400 && !(year%100) || year%4 ); }
または、同じことだけれども、
bool isLeapYear(int year) { return !(year%4) && ( year%100 || !(year%400) ); }
とも書ける（ドモルガンの法則で、この二つは双対である。）
コンピュータの処理的にif文バージョンと同じで効率がいいのは、後者のほうだろう。
（4で割り切れない場合は、&&以降の条件式を参照しない。マイナーケースから検討していく前者に比べて、メジャーケースから検討する後者のほうが理にかなっている）。
短くなった。
でも、もはや簡単には何をやっているかわからんだろう。
しかし、その暗号っぽさが面白くて愉快である。
