2014年11月28日金曜日

プログラミング初心者が中級者になるために学ぶべき4つの開発ツール


プログラミングの生産性はプログラマによって大きく異なります。
生産性の差というのはアルゴリズムや言語の知識、才能など様々ありますが、その中で最も効率よく、素早く改善出来るのは開発ツールの習得でしょう

開発ツールは世の中に五万とあり、様々な用途に合わせて作られています。

それらのツールを習得しているということはプログラマとしての能力そのものと言えるでしょう。

そして、天才的なプログラマでも意外とツールを良く理解していないことがあります。彼らに対してアドバンテージを取れるという意味でも開発ツールを学ぶ価値は非常に大きいです。


ここでは個別のツールに限定するのではなく、広くどのようなツールを、どのように学ぶべきなのかを議論したいと思います。




1. IDE (統合開発環境)



ex. Eclipse, Visual Studio

多くのプロジェクトにおいて、IDEはプログラミングの殆どの時間、開いているものです。
これを良く理解しているということがプログラマにとって重要であることは間違いありません。

しかし、「IDEを習得する」とはどういうことでしょうか。
IDEの利便性を最大限に引き出すためには以下の2点を習得する必要があるでしょう。

1. ショートカットキーを覚える

IDEは思った以上に沢山のショートカットキーが存在します。
いちいちGUI上でクリックするのではなくショートカットを利用するだけで作業効率は一段と上がります。

ビルドやデバッグなどの非常に頻繁に使うショートカットはすぐに覚えますが、それほど頻繁ではないショートカットの場合、自分で意識して使うようにしないと覚えられないものです


2. ビルドプロセスを理解する

IDEを自在に操れる人というのはIDEがその内部で何をやっているのかを理解しているプログラマです。

多くのIDEはMakefileに相当するものを自動生成することでプロジェクトのビルドを自動化しています。

この自動生成されるMakefileに凡そどのような内容が書かれているのかを理解すると様々な自動化が可能になります

例えばIDEが行っているビルドをそのままスクリプトにまとめることでテストビルドを自動化することが出来ます。

 

2. テキストエディタ



ex. Vi, Vim, Emacs

テキストエディタはあらゆる場面で使う、プログラマ・エンジニアの根幹となる武器です。
プログラマにとって優良なテキストエディタを習得するということは、日本人にとって日本語を習得するということと同義です

テキストエディタの習得において最も大切なことはショートカットを覚えることです。そもそもテキストエディタを開く目的自体、あるコマンドを実行することである場合もあるでしょう。

ちなみにテキストエディタとしてはViかEmacsをおすすめします。
これらはコマンドライン上で使え、ショートカットが豊富であり、またシェアが大きいからです。

十中八九、一生使えるツールになるでしょう。



 

3. Git (バージョン管理ツール)



ex. Git, Subversion (ここではバージョン管理ツールとして)

時々Gitは不必要に複雑だ、という方がいます。

複雑かもしれませんが、不必要なものではありません。


そもそも、バージョン管理はいかなる種類のソフトウェアにおいても重要なものです。
個人で開発する場合でも、過去のコードというのは常に取っておくべきものであり、また開発の途中で「やっぱりPlan AじゃなくてPlan Bにしよう」という時にPlan Aに取りかかる前の状態にコードを戻すことが出来ます。

これを手動でやろうとして失敗した方は多いと思います。

バージョン管理を丁寧に行うだけで作業の効率は格段に上がります

Gitとは全てのプログラマが習得すべきツールです。


また、Gitは絶対にコマンドライン上で扱うべきです
確かにGUIも有用ですが、GUIはそのままでは自動化出来ないという致命的な欠点を持っています。

Gitのcommitやpushというのはめんどうな作業であるので、だからこそそれらを自動化することでそれらの作業を単純化することが出来るのです。



 

4. スクリプト言語



ex. Perl, Ruby, Python

これまでのツール紹介でも繰り返し自動化と言ってきました。

自動化というのは開発ツールの本質の一つでしょう。

そして、どれだけ自動化出来るかというのは、プログラマの能力のかなり精確なベンチマークであるでしょう

それらの自動化を担当するのがスクリプト言語です。

スクリプト言語の代表はPerl, Ruby, Pythonでしょう。

スクリプト言語は本質的に「上から順に実行する」というものなので、自動化というものととても相性がいいのです。また、そもそもスクリプト言語は書くのが簡単であるということもあります。






これらの開発ツールを習得し、高い生産性と知識を得ればいち早く初級者から中級者になれるでしょう。


そもそもプログラミングとは効率向上・自動化の為のものです。

それを、プログラミングという活動自体に適用するということが中級者以上に求められる技能とも言えましょう。

2014年11月25日火曜日

Cスタンダードライブラリにおけるsin関数の実装

Cスタンダードライブラリにおける関数は様々な驚くべき実装が存在します。
rand()関数はどのようにして乱数を作っているのでしょうか。sin()関数はどのようにしてサインを計算しているのでしょうか。

ここではsin()の実装について考えてみましょう。



・sin関数の計算方法


そもそもsinを求める方法とは何があるでしょうか。


まず思いつくのはテイラー展開でしょうか。

テイラー展開をすることでsinは以下の式で表せます。

http://upload.wikimedia.org/math/6/c/d/6cd3737be7a2653367595e4365ba58f9.png

無限級数なのでどこかで丸めなければなりません。double型の桁数に合うように次数を決められれば良いのですが、その場合次数はxの値に依存することになります。
つまりxが大きいほど収束が遅くなるため、展開次数を大きくとる必要があります



もう一つ、sinを求める方法は三角比表でしょう。
例えば以上の三角比表が与えられた場合、
sin2°はsin0°とsin5°の線形補間で計算できます

しかし、上の表を見れば分かるように、5°刻みだと非常に粗い補間になってしまいます。
double型に使うにはもっと大きな表が必要になるでしょう。ただしそうすると、より多くのメモリを要求することになります。

また、線形補間ではなく二次補間をすることでより精度をあげることが出来るでしょう。しかしこの場合は計算時間が大きくなります。



さて、いずれの方法にしても精度と計算資源(メモリ・時間)のトレードオフの関係があると言えます。



sinの実装


では、実際の実装はどのようにしてsinを計算しているのでしょうか。

ここではIBM Libraryの実装を見てみましょう。
この実装はsinの真の値に最も近いdoubleの値を返します。



/*
 * IBM Accurate Mathematical Library
 * written by International Business Machines Corp.
 * Copyright (C) 2001-2014 Free Software Foundation, Inc.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU  Lesser General Public License
 * along with this program; if not, see <http://www.gnu.org/licenses/>.
 */

//..中略..//

double
SECTION
__sin (double x)
{
  double xx, res, t, cor, y, s, c, sn, ssn, cs, ccs, xn, a, da, db, eps, xn1,
    xn2;
  mynumber u, v;
  int4 k, m, n;
  double retval = 0;
  SET_RESTORE_ROUND_53BIT (FE_TONEAREST);
  u.x = x;
  m = u.i[HIGH_HALF];
  k = 0x7fffffff & m;           /* no sign           */
  if (k < 0x3e500000)           /* if x->0 =>sin(x)=x */
    retval = x;
 /*---------------------------- 2^-26 < |x|< 0.25 ----------------------*/
  else if (k < 0x3fd00000)
    {
      xx = x * x;
      /* Taylor series.  */
      t = POLYNOMIAL (xx) * (xx * x);
      res = x + t;
      cor = (x - res) + t;
      retval = (res == res + 1.07 * cor) ? res : slow (x);
    }                           /*  else  if (k < 0x3fd00000)    */
/*---------------------------- 0.25<|x|< 0.855469---------------------- */
  else if (k < 0x3feb6000)
    {
      u.x = (m > 0) ? big + x : big - x;
      y = (m > 0) ? x - (u.x - big) : x + (u.x - big);
      xx = y * y;
      s = y + y * xx * (sn3 + xx * sn5);
      c = xx * (cs2 + xx * (cs4 + xx * cs6));
      SINCOS_TABLE_LOOKUP (u, sn, ssn, cs, ccs);
      if (m <= 0)
        {
          sn = -sn;
          ssn = -ssn;
        }
      cor = (ssn + s * ccs - sn * c) + cs * s;
      res = sn + cor;
      cor = (sn - res) + cor;
      retval = (res == res + 1.096 * cor) ? res : slow1 (x);
    }                           /*   else  if (k < 0x3feb6000)    */
/*----------------------- 0.855469  <|x|<2.426265  ----------------------*/
  else if (k < 0x400368fd)
    {

 //..後略..//


sourceware.orgで全コードを見ることが出来ます

まず面白い最適化として、xの大きさに応じて場合分けをしていることがあげられます。

xが小さい場合はテイラー展開を、45°程度の場合は三角比表を、などなどそれぞれの場合に異なる処理をしていることが分かります。

xが小さい場合はテイラー展開が非常に早く収束するのでテイラー展開を採用するなど、非常に高い水準でのトレードオフが見られます。


Cという言語はこのような極限の最適化を重ねて書かれた言語です。
坐臥して最速という訳ではないということでしょう。




2014年11月17日月曜日

Unixテキスト処理コマンド集【cat, head, tail, grep, sort, join, awk】

テキスト形式のデータ処理に便利なUnixコマンドを紹介します。
Unixコマンドは無数にあるのですべてをカバーすることは出来ません。

ここではお手軽に一行で書けるコマンドを中心に扱います。多くの「ちょっとした処理」はこれらの組み合わせで行うことが出来ます。


cat

cat <オプション> <ファイル>

全文を出力する。いわずもがななコマンド。
元々ファイルをつなげる(concatenate)為に実装されたコマンドですが、主に小さいファイルのダンプの為に使われています。
有用なオプションとしては-n: 行番号を出力するというものがあります。これを使うとコンパイルエラーの出た箇所の確認などに便利です。

cat run.sh -n
     1    #!/bin/sh
     2   
     3   
     4    # arg1 = time
     5    #
     6    #
     7   
     8    cd $PBS_O_WORKDIR
     9    ./tiles$time $algname $PBS_ARRAYID $thread_number $param1 $param2 $param3 < $problem_type
    10   
ちなみにcatの語源はconcatenate(つなげる)の略形です。


head

head <オプション> <ファイル>

ファイルの先頭の10行を出力する。大きなデータファイルを確認する場合や、ファイルヘッダーのみ確認する場合に便利です。

オプション-nで任意の行数を出力することが出来ます。
例えば
head  -n 20 astar.dat
ならば先頭20行が出力されます。
head -n -20 astar.dat
とすると最後の20行以外のすべての行を出力します。
ただしheadと続くtailはUnixのディストリビューションによって若干異なるインターフェイスを持っています。中身は同じなので大きな違いはありませんが、manページを見ておく必要はあると思います。

ちなみにheadとtailで行番号を出力したい場合は
cat astar.dat -n | head -n -20
のようにすれば出来ます。この場合の行番号は元のファイルにおける行番号になります。


tail

tail <オプション> <ファイル>
ファイルの末尾の10行を出力する。headと相似形であるので説明はheadを見てください。


grep

grep [オプション] パターン [ファイル...]
grep [オプション] [-e パターン | -f ファイル] [ファイル...]
パーサとして優秀なコマンド。特にログから必要なデータをマイニングする場合によく使われます。
例えば、
grep cron /var/log/syslog
とおくとファイル/var/log/syslogの中で文字列"cron"を含む行を出力します。cronジョブのデバッグをする場合はこれを読むと原因がすぐに分かります。
このコマンドを熟知していれば「ログが多すぎて必要なデータが分からなくなってしまった」ということはありません。

オプションやトリックは様々あるのですべてを網羅することは出来ませんがいくつか基本のものを紹介します。


-c, --count
通常出力の代わりにパターンに一致した行が何行あったかを出力する。
-l, --files-with-matches
通常出力の代わりにパターンに一致した行のあるファイルの名前を出力する。

大規模なデータを扱う場合はgrepの通常出力が大きくなりすぎて扱いにくくなってしまうことがありあます。大きな詳細を扱うのではなく、より大きな傾向を見る場合に使いやすいオプションです。木ではなく森を見るためのコマンドといえるでしょう。

語源はテキストエディタedのGlobal Regular Expression Printから。


sort

sort [OPTION]... [FILE]...
ファイルの行をソートする。デフォルトだと先頭のフィールドに基づいてソートされる。
データは順番が重要になることがあります。例えばgnupotは一行ずつ読み込んで処理するシステムの一つです。plot with linesとするとデータ入力順に線を引いていきます。

デフォルトだと入力文字列を文字列としてみなしてソートする。どういうことかというと、以下のtest.txtをソートすると10が2よりも前にくるということです。
$ cat test.txt
0 zero
1 one
2 two
10 ten
 これをsortすると、
$ sort test.txt
0 zero
10 ten
1 one
2 two
2どころか1よりも手前にきてしまいます。フィールドを数字としてみなしてソートする為には-nオプションをつける必要があります。
$ sort sort.txt -n
0 zero
1 one
2 two
10 ten

join

join [OPTION]... FILE1 FILE2
二つのファイルの内部結合(inner join)を出力する。
比較データなどを1ファイルにまとめる場合などに便利です。
-aコマンドでouter joinにすることが出来る。

結合フィールドはソートされている必要があるので、前述のsortを使うことになります。sortされていない形を保つ必要がある場合はcat -nで行番号を加えることで便宜的なイテレーション番号をつけ、それに基づいてソートをするということが出来ます。


awk

awkは一行でテキスト処理を行う軽快なコマンドであると同時に表現力豊かなプログラミング言語でもあります。awkのスクリプトを書けばこれまで述べてきたコマンドをawkで実装することも出来ます。しかしながらここでは一行でかける簡単な処理に絞って説明をします。詳しい言語実装を知りたい方は下記リンクをご参照下さい。

awkの基本骨子は

1. データファイルを一行読み込む
2. パターンマッチングを行う
3. パターンにマッチした場合に処理を行う

です。例えば
awk '/error/{print $1, $2}'
とすれば"error"の文字列を含む行の1番目、2番目の語を出力するという処理になります。

パターンマッチングの部分はgrepに似ていますが、awkの方がより深入りをして細かい場合分けや出力の指定をすることが出来ます。

データのフォーマットを変えたり、複数データから平均を計算したり、gnuplotに渡すデータを作成したり、shell scriptの中で活躍できるコマンドです。 結構しっかりとした言語なので詳解な説明は下記リンクに譲ります。

*awk参考リンク

The GNU Awk User's Guide
フルドキュメント。非常に詳解なので困ったらこれを見ればいいでしょう。

AWK入門(ドットインストール)
awkの入門の為ならこちらをお勧めします。awkのしっかりとした言語であるという側面と、簡単に記述できるという側面の両方を見ることが出来ます。


2014年11月4日火曜日

Torqueサーバーを1から立ち上げる為の7ステップ

Torqueサーバーを立ち上げるステップをまとめました。

一つ一つの要素技術の説明は良くまとまっている記事がたくさんあるのでそちらに譲り、この記事では全体の流れを説明することを目的とします

Steps

1. 計算機にUbuntuをインストールする
2. ノード間のネットワークを構築する
3. 必要なパッケージをインストールする
4. OpenSSHサーバーを立ち上げる
5. torqueの設定をする
6. NFSの設定をする
7. メールの設定をする

適宜済んでいる設定をスキップして読んでください。



1. 計算機にUbuntuをインストールする


まず、全ての計算機に同じバージョンのUbuntuを入れる。
特に問題が起こったということは聞かないが、OSレベルの実装を多く含むことを行うことになるので念のため同じバージョンを使うべきだろう。またジョブを実行する環境が均一である方が望ましいだろう。
また、ここではUbuntuを例に説明しているが他のDebian系のOSでも同様に設定できるはず。


2. ノード間のネットワークを構築する


ヘッドノードとスレイブノードで必要なものが異なる
ヘッドノードとは、Torqueのジョブスケジュリングや、他のノードの状態を管理するユニークなノードである。スレイブノードは実際にジョブを実行するノードである。
ヘッドノードはハブとなる計算機だが、実験自体はスレイブノードで行われる為ヘッドにはそこまでのスペックは要求されない。ただしヘッドが落ちるとシステム全体が止まってしまうので頑強なものが良い。あるいは、ヘッドノードでコンパイルなどのメモリを食う作業を禁止にするべきだろう。

2-1. 物理層のネットワークを構築する

OpenMPIなどでノード間の通信が重要である場合を除いて、特に工夫をする必要はないだろう。
スイッチングハブを購入し、LANケーブルでヘッドとノードをつなげる。2014年現在大方のLANケーブルは1Gbpsである。ので、1Gbpsよりも遅いハブを使うと重大なボトルネックになってしまう。今は1Gbpsに対応したスイッチングハブも安く購入できる。何かと通信は行うので1Gbpsのものを買った方が良いだろう。

2-2. Ubuntu上でネットワークを設定する

Ubuntuでのネットワーク設定はGUIからもCLIからも可能であるが、クラスタの設定をいちいちGUIからやるのは面倒である。CLIで同時に設定できた方がバグも少ないのでCLIをおすすめする。
こちらのUbuntu PCをルータ代わりにして、新しくLANを構築してみるという記事が非常に丁寧にかかれているのでHow Toはこちらに任せたい。ただし、ここではDHCPではなく固定IPアドレスを使う。
Torqueの場合のIPアドレスのコツは0, 1, 2と始めるのではなく、100, 101, 102と始めるということで、この方がのちのち拡張しやすい。


3. 必要なパッケージをインストールする

3-1. Torqueの為のパッケージをインストールする

ヘッドとスレイブで必要とするパッケージが異なる。

ヘッドノード
sudo apt-get install openssh-server
sudo apt-get install torque-server
sudo apt-get install torque-scheduler
sudo apt-get install wakeonlan
sudo apt-get install nfs-kernel-serversudo apt-get install mail-utils
sudo apt-get install postfix

スレイブノード
sudo apt-get install openssh-server
sudo apt-get install torque-mom
sudo apt-get install torque-client
sudo apt-get install nfs-common
さて、パッケージの説明をしたい。

openssh-server
sshサーバー。sshで入れなければ何も出来ない。セキュリティに関しては最低限パスワード認証を禁止してポート番号を変えておくと良い。
 
torque-server
torqueのサーバー。qsubやqdelなどのインターフェイスはここで定義されている模様。

torque-scheduler
ジョブスケジュラー。どのジョブをどのノードで実行するかなどの意思決定を行う。いろんな研究成果を生かした、とても賢い人工知能だと言える。

wakeonlan
コマンドラインからLANにあるコンピュータを起動することが出来る。
サーバーの稼働率や設置場所にも依るが、いちいち電源ボタンを押すのは非効率である。ヘッドからコマンドラインでスレイブノードを起動できるようすると環境構築に便利である。使い方はこちらに

nfs-kernel-server
NFS(Network File System)の為のサーバー。NFSとは簡単に言うとネットワーク上でファイルシステムを共有するというものである。Torqueでは各ノードにあるファイルを統一するのに使われる。ユーザーはヘッドにファイルを置くことで実際の実行環境にも同様にファイルを置くことが出来るということだ。NFSとは何かについてはこちらの記事がわかりやすい
 
mail-utils
postfix
メールサーバー。Torqueには実行終了をメールで知らせる機能があるが、その送信の為に必要になる。また、サーバーは特に夏にはCPU温度をモニタリングする必要がある。CPU温度が閾値を超えたらメールを送るなどの処理をする為にもメールサーバーは有用である。

torque-mom
torque-client
ジョブを受け取って実行する為のパッケージ。


3-2. 環境の移植をする


上で説明したパッケージは汎用的なものだが、環境に応じて必要なパッケージを設定する必要がある。
もし既にあるUbuntuのパッケージを移植する必要があるなら、以下の手順で移植することが出来る。

1. 移植元のコンピュータのパッケージリストを得る
sudo dpkg --get-selections | awk '{print $1}'  > pkglist

2. 移植先のコンピュータにpkglistを送る(USBなどで)

3. 移植先のコンピュータでパッケージをインストールする
cat pkglist | xargs sudo aptitude install -y

これで移植元のパッケージが揃うことになります。ただしバージョンなど、すべて同じ設定になる訳ではありませんし、パッケージではないものはなくなります。



4. OpenSSHサーバー・クライアントの設定をする


4-1. 鍵の生成と交換

openssh-serverをインストールした時点でサーバーは立ち上がっている。ただしお互いにログインする為には公開鍵を共有する必要がある。

ssh-keygen

で固有の秘密鍵・公開鍵のペアを生成することが出来る。

sshサーバーは自身の~/.ssh/authorized_keysに書かれた公開鍵を持つクライアントのみとセッションを開く。ので、すべてのノードで鍵を生成し、すべてのノードのauthorized_keysにコピーする必要がある。あるいは、すべて共通の鍵を利用するということも出来なくはないが、セキュリティ上別の鍵にした方が良いだろう。

4-2. ホストの設定


/etc/hostsと/etc/hosts.allowに通信先のホスト名を記入する必要がある。

/etc/hostsはUbuntuインストール時は自分のPC名とローカルホストとipv6関連のみがかかれているはずである。ここに自分と他のノードのIPアドレスを列記する。ここでの設定はTorqueにも使われる。
 
/etc/hosts
127.0.0.1    localhost
127.0.1.1    yuu

10.44.0.100    head
10.44.0.101    node001
10.44.0.102    node002
# The following lines are desirable for IPv6 capable hosts
::1     ip6-localhost ip6-loopback
fe00::0 ip6-localnet
ff00::0 ip6-mcastprefix
ff02::1 ip6-allnodes
ff02::2 ip6-allrouters
/etc/hosts.allowはTCP接続を許可する相手を指定できる。ここでまとめてローカルネットワーク内のホストを許可することが出来る。

/etc/hosts.allow
portmap: 10.44.0. ALLOW
lockd: 10.44.0. ALLOW
rquotad: 10.44.0. ALLOW
statd: 10.44.0. ALLOW

5. torqueの設定をする


ここの設定はTORQUEの導入・設定に譲る。よくあるエラーに対する対処法もかかれている。
ひとつ追加したいのは、サービスをリスタートすると問題が解決することが多いということである。
torque-serverなどはserviceとして常にバックで走るソフトなので、実行中に設定変更されてもすぐには反映されない。その為環境構築中はこまめに

sudo service torque-server stop
sudo service torque-scheduler stop
sudo service torque-scheduler start
sudo service torque-server start

とすると良い。これでエラーが解決することは多い。スレイブノード側の場合はtorque-momとtorque-clientでこれを行う。


この時点ジョブを実行することが出来るようになっているはずである。ヘッドノードで

pbsnodes

と打って

node001
     state = down
     np = 8
     ntype = cluster 
node002
     state = down
     np = 8
     ntype = cluster
のように出力されたらノードが認識されているということである。
スレイブノードで

pbsnodes -a

と打つとstate = freeとなるはずである。
そうでない場合はここまでの設定を見直す必要がある。

6. NFSの設定をする

ヘッドノードをそのままNFSサーバーとして使うことが出来るが、ノードの数が多いクラスタの場合はヘッドとは別にNFSサーバーを置くべきだろう。その場合も設定方法に違いはない。
How To Set Up an NFS Mount on Ubuntu 14.04が良くまとまっている。
日本語だとUbuntuでNFSサーバの設定をするがわかりやすい。


7. メールの設定をする


postfixをインストールしただけだと多くのメールに送信出来ない。
それは今のメールサーバはPort 25を禁止にしているからである。Port 25はメールの為の標準のポート番号とされている。しかしそのため、多くのスパムメールはPort 25によって送られていた。それを受けてどのメールサーバもPort 25からはメールを受信しない設定をしている。

GmailのアカウントがあればGoogleのメールサーバを使うのがわかりやすい。
サーバでメールを送るまでに設定方法が書かれているのでこちらを参照されたい。





以上の7ステップでTorqueのサーバーを立ち上げることが出来る。試しに以下のコマンドを
複雑に思えるが各要素技術は概念としてはシンプルなものであり、また非常に汎用的に使われているものが多い。Torqueサーバーの有用性はさながら、これを立ち上げることは良い勉強にもなるだろう。