バイナリ行列演算ライブラリの開発と 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 を新たに作成する．

要素の挿入と削除による性能低下を抑えた高速ハッシュテーブルアルゴリズムの提案

A proposal and implementation of a fast hash table algorithm which suppresses decrease in search performance that is caused by repeating addition and deletion of elements (C/C++) August 2015 - January 2017

Abstract

  Although the hash table of the Open Addressing method shows high search performance, the search performance is decreased by repeating addition and deletion of elements. And the hash table of the Closed Addressing method doesn't change search performance, although search performance is low because of its pointer connections make cache miss. Therefore, I developed an algorithm that embeds a doubly linked list in the Open Addressing hash table. When a load factor is 50%, this algorithm is 2.18 times for insertion, 1.23 to 1.44 times for search and 1.80 times for deletion faster than std::unordered_map in Microsoft Visual C++ 2015 respectively. Moreover, by adopting the doubly linked list, Unlike the conventional Open Addressing type hash table, decreases of search performance due to addition and deletion of elements is suppressed under 6%. The suppression of decrease in search performance is due to the ability to insert elements in the place where is little need to seek by adopting the doubly linked list. (Added on March 10, 2017)

  従来の Open Addressing 方式のハッシュテーブルは， 検索性能は高いものの，要素の追加と削除を繰り返すことで， 検索性能が低下することが知られています． また， 要素の追加と削除により，検索性能が変化しない， Closed Addressing 方式のハッシュテーブルは， 検索性能が低いことが知られています． この投稿では，高速な Open Addressing 方式のハッシュテーブルに， 双方向リスト構造 (鎖型構造) を埋め込むアルゴリズムを開発し， key: UINT64，value: UINT64 のペアについて， Microsoft Visual C++ 2015 に実装されている std::unorderd_map ※1 と比較して， 挿入 2.18 倍，検索 1.23~1.44 倍，削除 1.80 倍の性能を達成しました． また， 双方向リスト構造の採用により， 従来の Open Addressing 型のハッシュテーブルと異なり， 要素の追加と削除による検索性能の低下を 6% 以内に抑えました ※2．