読者です 読者をやめる 読者になる 読者になる

studies

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

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())

studies.hatenablog.com

もちろん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のソートに安定性を保証することができるという話を書いた。

studies.hatenablog.com


そこで今回は、これを使って先日のソースを改良してみる。

#! /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++の勉強はそこそこに、シェルスクリプト正規表現なんかの勉強をしている。

というのも業務でコードを触る機会が減ってしまったのに加え、私の身の回りには、これらの技術を使うことで自動化できる業務があふれているからだ。

 

自動化できる業務が自動化されていないのはそういう技術を周りの人が持っていないからではない。

これらの業務が手作業でもできてしまう、しかも一回やる分には手作業のほうが早いからだろう。

 

たとえば、システムのステータスが書きだされた複数のテキストファイルから必要な情報を抜き出すという作業が与えられる。

ステータスが書かれたファイルはよく構造化されているから、grepsed, 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()関数で測った時間には、違いが出ることになる。

実際、二つの環境(WindowsUbuntu)で次のコードを書いて動かしてみたら、だいぶ違う挙動をすることが観察できた。

#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()関数での計測時間が著しく小さな数字になった。

面白い。

独習C++ 第2章

三連休があっという間である。
日がな惰眠を貪った三連休であった。

さて、今日はC++の勉強をした。

Amazon CAPTCHA

この分厚い本で勉強している。

問題数が多い。
すべての問題を解こうとしたら、時間がいくらあっても足りないだろう。

第2章の「前章の理解度チェック」からやってみた。

問題3の解答がコンパイラ依存になっている。
つまり、intもlongも32ビット前提の書き方をしている。

コンパイラ依存でないソースを書いてみたので、掲載してみる。

#include <iostream>
#include <climits>
using namespace std;

int rotate(int);
long rotate(long);

int main()
{
    int a = 0x00000008;
    long b = 0x80000000;
    cout << rotate(a) << endl;
    cout << rotate(b) << endl;
    
    return 0;
}

int rotate(int x)
{
    if ( x >> ( CHAR_BIT * sizeof(int) -1 ) ) {
        return 1 + (x << 1);
    } else {
        return x << 1;
    }
}

long rotate(long x)
{
    if ( x >> ( CHAR_BIT * sizeof(long) -1 ) ) {
        return 1 + (x << 1);
    } else {
        return x << 1;
    }
}


ポイントは、2点ある。

一つ目は、climitsをincludeして、CHAR_BITマクロを参照していること。
これによって、1バイトが8ビットでない環境にも対応できる。
これは、次のサイトを参考にした。
www.kijineko.co.jp


二つ目は、sizeof演算子を使って、intやlongのバイト数を求めていること。
これによって、たとえばintが4バイトでも2バイトでも問題なく、思った通りに動いてくれる。