Git Commands Cheating Sheet

Abstract

  この投稿では，使用頻度の高い git command とその使用方法を示す．

OpenMP による C++ コードの並列化

Abstract

　並列化の方針には，1) １タスクあたりの実行時間を削減する方針 (ストロング・スケーリング [1]) と，2) １タスクの実行時間はそのままだが，多数のタスクでも１タスクの時と同じ実行時間で処理する方針 (ウィーク・スケーリング [1]) の 2 種類がある．OpenMP は「OpenMP が使用できない環境では無視されるディレクティブ [2]」を用いて，for 文単位で並列化を行うため，ストロング・スケーリングに向いているが，実際には，並列化をタスク単位に調整すれば，ウェーク・スケーリングに利用できる．
　並列化を行う場合に，まず思い浮かべるのは，スレッドを生成しての並列化である．C++11 からは std::thread が標準化されているため，Windows か Linux かを意識せずに並列化できる．しかしながら，単純にタスクをスレッド数で割って処理させると，実行時間の不均一性から，処理の後半でプロセッサに空きができるなど問題がある．プロセッサを遊ばせないためには，タスクを一度スレッドプールに集約し，スレッドプールから，各 CPU に処理を振る必要がある．このような煩雑な処理の実装は，非常に骨の折れる作業である．このような状況に際しても，OpenMP は，ディレクティブ 1 行で並列化され，schedule(guided) オプション１つでスレッドプーロを生成する．
　実際に並列化が必要とされる状況について，例えば，多量のデータを扱う場合，CSV 等からタスクの一覧を読み込み，タスクごとに処理することは多い．これは，アムダールの法則 [3] を考えた場合，処理の単位が大きく並列化不能な箇所が少ないため，並列度を上げて実行時間を削減し易い．また，実装に際しても，大きな単位でのみ並列化の面倒を見ればよいため，実装の負担が少ない．
　本投稿では，OpenMP の簡単な実装例／実行例を示した後，多数のグラフプロットを必要とする GIF 動画の生成について，OpenMP を用いた並列化を行う．

A single header file template container class of pseudo 2 dimensions row-major and column-major matrix

C++ における行列コンテナ sstd::mat_c<T>/sstd::mat_r<T> の提案

Abstract

　C++ において，画像処理や線形代数演算を行う場合，動的確保された固定長 2 次元配列クラスが用いられる．一般に，画像では，行方向にデータが格納されているため，row-major (行優先) の配列が用いられる．また，数値行列では，固有値計算における固有ベクトルなど，必要な計算結果が列方向に現れるため，column-major (列優先) の配列が用いられる．例えば，画像処理ライブラリである OpenCV の cv::Mat クラスは row-major として，線形代数演算ライブラリである Eigen の Matrix クラスは column-major として※1，それぞれ設計されている．また，可変長 2 次元配列を動的確保する場合，std::vector<std::vector<T>> が用いられる．これは，要素の追加や削除が発生する場合に有効である．
　このように，C++ において 2 次元配列を利用する場合は，用途に応じて型を使い分けることが望ましい．しかし，実態として，OpenCV や Eigen を用いない場合は，殆ど std::vector<std::vector<T>> が用いられている．これは，現状の STL が標準的な行列コンテナとして std::matrix<T> を提供しておらず，また，代替クラスの設計にはコストが掛かることに起因する．基本的に，std::vector<std::vector<T>> は row-major であるため，column-major のデータを扱うには不向きである．加えて，各行ベクトルは独立してメモリ確保されるため※2，メモリアドレスは不連続となる．これらは，キャッシュミスを誘発する．更に，例え固定長であっても，std::vector<T> は，現在確保しているメモリ長と挿入されている要素数を保持するため，余分にメモリを消費する．これらの問題を解消するため，本投稿では，標準的な行列コンテナとして，sstd::mat_r<T> (row-major: r) と sstd::mat_c<T> (column-major: c) を提案する．

※1. Eigen は，行列サイズが小さい場合，静的確保を用いる ^[1]．
※2. 行ベクトルのコンストラクタは，それぞれの行ごとに別に呼び出される．

UNIX 哲学に学ぶ 高品質なソフトウェア設計

Outline

　なぜ UNUX 哲学 ^[1] なのか．まずはこの題意について説明したい．UNIX ^[2] の誕生には，先行して開発されていた Multics ^[3] の「新奇なアイデアを貪欲に取り込んだ ^[3]」結果，「巨大で複雑なものに ^[2]」なり，「現実解 ^[3]」となり得なかった歴史がある．これを踏まえ，UNIX では，まず小規模に動作するシステムを作り，巨大で複雑な問題に対しても，巨大な単一プログラムで解決することを避け，小規模なソフトウェアへと分割し，組み合わせることで，解決した．このような UNIX 開発における経験則を，UNIX 哲学と呼び，我々の求める高品質なソフトウェア設計の礎となり得る思想である．品質の高いソフトウェア開発には，ある種の哲学，つまりは設計思想が重要となる．本投稿では，UNIX 哲学を交えつつ，ソフトウェア設計に必要な設計思想について，おおよそ一般的と思われることを説明する．

※ この記事は，「みゅーもり Advent Calendar 2018 (通称：みゅんカレ)」13 日目の記事です．十分に検証されたものではなく，私の理解を大雑把にまとめたものです．したがって，事実と異なる可能性があります．また，本文中の擬似コードは C/C++ または Python です．

C++ による non-blocking socket を用いた http サーバの実装

Abstract

  http サーバは http daemon (httpd) とも呼ばれ，socket 通信を用いてブラウザと通信するサーバ側のプログラムである．以前は，接続数と同じ数のプロセスを立ち上げ，blocking を行う実装が一般的であったが，nginx (エンジンエックス) [1] の登場以来，特に静的な web ページでは，non-blocking な実装により，1 つのプロセスで複数の接続を処理することで，コンテキストスイッチと呼ばれるプロセス切り替えのオーバーヘッドを削減する手法が広がっている．しかしながら，non-blocking の実装サンプルは少なく，実装しても些細なミスで致命的に動作せず，また，存在するサンプルも，httpd の実装と，socket 回りの実装が密結合となっており，分離が難しいことが分かる．加えて，nginx のソースコードも，動作を理解するには，非常に大規模で複雑であった．したがって，本投稿では，定数時間でイベントを監視可能な epoll を用いて，httpd の socket 通信部分と httpd 部分とが疎結合となる見通しのよいサンプルを実装する．結果として，簡単な HTML と CSS を用いた画像付きのサンプルページを配信可能な httpd を実装した．また，request URL の確認において，hash table を用いた照合によりパスを確認することで，ディレクトリトラバーサル [2] のような，古典的で基本的なセキュリティ問題に対処した．

std::vector<T> で MATLAB や numpy のように配列計算する

Abstract

  C++ において，クラスのコンストラクタ中でメモリを確保し，ディストラクタ中でメモリを解放することで，メモリ寿命をクラス寿命としてスコープにより制御すること (RAII※) は一般的である．C++ において，単なる配列を RAII に従い実装する場合，新たなクラスを定義することはせず，std::array<T> や std::vector<T> などの標準実装のコンテナ型を用いることが一般的である．これらのコンテナ型は，単なる配列としてだけでなく，数値計算やデータ解析における配列としても多用される．このとき「要素の追加」や「配列全体への演算」といった操作が頻繁に発生する．しかしながら，現状では std::vector<T> に演算子が定義されておらず，MATLAB における a=[1, 2, 3]; a*=4 や numpy における a=np.asarray([1,2,3]); a*=4 といった演算は，std::vector<double> a={1,2,3}; for(int i=0; i<a.size(); i++){ a[i]*=4; } のように，for 文を用いた冗長な記述となる．
  そこで，本投稿では，計算や解析で特に多用される std::vector<T> に対して演算子を定義することで，記述の簡略化を図る．より具体的には，四則演算子と剰余演算子，べき乗演算子を定義した．また，左シフト演算子 (<<) と 左シフト代入演算子 (<<=) をそれぞれ要素の結合と追加 (.push_back()) として割り当てた．この結果，先ほどの演算は，std::vector<double> a={1,2,3}; a*=4; のように簡略化された．

※ RAII は Resource Acquisition Is Initialization の省略形．「資源（リソース）の確保と解放を，クラス型の変数の初期化と破棄処理に結び付けるというプログラミングのテクニック [追記1]」のこと．

不偏分散の定義と証明，および n-1 の解釈

Abstract

  本投稿では，不偏分散の定義とその解釈について説明する． 不偏分散 $\sigma_u^2$ は， 1) 標本分散の期待値 $E[\sigma^2]=\frac{n-1}{n}\sigma_0^2$ と， 2) 母分散 $\sigma_0^2$ の偏りを無くすため，標本分散 $\sigma^2$ を $\frac{n}{n-1}$ 倍した値として定義される． このように，不偏分散は，期待値について偏りの無い分散として定義される． 数式の解釈について，サンプル数が有限の場合 (特に，サンプル数が極端に少ない場合)，母分散の範囲に当たりをつけるには，分散を広めに見積もる必要がある．$\frac{n}{n-1}$ 倍は，1) と 2) を比較して，どの程度範囲を広げれば母分散の範囲を指示できるか，を計算した値と考えられる．

※ $n_0$ は 母数， $n$ は 標本の数 (サンプル数)， $\overline{x}\equiv\frac{1}{n}\sum_{i=1}^n{x_i}$ は 標本平均， $\sigma^2\equiv\frac{1}{n}\sum_{i=1}^n(x_i-\overline{x})^2$ は 標本分散， $\overline{x}_0\equiv\frac{1}{n_0}\sum_{i=1}^{n_0}{x_i}$ は 母平均， $\sigma_0^2\equiv\frac{1}{n_0}\sum_{i=1}^{n_0}(x_i-\overline{x})^2$ は 母分散， $\sigma_u^2\equiv\frac{1}{n-1}\sum_{i=1}^n(x_i-\overline{x})^2$ は 不偏分散， をそれぞれ表す．

論文の紹介と検証：Marsaglia, G. 2003. Xorshift RNGs.

Abstract of this post

  This post will introduce Marsaglia, G. 2003. Xorshift RNGs. [1] which is a paper of Xorshift random number generator. And, in the reproducing process of calculating the hyperparameters reveals that [1] has a few calculation mistakes of hyperparameters. This result means that there is a parameter which enable to generate random number by only 2 calculations of 64 bits xorshifts while [1] said that at least 3 calculations are required.

  この投稿では，Xorshift 疑似乱数生成器の論文 Marsaglia, G. 2003. Xorshift RNGs. [1] を紹介する．前提条件として，参考文献 [2] 読了レベルの知識を必要とする．以下，論文の節に沿って適宜翻訳を行いながら，必要な計算の実装と実行結果を示す．また，再現実験および，[追記2] より，[1] のパラメータのいくつかとは異なる計算結果を得た．また，shift 操作 2 回で乱数を生成できるパラメータは存在しないとされていたが[1]，64 bits 時において，存在することを示す計算結果を得た．

C++ から Email (Gmail) を送信する．

Abstract

  この投稿では，C++ から Email (Gmail) の送信を行う．C++ からメールを送信するには，socket 通信で接続を確立し，OpenSSL 等の暗号化ライブラリ通して通信する必要がある．socket 通信まで正常に動作させられれば，暗号化通信は socket を OpenSSL でラップするだけである．その後，メールサーバーと定型文をやり取りすることで，メールが送信される．本投稿ではメールサーバとして Gmail を利用する．Gmail をプログラムから利用するにあたり，予め Gmail の「安全性の低いアプリの許可:」を「有効」にする必要がある．また，2 段階認証を使用している場合は，本プログラム用にアプリケーションパスワードを発行しておく必要がある．

C++ から任意の Python 関数を実行する

Calling any Python function from C++

Abstract

  There is a few methods to run python functions on C++ like boost::python or using of Python.h. For example, using boost.python needs to convert C++ types like std::vector<T> frequently used as a standard implementation to Python types like numpy enable to give them as a function arguments. While this method will provide high execution efficiency, users need to prepare or convert types like std::vector<T> to Python types. For these reasons, sstd::c2py has been developed in order to call any Python functions with built-in, std::vector<T>, sstd::mat_c<T> or sstd::mat_r<T> (T is limitted by built-in types.) types from 2 lines of C++ codes.

  C++ から Python 関数を呼び出すには，boost::python や Python.h ヘッダからの API 呼び出しが知られている．例えば，boost::python を利用する場合は，C++ 側で Python 側へそのまま受け渡しができる numpy 型等を用意した上で python 関数の呼び出しを行う ([8] より推察)．この手法は，高い実行効率を得られる反面，標準実装として C++ で頻繁に用いられる std::vector<T> 型をそのまま利用しようとした際に，ユーザ側で変換しておく必要がある ([9] より推察) など，実装に必要な手間も大きい．そこで，C++ の built-in 型 および std::vector<T>, sstd::mat_c<T>, sstd::mat_r<T> (ただし，T は built-in 型に限る．) と同等の numpy 型を引数に取る任意の Python 関数を C++ から 2 行で実行するライブラリを開発した．