C++
タイトルの通り、マルチプロセスで使用可能なロックフリーのFIFOキューを実装したので、その簡単な紹介。 作成物 github: ipc-msgque (0.0.4) ロックフリーなFIFOキュー 再入可能 かつ SIGKILLに対して安全*1 C++ 共有メモリ(mmap)を使用 マルチプロセス(and…
結論: デッドロックになってしまう 自動的にロックを解放してくれたりはしないみたい。 以下、試した内容のメモ書き。 環境 $ cat /proc/version Linux version 3.0.0-23-generic (buildd@komainu) (gcc version 4.6.1 (Ubuntu/Linaro 4.6.1-9ubuntu3) ) #38…
今年はlisp系のプログラミング言語(及びその処理系)を作ってみようと考えていて、かつ(少なくとも)当面の間はスタック型VMを基盤として実装していくことになると思われるので、まずは単純なスタックマシンのバイトコードインタプリタで、どの程度の処理速度…
割合汎用的な、整数のビットを前後反転する関数を作成してみた。 2の乗数サイズの任意の整数型のビット反転が可能。 // 反転例 bit_reverse(0x0000FFFF) => 0xFFFF0000 // 実装 // バイト単位での変換表 const unsigned char REV_BYTE[]={ 0,128,64,192,32,1…
ハッシュテーブルを実装してみた。 ・cc-dict-0.0.3 チェイン法を用いたハッシュテーブルで、リンクリスト(チェイン)のノードを割り当てる際に自前のアロケータを使っている点以外は、特に変わったところもないと思う。 ベンチマーク 一応、ベンチマークも取…
g++(及びその他)のunordered_mapで文字列をキーにしたい場合の注意書き。 unordered_mapのようにconst char*を指定すると、キーが文字列ではなくポインタ(整数値)として解釈されてしまう*1。 以下、その際の挙動の確認用のコード: /** * ファイル名: str_map…
構造体やクラスのインスタンスの特定のフィールドのアドレス(ポインタ)だけ分かっている場合に、そこからオブジェクト全体のポインタを取得したい場合に使うマクロ。 やっていることは単にフィールドのアドレスから、そのフィールドの(クラスor構造体の)先頭…
今日は久しぶりにUNF(ユニコード正規化ライブラリ)に手を加えていた。 大きな変更点は、正規化用変換テーブルを実現していたTRIEをDAWGにしたこと。 もともとは正規分解と互換分解用に、内容がほぼ等しいTRIEを別々に持っていたので、それを一つDAWGにして共…
以前にcommon lispで実装したSA-ISアルゴリズムを、C++でも実装したのでその計時結果など。 ソースコード(github): sais-0.0.1 計時 対象データには以下のサイズのテキストファイル群を使用。 $ ls sa.txt.* -rw-r--r-- 1 user user 10000 2010-12-23 19:25 …
以前にCommon Lispで実装したマルチキークイックソートをC++で書き直して、STLのstd::sortと速度を比較してみた。 使用データ Wikipediaの記事タイトル約500万行を使用。 データ作成方法などはここを参照。 $ wc -l wiki.title.500 5340378 wiki.title.500 $…
前回にソート済みファイルからDAWGを構築する際には、個々のノードのハッシュ値をO(1)で(簡単に)算出可能にするために、ノードにハッシュ値用のフィールドを持たせていた。 ;;;; 再掲 ;; DAWGのノード用の構造体 (defstruct node (label 0 :type octet) (sib…
UNFという名前*1で、C++でUnicode正規化を行うライブラリを実装 (ver 0.0.1)。 ついでに、それを利用したRuby拡張ライブラリも作成。C++やRubyで使える、軽くて高速なUnicode正規化ライブラリは、一年以上前から欲しい(作りたい)と思っていたので、作り終え…
ham(0.0.2)。 Nグラムベースのベイジアンフィルタ。 必要な分だけ実装してサクッと終わらせたかったけど、いくつか試したことが出てきたのでもう少し続ける。 UTF-8以外の文字コード hamは0.0.1ではUTF-8にのみ対応し、その文字Nグラム(N〜Mグラム)*1を素性…
hamの分類性能評価的なもの。 そんなに本格的なことは行わない。 hamでは、基本的に『Practical Common Lisp』にて説明されているスパムフィルタリングの方法(ベイジアンフィルタの一種)をそのまま使わせてもらっている。 このベイジアンフィルタによる分類…
手軽に使える二値分類器*1が急遽必要になったので、ベイジアンフィルタを用いたものを実装。 ham-0.0.1 素性にはNグラムを採用。 対応文字コードはUTF-8のみ。 多分実用程度には高速。 分類性能評価的なことはこれから行う予定。 それらしいデータを用意しな…
Nグラムを取り出すC++のクラスを作成したのでメモ。 UTF-8のみ対応。 /* * ファイル名: ngram.hh */ #ifndef TOKENIZER_NGRAM_HH #define TOKENIZER_NGRAM_HH #include <algorithm> #include <vector> #include <cstring> namespace Tokenizer { class Ngram { public: Ngram(unsigned mi</cstring></vector></algorithm>…
任意のコマンドをデーモンプロセスとして実行するようなコマンドが欲しかったので実装してみた。 /*** * ファイル名: daemonize.c * コンパイル: gcc -o daemonize daemonize * * 概要: * 引数で渡したコマンドをデーモンプロセスとして実行する。 * * 使い…
前回までで最小完全ハッシュ関数(MPHF)の実装方法(の一つ)が分かったので、C++から使いやすくするためにライブラリ(と云う程の規模ではないけど)としてまとめておいた。 ・mphf-0.0.1実装の大枠は、前回のcommon lisp版のものと同様なので略*1。 ハッシュ関…
DAWGのキーに一意なIDをマッピングするために、前回考えた方法は、サイズ的に効率的に実装するのが無理そうなことが分かったので、別の方法に変更することに。 IDへのマッピング 方法概要。 DAWGはIDのことを考慮せずに普通に構築する キーのIDは、完全最小…
tkngさんが作成したMicterという単語分割器の分割部を高速化できるような気がしたので試してみた。 そのメモ。試した結果のソース一式はmimicという名前でgithubに保存しておくことにする*1。 結果 まず、結果から*2。 # 分割対象のテキスト(のサイズ) $ ls …
AC法(エイホ-コラシック法)というものを知ったのでDoubleArrayで試してみた。 概要 入力テキストから、辞書(= 文字列セット)に登録されている文字列を効率的に検索するための方法らしい*1。 詳細は、Wikipediaの『エイホ-コラシック法』の項目を参照。 自分…
各種アルゴリズムを試す際のベースとなるような(シンプルな)DoubleArrayが欲しくなったので作成した。 構成など 多分、DoubleArrayとしては一番単純な構成*1。 ※ 以下で云う"ノード"は、"ノードのインデックス"の略のような意味合い 静的構築 各キーを改行区…
試したいことが出てきたので、少し延長して八回目。 目的 今回の目的は六回目で作成したtrieをベースとし、検索速度を向上させること。 結果 最初に結果から載せる。 入力データや計測方法等は七回目のそれらに準拠。 データサイズ検索所要時間(秒) louds-tr…
七回目。多分最後。これまで作ってきたものを他のtrie実装と比較する。 比較対象 louds-trie: LOUDS++によるtrieの実装。五回目を参照 louds-trie-tail: LOUDS++によるtrie(TAIL配列/圧縮有)の実装。六回目を参照 doar-0.0.12: DoubleArray(TAIL配列/圧縮有)…
前回に作成したLOUDS(LOUDS++)を用いたtrieの改良を試みる。 改良案 前回のtrie実装は、まだまだ全然最適化されていないので、改良すべき(or できるであろう)箇所は結構沢山ある。 案として、例えば... bit-vectorの実装方法 ... 他の実装方法の方が効率的(…
四回目まででLOUDS(LOUDS++)の実装方法は分かったので、今回は応用編。 LOUDSを用いてtrieを実装する(というかtrieを実装したソースコードを載せる)。 作るもの 実際に作成するのは以下の二つのコマンド。 mklouds-trie: ソート済みテキストファイルから、LO…
以下のような内容のファイルがあるとする。 # ファイル名: sample.txt ※ この部分はファイルに含まれない ab abc abef 1 1248 126 13579 これは次のような構造を持つトライ木として考えることができる。※'_ROOT_'は仮想的なスーパールート 今回は、上のよう…
以前に作成したC++によるURLエンコード/デコード関数は、変換先の文字列を格納するためにstd::stringクラスを使っていた。 std::stringを使えば、クラス側がメモリ管理を適切に行ってくれるので楽(バグも生じにくい)なのだが、その分オーバヘッドもある。 UR…
仕事柄(かどうかは分からないが)switch分岐を多用したCやC++の文字列(群?)変換関数を書く機会がたまにある。 例えば最近では、Shift_JISの全角文字(カタカナ+記号)を半角文字に変換するCの関数を作成した(このRuby拡張ライブラリの中で使われている関数)。 …
昨日の続き。 比較対象にC++とclojureを追加し、Javaのコードも若干変更した。下の三つが、それぞれのベンチマーク用のコード。(ベンチマーク用データは、前回と同様のものを使用する) 参照: mmap_t /** C++ **/ //////////////////////////// // ファイル名…
