Search on the blog

2014年3月31日月曜日

人口密度を図にしてみた

東京都豊島区 

福岡県福岡市

富山県富山市

奈良県上北山村

2014年3月27日木曜日

EclipseでJavaを書くときに設定しておくべきもの

 Eclipseでワークスペース/プロジェクトを作成したときに、設定すべきものをメモしておく。主にフォントの設定、FindBugsの設定、Checkstyleの設定など。

1. 行数を表示
Window> Preferences> General> Editors> Text Editors
Show line numbersにチェック

2. 空白文字を表示
Window> Preferences> General> Editors> Text Editors
Show whitespace charactersにチェック

3. 等幅フォントにする(windowsなら不要)
Window> Preferences> General> Appearance> Colors and Fonts >Java >Java Editor Text Font
DejaVu Sans Monoを選択

4. FindBugsの設定
Window> Preferences> Java> FindBugs
Minimum rank to report: を20に設定

5. FindBugsの自動実行
プロジェクト右クリック> Properties> FindBugs
FindBugsを自動的に実行をチェック

6. Checkstyleのアクティベート
プロジェクト右クリック> Checkstyle
Activate Checkstyle

7. Checkstyleの設定
Window> Preferences> Checkstyle
Sun Checksをコピーしてチェック設定ファイルを作成する。作成したものをデフォルトに設定。必要に応じて、不要な(too muchな)チェックを外す。

Class Design - Design For Extension (これを外さないと、拡張されていないメソッドには全部finalかabstractをつけろと言われる)
Miscellaneous - Final Parameters (これを外さないと、変更されないパラメータには全部finalつけろと言われる)
Javadoc Comments - Package Javadoc (これを外さないと、package-info.javaを書けと言われる)

C++11のスマートポインタを使ってみる

 C++11から使えるようになったスマートポインタを使って遊んでみました。なかなか面白いです。
  1. unique_ptr
  2. shared_ptr
  3. weak_ptr
の順で使い方を見ていきます。

unique_ptr
unique_ptrは自身がスコープアウトした時点で、管理しているオブジェクトをdeleteします。
 その名のとおり、あるオブジェクトを管理するunique_ptrは一意でなければいけません。よってunique_ptr間でオブジェクトの共有は出来ません。

とりあえず使ってみます。
#include <iostream>
#include <memory>

using namespace std;

struct hoge {
    hoge() {
        cout << "a hoge instance is constructed" << endl;
    }

    ~hoge() {
        cout << "a hoge instance is destructed" << endl;
    }

    void doSomething() {
        cout << "a hoge instance does something" << endl;
    }
};

int main(int argc, char **argv) {

    cout << "start block" << endl;
    {
        unique_ptr<hoge> ptr(new hoge());
        ptr->doSomething();
    }
    cout << "end block" << endl;

    return 0;
}
実行すると、

start block
a hoge instance is constructed
a hoge instance does something
a hoge instance is destructed
end block

のようになります。hogeを管理しているunique_ptrがスコープアウトした時点でhogeのデストラクタが自動で呼ばれているのが分かります。

 複数のunique_ptrでオブジェクトを共有することは出来ないので、以下のようなソースはコンパイルエラーになります。
int main(int argc, char **argv) {
    unique_ptr<hoge> ptr(new hoge());
    unique_ptr<hoge> qtr = ptr;
    return 0;
}

shared_ptr
次にshared_ptrを使ってみます。shared_ptrはオブジェクトを共有できます。管理しているオブジェクトの参照カウントが0になった時点でオブジェクトを自動消去します。

先ほどと同じhogeを使って実験してみます。
int main(int argc, char **argv) {

    shared_ptr<hoge> ptr;

    cout << "start block" << endl;
    {
        shared_ptr<hoge> qtr(new hoge());
        ptr = qtr;
        qtr->doSomething();
    }
    cout << "end block" << endl;

    return 0;
}
実行結果は以下のようになります。

start block
a hoge instance is constructed
a hoge instance does something
end block
a hoge instance is destructed

 hogeはブロック内でnewされます。qtrがhogeを所有しているため、hogeの参照カウントは1です。
その後、ptr = qtrで、ptrもhogeを参照することになります。ここでhogeの参照カウントは2になります。
ブロックを抜けると、qtrがスコープアウトするため、参照カウントが1になります。
最後に、main関数を抜ける時点でptrがスコープアウトし、参照カウントが0になります。
参照カウントが0になった時点で、hogeがdeleteされます。

 shared_ptrの参照カウントは、shared_ptr::use_count()メソッドで取得できます。

weak_ptr
最後にweak_ptrです。Javaの弱参照と似たような感じです。weak_ptrはオブジェクトを共有できますが、weak_ptrによる参照は参照カウントには影響しません。よって、weak_ptrが参照しているオブジェクトが既に削除されてしまっているという場合もあります。

int main(int argc, char **argv) {

    weak_ptr<hoge> ptr;

    cout << "start block" << endl;
    {
        shared_ptr<hoge> qtr(new hoge());
        ptr = qtr;
        cout << ptr.use_count() << endl;
        qtr->doSomething();
    }
    cout << "end block" << endl;

    return 0;
}
を実行すると、

start block
a hoge instance is constructed
1
a hoge instance does something
a hoge instance is destructed
end block

と表示されます。weak_ptrが参照カウンタに関与しないことが分かります。
また、weak_ptrによる参照が存在しても参照カウンタが0になった時点でオブジェクトがdeleteされていることが分かります。

2014年3月24日月曜日

C++でポリモーフィズム

C++でポリモーフィズムを行う場合は、virtualをつけるらしい。

virtualを付けた関数を”仮想関数”と呼ぶ。
仮想関数にすると、親クラス型の参照を使って子クラスのメソッドにアクセスした場合、子クラスで定義されたメソッドが実行される。

virtualを付けなかった場合は、親クラス型の参照からアクセスすると、親クラス側のメソッドが実行される。もちろんvirtualを付けなくてもメソッドのオーバーライド自体は出来て、子クラス型の参照からメソッドを呼び出せばオーバーライドしたメソッドが実行される。

以下の例を見た方が分かりやすい。
#include <iostream>

using namespace std;

struct animal {
    virtual void greet() {
        cout << "Hello, I'm an animal." << endl;
    }
};

struct dog : animal {
    void greet() {
        cout << "Hello, I'm a dog." << endl;
    }
};

struct cat : animal {
    void greet() {
        cout << "Hello, I'm a cat." << endl;
    }
};

int main(int argc, char **argv) {
    animal *p = NULL;

    p = new dog;
    p->greet();
    delete p;

    p = new cat;
    p->greet();
    delete p;

    return 0;
}
上のコードを実行すると、
Hello, I'm a dog.
Hello, I'm a cat.
のようになる。

greetメソッドにvirtualを付けない場合は、
Hello, I'm an animal.
Hello, I'm an animal.
となってしまう。

2014年3月17日月曜日

Boostの多倍長整数ライブラリ

 Boostの多倍長整数ライブラリを使ってみました。これでCode JamとかHacker Cupで多倍長出てもC++で行けそうです。

準備
自宅のマシンはLinuxなので最初からBoostが入っていましたが、versionが少し古くて目的の機能は使えませんでした。

ということでインストールから。

1. 最新版のBoostを公式ページからダウンロードします。

2. ダウンロードしたら適当なディレクトリに展開します。

3. 展開したディレクトリに移動して以下のコマンドを実行します。
kenjih$ ./bootstrap.sh --prefix=/home/kenjih/local
kenjih$ ./b2 install 

--prefixで指定しているのは、インストール先のディレクトリです。Linuxのディストリビューションに最初から入っているBoostの上にインストールすると、環境が壊れてしまう可能性があるため、ユーザのlocalディレクトリなどにインストールするのがよいと思います。

使ってみる
まずは、簡単な掛け算から入ってみます。入力された2つの整数の積を計算してみます。
#include <iostream>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;

typedef boost::multiprecision::cpp_int bigint;

int main() {
    bigint a, b;

    cin >> a >> b;
    cout << a * b << endl;

    return 0;
}
コンパイルするときは、以下のようにheaderの検索パスを指定します。
kenjih$ g++ -o test -I ~/local/include test.cpp

次に、フィボナッチ数列でも計算してみますか。フィボナッチ数列の最初の100項を表示します。

#include <iostream>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;

typedef boost::multiprecision::cpp_int bigint;

int main() {
    bigint x(0), y(1);

    for (int i = 0; i < 100; i++) {
        cout << x << endl;
        y = y+x;
        x = y-x;
    }

    return 0;
}

 最後に、ビット演算。入力された数を2進数で解釈して再構築できるか確認しています。
#include <iostream>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;

typedef boost::multiprecision::cpp_int bigint;

int main() {
    bigint x, y, b(1);
    cin >> x;

    while (x > 0) {
        if (x & 1)
            y |= b;
        x >>= 1;
        b <<= 1;
    }
    
    cout << y << endl;

    return 0;
}

2014年3月16日日曜日

静的ライブラリと動的ライブラリを作る

まえがき
gccで静的ライブラリと動的ライブラリを作ってみました。静的ライブラリは前回のポストにも載せましたが、対比が分かりやすいように再掲します。

静的ライブラリをつくる
静的ライブラリは、libxxx.aというファイルです。拡張子のaはarchiveの略です。
以下では、加減乗除を行う関数が定義されたadd.o、sub.o、mul.o、div.oをarchiveしてlibhoge.aというファイルを作成します。

kenjih$ gcc -c add.c
kenjih$ gcc -c sub.c
kenjih$ gcc -c mul.c
kenjih$ gcc -c div.c
kenjih$ ar -q -v libhoge.a *.o
のようにして静的ライブラリを作成します。

main.cからlibhoge.aの機能を使用する場合は、以下のようにコンパイルします。
kenjih$ gcc -o main main.c -L. -lhoge
-Lはライブラリの検索パスの指定です。libhoge.aがカレントディレクトリにある場合は、-L.のようにします。

動的ライブラリをつくる
動的ライブラリは、libxxx.soというファイルです。拡張子のsoはshared objectの略です。 静的ライブラリのときと同様に加減乗除を関数を定義したオブジェクトファイルをまとめてライブラリにします。
kenjih$ gcc -c -fPIC add.c
kenjih$ gcc -c -fPIC sub.c
kenjih$ gcc -c -fPIC mul.c
kenjih$ gcc -c -fPIC div.c
kenjih$ gcc *.o -shared -o libhoge.so
のようにして動的ライブラリを作成することができます。

コンパイルするときは以下のようにします。
kenjih$ gcc -o main main.c -L. -lhoge
コンパイルは静的ライブラリにリンクするときと同様です。gccのリンカは-lxxxと指定されたとき、まずlibxxx.soを探してあればそれをリンクします。libxxx.soが無ければlibxxx.aを探してそれをリンクします。

動的ライブラリはランタイム時にリンクされます。実行ファイルがどの動的ライブラリに依存しているかはlddコマンドで確認できます。
kenjih$ ldd main
	linux-gate.so.1 =>  (0xb77af000)
	libhoge.so => not found
	libc.so.6 => /lib/i386-linux-gnu/libc.so.6 (0xb75ea000)
	/lib/ld-linux.so.2 (0xb77b0000)
libhoge.soがnot foundとなっています。これはlibhoge.soがデフォルトのライブラリ検索パス内に存在しないからです。libhoge.soを適切なパスに移動させてもいいですが、環境変数LD_LIBRARY_PATHに動的ライブラリのパスを指定することも出来ます。

export LD_LIBRARY_PATH=$(pwd)
を実行して、libhoge.soファイルがあるカレントディレクトリをLD_LIBRARY_PATHに指定します。

再度lddコマンドを実行してみます。
kenjih$ ldd main
	linux-gate.so.1 =>  (0xb771c000)
	libhoge.so => /home/kenjih/programming/cpp/sample2/dynamic/libhoge.so (0xb7717000)
	libc.so.6 => /lib/i386-linux-gnu/libc.so.6 (0xb7554000)
	/lib/ld-linux.so.2 (0xb771d000)
で作成した動的ライブラリの場所が認識されたことが分かります。./mainを実行すると、libhoge.soが動的にリンクされます。

2014年3月15日土曜日

-lmとは何か

 gccでコンパイルするときにつける-lmについて調べてみました。
libm.aというライブラリをリンクしているということは知ってました(※1)が、.aファイルが何者なのか?どうやって作るのか?は知らなかったので、いい勉強になりました。
 ついでに、.aファイルを自分で作ってみました。

-lmとは?
まず、-lオプションについて。
-lxxxというオプションをつけると、リンカがlibxxx.aというファイルを探してリンクしてくれます(※2)。

どこを探すかというと、デフォルトで設定されているパスを探します。

$ gcc --print-search-dirs

というコマンドを実行すると、gccがプログラム/ライブラリを検索するパスの一覧が表示されます。
デフォルトの検索パスに含まれていない場所も検索するようにしたい場合は、-Lオプションを使ってパスを指定することが出来ます。

.aファイルの拡張子aは「archive」の意味です。
.aファイルはarコマンドで作成することが出来ます。また、arコマンドを使うと、archiveの中身を確認することも出来ます。

例えば、-lmでリンクされるlibm.aの中身を確認すると、

$ ar -t `locate libm.a | head -n 1`
k_standard.o
s_lib_version.o
s_matherr.o
s_signgam.o
.....

のようにオブジェクトファイルが含まれていることが分かります。
オブジェクトファイルが大量にarchiveされていますが、実際にリンクされるのはリンク先で使用されるオブジェクトファイルのみです。

ライブラリには静的ライブラリと動的ライブラリが存在します。
*.aファイルは静的ライブラリ。動的ライブラリは*.soというファイル名です。
リンカは、まず動的ライブラリ、次に静的ライブラリという順番でライブラリを検索します。
静的ファイルは実行ファイルの内部にリンクされます。これに対して、動的ライブラリはランタイムでリンクされます。

静的ライブラリを作る
以下の4つのオブジェクトファイルをarchiveすることにします。
  • add.o
  • sub.o
  • mul.o
  • div.o
それぞれのファイルには、int同士の加減乗除を行う関数を定義しておきます。

で、これらをarchiveします。
$ ar -q -v libhoge.a *.o
a - add.o
a - div.o
a - mul.o
a - sub.o

テスト用関数を書きます。
#include <stdio.h>

int main() {
    int a, b;
    a = 10;
    b = 2;

    printf("%d + %d = %d\n", a, b, add(a, b));
    printf("%d - %d = %d\n", a, b, sub(a, b));
    printf("%d * %d = %d\n", a, b, mul(a, b));
    printf("%d / %d = %d\n", a, b, div(a, b));

    return 0;
}
で、コンパイルします。
libhoge.aファイルはmain.cファイルと同じ階層に保存します。libhoge.aファイルのパスが検索されるように、-Lオプションで-L.と指定します。

$ gcc main.c -L. -lhoge -o test

正常に動作しました。

訂正
(※1) -lmでlibm.aがリンクされるというのは間違いでした。libm.soという動的ライブラリが存在するので、libm.soが動的にリンクされます。
(※2) これは間違いです。正しくは、「-lxxxというオプションをつけると、リンカはまずlibxxx.soというファイルを探してそれがあればリンクします。もし無ければ、libxxx.aというファイルを探してリンクします。」

2014年3月7日金曜日

UNIXコマンドメモ

 自分用のメモ書きです。

1. プロセスが使用しているポートを調べる
netstatを使う方法
$ sudo netstat -tanp | grep mysql
-t: TCPのみ
-a: listenしているソケットもしていないソケットも表示
-n: アドレスを数値で表示
-p: プロセス名を表示

lsofを使う方法
$ sudo lsof -c mysql -a -i -a -P
-c: プロセス名を指定
-a: 条件をANDでつなげる(デフォルトはOR結合)
-i: listenしているポートを表示
-P: ポート番号をポート名に変更(80->httpのように)しない

2. ポートを使用しているプロセスを調べる
$ sudo lsof -i:3306

3. ファイルを高速検索する
$ locate httpd.conf
locateはディスク上のファイルではなく、DBに格納されたファイルパス情報を検索している。 DBはupdatedbというコマンドで最新化できる。updatedbはcronに登録されている。

4. 素因数分解する
$ factor 123456789

5. 画像ファイルを表示する
$ display xxx.jpg

6. ファイルからベース名(拡張子を除いたもの)を取得する
$ basename test.cpp .cpp

7. インストールされたライブラリのメタ情報を取得する
$ pkg-config --cflags opencv
$ pkg-config --libs opencv

特定のライブラリに依存するソースコードをコンパイルするときに便利。
以下のようにバッククオート演算子と組み合わせて使う。
$ g++ -ggdb `pkg-config --cflags opencv` -o `basename opencvtest.cpp .cpp` opencvtest.cpp `pkg-config --libs opencv`

8. ファイル、URLをデフォルトのアプリケーションで開く
$ xdg-open sample.avi
$ xdg-open http://yahoo.co.jp
上の例では、それぞれビデオファイル、yahooのページをデフォルトのアプリケーションで開きます。

9. Linuxのバージョンを確認する
$ lsb_release -a

10. インストールされているパッケージのリストを取得する
$ dpkg -l
必要に応じて、パイプとgrepで絞り込みを行う。
$ dpkg -l | grep openssl

11. マシンが32bit/64bitのどちらで動作しているか調べる
CPUが64bitをサポートしているかどうかは以下のコマンドで分かる。
$ lscpu | grep op
CPU op-mode(s): 32-bit, 64-bit のように表示されれば、64bitのオペレーションモードをサポートしていることが分かる。

次に、OSが64bitかどうかは以下のコマンドで分かる。
$ uname -m  # uname -p でもOK.
x86_64のように表示されれば64bit。ix86のように表示されれば32bit。
64bit CPU上で64bit版OSが動作している場合に、マシンは64bit環境で動作していると言う。

2014年3月2日日曜日

tetrationとiterated logarithm


 tetrationとiterated logarithm。
それぞれ演算の種類です。見たことはありましたが、理解が曖昧だったので調べてみました。

tetrationとは?
na = 1 if n = 0
na = a^((n-1)a) if n > 0

で定義される演算です。

02 = 1
12 = 2^(02) = 2
22 = 2^(12) = 4
32 = 2^(22) = 16
42 = 2^(32) = 65536
52 = 2^(42) = 2^65536
......

のようになり、ものすごい早さで増加する関数です。

a * n = a + a + a + a + ....というように掛け算は足し算に分解できます。
同様に、
a ^ n = a * a * a * a * ... というようにべき乗は掛け算に分解できます。

tetrationの場合は、
na = a^(a^(a^(a^....)))というようにべき乗に分解できます。 例えば42 = 2^(2^(2^2)) = 2^(2^4) = 2 ^ 16 = 65536というふうになります。

iterated logarithmとは?
iterated logarithmとは以下のように定義される関数です。

log*(n) = 0 if n <= 1
log*(n) = 1 + log*(log(n)) if n > 1

log*()は一般に"log star"と読みます。

例えば底を2とすると、
log*(1) = 0
log*(2) = 1 + log*(log(2)) = 1 + log*(1) = 1
log*(4) = 1+ log*(log(4)) = 1 + log*(2) = 2
log*(16) = 1 + log*(log(16)) = 1 + log*(4) = 3
log*(65536) = 1 + log*(log(65536)) = 1 + log*(16) = 4
log*(2^65536) = 1 + log*(log(2^65536)) = 1 + log*(65536) = 5

となります。ちょうどtetrationの逆関数のような関係(※)にあり、ものすごく増加の遅い関数です。

※厳密にはtetrationの逆関数はsuper-logarithmです。
正の実数nに対して、super-logarithmとiterated logarithmには
log*n = ceil(slog(n))
という関係が成り立ちます。