Abstract
Shellscript で設定ファイルを読み込む場合など，コメントを削除したいことがある．このような場合は cut コマンドで，不要なコメントを削除するとよい．
2023年4月4日
2022年6月30日
C/C++ の簡易パッケージマネージャを作った話
概要
ある程度大きなソフトウェアを開発するには，
ソフトウェアを機能ごとにモジュール化して，
機能ごとに開発すると，効率的に分業できる．
また，インターフェースに互換性があれば，
複数ライブラリをベンチマークして，
機能ごとに最もユースケースに合うライブラリを利用することもできる．
パッケージ管理において Python は非常に参考になる言語で， 例えば，requirements.txt にインストールしたいライブラリとバージョンを記載して pip を実行すれば，ものの数分で環境が構築できる． しかも，venv などを利用すれば仮想環境として構築できるため， 同じ PC の中に複数プロジェクト向けの環境を用意できる． こうした仕組みは是非とも C++ にも欲しい．
既存の C++ 向けパッケージマネージャーもあるが，なぜか pip でのインストールが必要だったり，デファクトスタンダードというレベルのものはないため， C/C++ 向けの簡易パッケージマネージャーを試しに開発してみることにした．
※ C++ で既存のパッケージマネージャーとしては Conan や Vcpkg, Hunter, Buckaroo, poac などがある．ここで紹介するのは，趣味で作ったおもちゃの（プロダクトレベルでない）パッケージマネージャーなので，本格的に利用する場合は，よくよく各パッケージマネージャーを比較検討することをお勧めする．
※ 2013 年以降，docker の登場により，C++ の環境としても構築しやすくなってはいるが， docker の主眼は（パッケージ管理ではなく）環境そのものの仮想化なので，別の問題として考える．
パッケージ管理において Python は非常に参考になる言語で， 例えば，requirements.txt にインストールしたいライブラリとバージョンを記載して pip を実行すれば，ものの数分で環境が構築できる． しかも，venv などを利用すれば仮想環境として構築できるため， 同じ PC の中に複数プロジェクト向けの環境を用意できる． こうした仕組みは是非とも C++ にも欲しい．
既存の C++ 向けパッケージマネージャーもあるが，なぜか pip でのインストールが必要だったり，デファクトスタンダードというレベルのものはないため， C/C++ 向けの簡易パッケージマネージャーを試しに開発してみることにした．
※ C++ で既存のパッケージマネージャーとしては Conan や Vcpkg, Hunter, Buckaroo, poac などがある．ここで紹介するのは，趣味で作ったおもちゃの（プロダクトレベルでない）パッケージマネージャーなので，本格的に利用する場合は，よくよく各パッケージマネージャーを比較検討することをお勧めする．
※ 2013 年以降，docker の登場により，C++ の環境としても構築しやすくなってはいるが， docker の主眼は（パッケージ管理ではなく）環境そのものの仮想化なので，別の問題として考える．
2022年5月28日
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
この計算コスト削減の観点では， 基準となる 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
2019年5月19日
2019年4月21日
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 を用いた並列化を行う．
並列化を行う場合に，まず思い浮かべるのは，スレッドを生成しての並列化である．C++11 からは std::thread が標準化されているため，Windows か Linux かを意識せずに並列化できる．しかしながら，単純にタスクをスレッド数で割って処理させると，実行時間の不均一性から，処理の後半でプロセッサに空きができるなど問題がある．プロセッサを遊ばせないためには，タスクを一度スレッドプールに集約し，スレッドプールから，各 CPU に処理を振る必要がある．このような煩雑な処理の実装は，非常に骨の折れる作業である．このような状況に際しても，OpenMP は，ディレクティブ 1 行で並列化され，schedule(guided) オプション１つでスレッドプーロを生成する．
実際に並列化が必要とされる状況について，例えば，多量のデータを扱う場合，CSV 等からタスクの一覧を読み込み，タスクごとに処理することは多い．これは，アムダールの法則 [3] を考えた場合，処理の単位が大きく並列化不能な箇所が少ないため，並列度を上げて実行時間を削減し易い．また，実装に際しても，大きな単位でのみ並列化の面倒を見ればよいため，実装の負担が少ない．
本投稿では，OpenMP の簡単な実装例／実行例を示した後，多数のグラフプロットを必要とする GIF 動画の生成について，OpenMP を用いた並列化を行う．
2019年4月11日
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. 行ベクトルのコンストラクタは，それぞれの行ごとに別に呼び出される．
このように，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. 行ベクトルのコンストラクタは，それぞれの行ごとに別に呼び出される．
2018年12月13日
UNIX 哲学に学ぶ 高品質なソフトウェア設計
Outline
なぜ UNUX 哲学 [1] なのか．まずはこの題意について説明したい．UNIX [2] の誕生には，先行して開発されていた Multics [3] の「新奇なアイデアを貪欲に取り込んだ [3]」結果，「巨大で複雑なものに [2]」なり，「現実解 [3]」となり得なかった歴史がある．これを踏まえ，UNIX では，まず小規模に動作するシステムを作り，巨大で複雑な問題に対しても，巨大な単一プログラムで解決することを避け，小規模なソフトウェアへと分割し，組み合わせることで，解決した．このような UNIX 開発における経験則を，UNIX 哲学と呼び，我々の求める高品質なソフトウェア設計の礎となり得る思想である．品質の高いソフトウェア開発には，ある種の哲学，つまりは設計思想が重要となる．本投稿では，UNIX 哲学を交えつつ，ソフトウェア設計に必要な設計思想について，おおよそ一般的と思われることを説明する．
※ この記事は，「みゅーもり Advent Calendar 2018 (通称：みゅんカレ)」13 日目の記事です．十分に検証されたものではなく，私の理解を大雑把にまとめたものです．したがって，事実と異なる可能性があります．また，本文中の擬似コードは C/C++ または Python です．
※ この記事は，「みゅーもり Advent Calendar 2018 (通称：みゅんカレ)」13 日目の記事です．十分に検証されたものではなく，私の理解を大雑把にまとめたものです．したがって，事実と異なる可能性があります．また，本文中の擬似コードは C/C++ または Python です．
2018年9月29日
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] のような，古典的で基本的なセキュリティ問題に対処した．
2018年8月17日
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]」のこと．
そこで，本投稿では，計算や解析で特に多用される std::vector<T> に対して演算子を定義することで，記述の簡略化を図る．より具体的には，四則演算子と剰余演算子，べき乗演算子を定義した．また，左シフト演算子 (<<) と 左シフト代入演算子 (<<=) をそれぞれ要素の結合と追加 (.push_back()) として割り当てた．この結果，先ほどの演算は，std::vector<double> a={1,2,3}; a*=4; のように簡略化された．
※ RAII は Resource Acquisition Is Initialization の省略形．「資源（リソース）の確保と解放を，クラス型の変数の初期化と破棄処理に結び付けるというプログラミングのテクニック [追記1]」のこと．
2018年7月21日
不偏分散の定義と証明，および 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$ は 不偏分散， をそれぞれ表す．
※ $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$ は 不偏分散， をそれぞれ表す．
登録:
投稿 (Atom)