先週末から SWIG を使って分類器と学習器の Perl/Python/Ruby/Lua バインディングを書いていた．3年ぐらい前に書いた分類器の Ruby バインディングは，Ruby の C インタフェースが変わってそのままでは動かなかったので，結局一から書き直すことに．Python -> Ruby -> Perl -> Lua と書いてきて一番大変だったのは Perl．学部の時少し使っただけで，もはや文法をほとんど覚えていなかったので，何よりテスト用のスクリプトを書くのが大変だった． SWIG で書いた std::vector 用の入力インタフェースは以下．スクリプト言語側の配列を C++ の std::vector に詰め直して関数に渡すだけ．色々拾ったり編集したりしたものだけど，言語横断的に見れたほうが便が良いのでメモしておく．swig-2.0.3 + Perl 5.8.9/5.1

なお、メモリ消費量はtopコマンドで測ったので、かなり大雑把な数字だ。また、Cで同様の処理のコードを書くと、ほぼC++と同じ速度になる。 追記(2011/02/17 8:50)：Rubyによるベンチマークを追加。 追記(2011/02/17 11:00)：Smalltalkによるベンチマークを追加。ソースコードは「Smalltalkのtは小文字です」のループ回数を修正した。 追記(2011/02/17 16:00)：Perlによるベンチマークを追加。 追記(2011/02/18 10:30)：Java 1.6.0_22で実行した、Scalaによるベンチマークを追加。また、clang/llvmでC++とObjective Cの値を取り直し、改善が見られないのを確認。 追記(2011/02/18 14:30)：Ruby 1.8.7によるベンチマークを追加。1.9.2との速度差については、@IT

とりあえず、シリアライズしてファイルへの保存と、読み込みしてデシリアライズをしてみました。 ファイルに保存するときの拡張子は.mpacにするのがいいそうです。 #include <msgpack.hpp> #include <vector> #include <string> #include <iostream> #include <fstream> #include <boost/range/algorithm/for_each.hpp> void disp(const std::string& s) { std::cout << s << std::endl; } int main() { // シリアライズ { std::vector<std::string> vec; vec.push_back("Hello"); vec.push_back("MessagePack"); st

Boost.勉強会4にて発表した内容です。http://atnd.org/events/11551Read less

今回の内容は，0 を終端とする文字列と，長さを別に持つ文字列の扱いに関する小ネタです． 検索用のインタフェースを用意するとき，どちらか一方を選択するのであれば，後者にすると思います．しかし，できれば前者も提供したいと思うのが人情というものでしょう． という理由から，marisa-trie では，どちらも使えるようになっています．とはいえ，別々に実装するのは甚だ面倒です．検索用の関数は lookup(), find() 系列, predict() 系列と大量にあり，ほとんど同じになるものを別々に実装するなんて正気の沙汰ではありません．以降の修正でどちらか一方だけ直し忘れたなんてのも，実にありそうな話です． シンプルな対策は，0 を終端とする文字列を受け取ったとき，まず長さを求めてやるというものです．しかし，長い文字列が与えられる可能性がある場合，この手は危険です．100MB くらいのテキスト

marisa-trie を 0.1.0 に更新するべく，テストを追加したり，Visual C++ 用のファイルを作成しなおしたり，ドキュメントを更新したりしていました．実装の方はほぼ完成したという状況なので，ドキュメントの更新が終われば公開できると思います． 変更の内容は，以下のようになっています． エラー処理の方法を変更 旧版は放置でしたが，新版では marisa::Exception に統一しました． 機能の追加 TAIL にバイナリモードを追加しました．テキストモードでの構築に失敗したときは，自動的にバイナリモードを使うようになっています． インタフェースの変更・追加 特に，build() の引数が大幅に変更されています．旧版ではパラメータを個別に指定するようになっていましたが，新版ではフラグを使って一気に指定するようになりました． find() や predict() など，複数の

cpprefjp - C++日本語リファレンス まだサイトを用意しただけで、中身はまだまだです。 C++ Referenceが便利だったので、それの日本語版 + C++0x対応したサイトがほしい、というのが動機です。 boostjp Google Groupのメンバであれば編集できるようにしてありますので、サイトの充実のためにみなさんご協力お願いします。 cpprefjpのためのGoogle Groupも用意しようかと考えましたが、boostjpとメンバが大幅にかぶりそうなので、boostjp一本に絞ります。 cpprefjpでのご相談は、boostjpの方に投稿していただければと思います。

[2011/11/30 更新; std::(unordered_)map でメモリ使用量を見積もる - ny23の日記に従い，STL コンテナのメモリ使用量を計測] [2011/02/21 更新: marisa-trie 0.1.3; 発表資料（Prefix/Patricia Trie の入れ子による辞書圧縮） - やた＠はてな日記 にてこの記事の実験結果を引用されているので，以後原則更新しないこととする．なお，marisa-trie は 検索時間が短くなりました - やた＠はてな日記 にあるように，marisa-0.2.0-beta3 以降ではさらに検索が速くなっています．] [2011/02/18 更新: marisa-trie の仕様変更に伴い，追記の記述を整合性が取れるよう変更; 最新版では未確認] id:s-yata さんが marisa-trie を公開されたので，例によってベ

# 環境依存な内容な上，無駄に細かい話なので，「そういうこともあるかもねー」くらいに流しちゃってください． （追記 2011-01-11）新しい規格では std::string の Copy on Write（CoW: 書き込み時に複製）が実質禁止になるとのことです．後，gcc 4.5 の時点で CoW はやめてしまうみたいですし，「そんな時代もあった」くらいに軽く流しちゃってください．id:gintenlabo さん，コメントありがとうございます． （追記の続き）個人的には，std::string の CoW 動作は挙動が分かりにくくなるので止める方に賛成です．でも，std::vector なんかを拡張するときはどうするのかな…？コピーしてしまうのか，swap() を使うようにするのか…． （さらに追記 2011-01-11）おおっと，ムーブコンストラクタにムーブ代入演算子なんてものが…

概要 トライのライブラリを公開しました．ドキュメントはまったく用意できていませんが，とりあえず使えます．（追記 2011-01-09）ドキュメントを追加しました． http://code.google.com/p/marisa-trie/ ドキュメント ベンチマーク 使い方 インタフェース ツール インストール ビルド・インストールの方法は configure と make です．以下のようにすればインストールできます． ./configure make make check sudo make install インストールせずに試したいという方は，make install を省略して，tools/ 内部のツールを使うなり，lib/marisa/trie.h を見て使い方を確認するなりしてください．インストールせずにライブラリを利用するには，lib/ 以下のヘッダすべてと lib/libm

昨年末の投稿から引き続いて，多層トライをライブラリ化していました．現在，ソースコードはほとんど完成していますが，ライブラリの名前はまだ決まっていません．パトリシア（PATRICIA: Practical Algorithm To Retrieve Information Coded In Alphanumeric）のようにネタに走ってみるのもいいかな，なんて思いつつ…． 以下，少し前におこなった実験の結果です．最新版と比べるとサイズに数十バイト程度の誤差がありますけど，ほぼ無視できるので，そのままになっています． #tries: 辞書を構成するトライの数 #nodes: ノード数の合計 size: 辞書のサイズ build: 構築時間（us/key） restore: キーの ID から文字列を復元するのに要した時間（us/key） lookup: 完全一致検索に要した時間（us/key）

FM-indexのC++による実装 FM-index++を公開しました。 http://code.google.com/p/fmindex-plus-plus/ FM-index[1〜4]とは、圧縮全文索引の一種でO(n)時間とO(nlgσ)メモリー(n:テキスト長、σ:文字種類数)で構築することができます。最近では、テキスト処理ばかりでなくゲノム検索[5]など、いろいろなところで応用されています。今回は、クエリーに対する検索操作の内、exact検索、ハミング距離による検索、編集距離による検索の３つを実装しました。それぞれの計算時間は、qがクエリーの長さとすると、exact検索がO(q)時間、 ハミング距離による検索がO(q^σ)時間、編集距離による検索がO((q \times q)^σ)時間です。よって、４文字種のDNAや２０文字種のタンパク質など、文字種類数が少ない対象にはハミング距離

私は，スカートを履いた女の子に，スカートを履いたままぱんつを脱いで，脱ぎ終わったら右手を挙げるようにと，そう命令した．私は，その子が右手を挙げたのを確かに見た．だが，その子のスカートをめくってみたらぱんつはまだそこにあったのだ！ - http://twitter.com/Cryolite/status/8455287843 より一部改変 これは C++ advent calendar の参加記事です。 本ブログエントリは，以降のブログエントリと合わせて， C++0x のメモリモデルに関する規則を具体的な例や意味付けを交えた形で説明していくことを目的としています． 1998年に制定され，2003年に改訂された現行の C++ プログラミング言語標準規格 (以下， C++03) においては，プログラム中にただ1つの実行スレッドしか存在しない場合の規定しか記述されていませんでした*1．しかし， C