shellscript でコメントを削除する

Abstract

  Shellscript で設定ファイルを読み込む場合など，コメントを削除したいことがある．このような場合は cut コマンドで，不要なコメントを削除するとよい．

C/C++ の簡易パッケージマネージャを作った話

概要

    ある程度大きなソフトウェアを開発するには， ソフトウェアを機能ごとにモジュール化して， 機能ごとに開発すると，効率的に分業できる． また，インターフェースに互換性があれば， 複数ライブラリをベンチマークして， 機能ごとに最もユースケースに合うライブラリを利用することもできる．
  パッケージ管理において Python は非常に参考になる言語で， 例えば，requirements.txt にインストールしたいライブラリとバージョンを記載して pip を実行すれば，ものの数分で環境が構築できる． しかも，venv などを利用すれば仮想環境として構築できるため， 同じ PC の中に複数プロジェクト向けの環境を用意できる． こうした仕組みは是非とも C++ にも欲しい．
    既存の C++ 向けパッケージマネージャーもあるが，なぜか pip でのインストールが必要だったり，デファクトスタンダードというレベルのものはないため， C/C++ 向けの簡易パッケージマネージャーを試しに開発してみることにした．

※ C++ で既存のパッケージマネージャーとしては Conan や Vcpkg, Hunter, Buckaroo, poac などがある．ここで紹介するのは，趣味で作ったおもちゃの（プロダクトレベルでない）パッケージマネージャーなので，本格的に利用する場合は，よくよく各パッケージマネージャーを比較検討することをお勧めする．
※ 2013 年以降，docker の登場により，C++ の環境としても構築しやすくなってはいるが， docker の主眼は（パッケージ管理ではなく）環境そのものの仮想化なので，別の問題として考える．

C++ で複数の std::vector<T> を１つの std::vector<T> を基準にソートする

概要

  C++ で複数の std::vector<T> を１つの std::vector<T> を基準に sort する場合を考える ※1． こうした場合，通常 std::vector<T> に含まれる値を構造体や，std::pair<T>, std::tuple<T> に入れ替えてから std::sort() で並び替える． ここで，sort された結果を，構造体や，std::pair<T>, std::tuple<T> のまま取り扱いたい場合は問題ない． 一方で，構造体や，std::pair<T>, std::tuple<T> を，再び std::vector<T> に変換したい場合は， データ構造ごとに別々の実装が必要でコードは煩雑となり，計算コストも増える．
  この計算コスト削減の観点では， 基準となる std::vector<T> の sort 順序を保存しておき， 保存結果を元に残る std::vector<T> する方法が考えられる． この考えは，例えば Stack overflow で取り上げられている ※2．
  この投稿では，計算コストを加味した上で，さらにコードを簡略化する方法を紹介する． C++ のテンプレートの再帰展開を応用すると，これまで煩雑だった処理を１行で記述できるようになる．

※1. 具体例としては，一方の std::vector<T> が ID を持っており，もう一方の std::vector<T> が対応する文字列を持っている場合に， ID を基準として 2 つの std::vector<T> を並び替えたい状況が考えられる．
※2. 例えば，StackOverflow に紹介されている． Sorting multiple vectors based on a reference vector

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 行で実行するライブラリを開発した．

バイナリ行列演算ライブラリの開発と Xorshift 疑似乱数生成器のパラメータ計算

Development of binary matrix calculation library and calculation of Xorshift RNG parameter

Abstract

  バイナリ行列※1は，0 と 1 の 2 値しかとらない行列で，xorshift 疑似乱数生成器の位数計算などに用いられる．しかしながら，高速にバイナリ行列を計算する専用のライブラリを確認できなかったため開発した．char 型の配列を利用した計算と比較して，1/8 のメモリで済み，bit 演算により バイナリ行列乗算を 24~ 600 倍程度高速に計算できると推測される※2．ライブラリとしての利便性を考慮して，演算子のオーバーロードを行うとともに，サンプルプログラムとして xorshift 疑似乱数生成器の位数を計算した．

※1. Wikipedia では，"logical matrix, binary matrix, relation matrix, Boolean matrix, or (0,1) matrix" の名称で紹介されている[8]．bits martix の名称は一般的でないと思われる．
※2. char 型の配列を利用したバイナリ行列演算を実装していないため，直接の比較はしていないが，利用した手法 [3] から，32x32 bits で約 24 倍，64x64 bits で約 60 倍，1024x1024 bits で約 120 倍，4096x4096 bits で約 590 倍，高速に計算できると推測される．

C++ から Python (Matplotlib) でグラフを描く

Abstract

  C++ から Python の Matplotlib でグラフを生成する場合，lava/matplotlib-cpp 等の Python/C API を利用した手法が知られている．しかしながら，様々な制約のため Python/C API を利用できない場合がある．このような場合，C++ で生成したデータを CSV 等のファイルへ一旦書き出した後，再度 Python でデータを取り込むことで描画できるが，これも，大きな労力を伴う．そこで，本投稿では，system 関数により，Python をコマンドラインからの呼び出しとして実行し，この際に描画データを引数として受け渡すことで，労力の軽減を図る．

※ 現在では C++ から任意の Python 関数を実行する の方が，簡単です． - 2018.0316 追記

WinSCP から Cygwin 上の Emacs を起動する

Abstract

  本投稿では，Cygwin 上にインストールされた，Emacs を，WinSCP から起動します．WinSCPは，MS-Windows上で動くオープンソースでグラフィカルなFTP，FTPS，SFTPクライアントプログラムです [1]．WinSCP は，コマンドプロントからの呼び出しと同様の手法で，外部の様々なエディタを起動できます．しかし， Cygwin 上にインストールされた Emacs は，引数の与え方の関係で上手くいきません．そこで，本投稿では，まず，Cygwin 上にインストールした Emacs をコマンドプロントから呼び出します．次に，WinSCP からバッチファイルを経由することで，Cygwin 上の Emacs を起動する方法を提案します．

競技プログラミングこと始め

Abstract

  プログラミングコンテストでは，プログラミングの様々な技能を競い合う．その中で，競技プログラミングでは，出題された同一の問題を，より早く正確にコーディングする技能を競う．
  当然だが，競技プログラミングでは値の入出力を行う必要がある．しかしながら，全く対策をしないと，そもそも普段 sprintf() を使わないから挙動が分からない，といった事態に陥る．この最悪の事態を回避するため，これら基本的な操作と，競技プログラム特有の簡略化表現についてのテンプレートを作成する．また，コンテストの過去問やその答案を学習する．

C++ で MatB(':', 0) = MatA(':', 0); を実装する

概要

  この投稿では，C++ で行列の行や列のコピーを簡便に記述するために，演算子のオーバーロードを組み合わせ， MatB(':', コピー先の列数) = MatA(':', コピー元の列数); や MatB(コピー先の行数, ':') = MatA(コピー元の行数, ':'); のような記法を目標とする．これは，Python などの高級言語に似せた記法である (※要確認)．

固有値の検算

概要

  この投稿では固有値を検算する手法と，その証明を示す．固有値計算を実装した場合や，固有値計算で桁落ちが疑われる場合など，計算した固有値が正しい値か確認したいことがある．そこで，下記に示す行列の性質を利用すると，簡易的に固有値が正しい値か検算できる．この性質は一般によく知られている．

汎用 Makefile の書き方

概要

  C/C++ 言語において，コンパイラに MSVC++ ではなく GCC を使用する場合， コマンドラインから $ g++ main.cpp   のようにしてコンパイルを行うことは常である． ファイルが少ない場合や，依存関係の簡単な場合は， コマンドも短く，コンパイルも直ちに終わるため， 大きな問題とはならない． しかしながら， 少し複雑なプログラムを書けば， すぐに多くのファイルを引数に与える必要が生じる． これを解決するために，ご存じのとおり Makefile が使用される． しかしながら， 数十を超えるファイルの依存関係を， ベタ打ちで Makefile に記述することは， とても骨の折れる作業である． また， 誤った記述によるコンパイルエラーや， ファイルの追加や削除による書き換えなど， 非常に手間がかかる． そこで， ファイルとその依存関係を自動で認識し， Makefile の変更を最小限に抑えた， 汎用的に使用できる Makefile が求められる． 現状存在する汎用 Makefile のネットサンプルを元に， 簡潔に理解でき，少ないコストで維持・管理可能かつ， 完動する汎用 Makefile を新たに作成する．