ワンライナーでちょっと複雑なソート
早く目が覚めてしまった。
これは午後眠くなるぞー。
最後の仕上げ？として、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で割り切れない場合は、&&以降の条件式を参照しない。マイナーケースから検討していく前者に比べて、メジャーケースから検討する後者のほうが理にかなっている）。
短くなった。
でも、もはや簡単には何をやっているかわからんだろう。
しかし、その暗号っぽさが面白くて愉快である。
久方の雨も降らぬか雨障み
久しぶりの更新である。
最近は少しずつ残業も増えてきた。
世の中のブロガーは、どうやってブログを書く時間やブログのネタを見つける時間を捻出しているのだろう。
最近私はC++の勉強はそこそこに、シェルスクリプトや正規表現なんかの勉強をしている。
というのも業務でコードを触る機会が減ってしまったのに加え、私の身の回りには、これらの技術を使うことで自動化できる業務があふれているからだ。
自動化できる業務が自動化されていないのはそういう技術を周りの人が持っていないからではない。
これらの業務が手作業でもできてしまう、しかも一回やる分には手作業のほうが早いからだろう。
たとえば、システムのステータスが書きだされた複数のテキストファイルから必要な情報を抜き出すという作業が与えられる。
ステータスが書かれたファイルはよく構造化されているから、grepやsed, awkといったツールがとてもよく活躍する。
しかし、与えられるファイルはせいぜい5個や6個であり、時間を最優先する現場では多くの場合、考える時間を惜しんで、先に手が動いてしまう。
つまり、テキストエディタを開き、検索をかけ、あるいは自分でスクロールして、必要な個所を見つけ、別のファイルにコピーアンドペーストする。
一回きりの作業ならこれでもちろん良いのである。
途中で単調作業に飽きるのを我慢しさえすれば、実際「早い」のだから。
だが二回目以降の作業があるなら、少し考える時間をとってシェルスクリプトを書いたほうがいいことが多い。
二回目以降の作業時間はほぼゼロだ。
難しいのは、同じ作業がまた現れるか、という見極めである。
人間はミスをするし、作業のやり直しを命じられるかもしれない。
あるいは、実は一か月後に同じ作業をする必要が出るのかもしれない。
そこらへんの見極めが不適切だと、無駄な単調作業に何時間も時間をかけてしまったり、あるいは逆に二度と使わないシェルスクリプトを書いてしまうことになる。
だらだらとよくわからないことを書いたけれど、一回の作業でもサッとスクリプトを書けたり、あるいはワンライナーで全部こなしてしまえるのなら、そうしてしまうほうがずっといい。判断する時間も節約できる。
そんなスーパープログラマになりたい（小並）。
時間を扱うライブラリ関数
引き続き、独習C++をやっている。
練習問題で、時間を扱うことが多い。
今までC言語でも時間を扱ったことがほとんどなかった。
C++というよりCの標準ライブラリ関数の勉強みたいになっている。
ctime（C言語ならtime.h）をかんたんにまとめる。
time_t型
ctimeをincludeすると、time_t型という型を使うことになる。
time_t型というと恐ろしい感じがするが、数値型である。
ほとんどの場合はlong型をtypedefしているだけらしい。
慣れないうちはtime_t = longと思っていいだろう。
私の環境でもtime_tはlongのようだ。
time関数 time_t time(time_t*)
引数の実体に現在時刻をセットする。
同時に現在時刻（暦時間）を返却する。
値を返すところが二つあって不思議な感じがする。
time_t now = time(NULL)
としても、別にsegmentation faultになったりはしない。
自分が使うとしたら、たぶんこういう使い方をするだろう。
私の環境では1970年1月1日0時0分からの秒数が返却される。
たいていの場合はそんな風になっているから、
start = time(NULL); ; ; end = time(NULL); long passed_time = (long)end - start
という感じで、経過時間（秒単位）を求めることができる。
処理系依存の書き方になってしまうけど。
difftime関数 double difftime(time_t, time_t)
上の書き方を処理系依存から改良するためには、difftime関数を使う。
経過時間を秒単位で返してくれる。
ctime関数 char* ctime(time_t*)
引数を文字列に直して返却する。
clock関数 clock_t clock();
time関数が暦時間をtime_t型で返却するのに対して、clock関数は、プロセス開始からのCPU時間をclock_t型で返却する。
私の環境ではclock_t型もlong型であり、ミリ秒単位で返却される。
clock_t型を秒単位に直すために、CLOCKS_PER_SECマクロで割る必要がある。
この値が、私の環境では1000になっているというわけ。
これを使って、経過時間を求める場合は、
start = clock();
;
;
end = clock();
double passed_time =
(double)(end - start) / CLOCKS_PER_SEC;
とする。
time関数とclock関数の違い
同じように経過時間を測れるように見えるが、大きく違う。
返却する値が、time関数は暦時間であり、clock関数はプロセッサ時間である。
プロセッサ時間というのは、プロセスがCPUを占有した時間である。
つまり、OSのタスクスケジューリングによっては、見た目ではとても時間が経過している（暦時間は進んでいる）のに、プロセスへのCPU資源の割り当てが少なく、プロセッサ時間はほとんど消費していない、というようなことが起こりうる。
この場合、time()関数で測った時間とclock()関数で測った時間には、違いが出ることになる。
実際、二つの環境（WindowsとUbuntu）で次のコードを書いて動かしてみたら、だいぶ違う挙動をすることが観察できた。
#include <iostream> #include <ctime> using namespace std; int main() { // 何か入力してエンターキーを押すまでの時間を測る？ time_t start = time(NULL); clock_t clock_start = clock(); int a; cin >> a; time_t end = time(NULL); clock_t clock_end = clock(); double clock_passed_time = (double) (clock_end - clock_start) / CLOCKS_PER_SEC; double passed_time = difftime(end, start); cout << "time()関数での計測時間\t" << passed_time << endl; cout << "clock()関数での計測時間\t" << clock_passed_time << endl; return 0; }
Windowsではほぼ等しい値になったのに対し、Ubuntuではclock()関数での計測時間が著しく小さな数字になった。
面白い。
