Home > 7月, 2009

2009.07.14

CDB++ 1.1 released

CDB++のバージョン1.1をリリースしました.こちらも,libLBFGSで大変お世話になっている今道様からパッチを頂きました.

一つ目はgotoを使っていたためのコンパイルエラーの修正です.よく「gotoは読みづらくなるから使うな」という主張を見かけますが,私はエラー時の終了処理など,用途がはっきりしている場合は積極的に使うべきだと考えています.error_exitみたいなラベルを付ければ,エラー時の処理内容が分かりやすくなりますし,何重にもネストしたループから脱出する場合も,gotoを使わないとロジックが分かりづらくなります.

ただ,C++では変数の宣言が関数内の何処にでも書けるという仕様から,gotoの使い方が難しくなります.具体的には,次のようなコードの場合です.

    // Processing #1...
    if (error_condition_1) {
        goto error_exit;
    }

    // Processing #2...
    if (error_condition_2) {
        goto error_exit;
    }

    // Continue the procedure...
    int variable = foo(...);

    return true;

error_exit:
    // Error handling...
    return false;

このコードでは,error_exitにジャンプしたときに,variableの値が不定になるので,たとえerror_exit以降の処理でvariableを参照しなくても,gccのバージョンによってはコンパイルエラーになります.このミスは今までも何回かやっていたのですが,ついつい忘れてしまうんですよね.C++ではやっぱりgotoは慎重に使うスタンスが安全なのかもしれません.

また,ハッシュ関数をSuperFastHashからMurmurHashに置き換えました.私はこのハッシュ関数を知らず,これも今道さまに教えて頂きました.MurmurHashはSuperFastHashよりも2倍くらい高速だと謳われていて,コードもすごくシンプルです.「むらむらハッシュ」ってすごい名前だなぁと思っていたら,「multiply + rotate」が語源のようです.ハッシュ関数が変わってしまったので,CDB++の1.0と1.1のデータベース間に互換性はありません.

サンプルコードでは,成功したときに何も表示されない素っ気ない仕様だったので,「OK」を表示するようにしました.また,データベースの構築と,読み込みの手順を,別々の関数に分離し,コードを読みやすくしてみました.

2009.07.13

libLBFGS 1.8 released

libLBFGSのバージョン1.8をリリースしました.今回のリリースでは,backtracking法による線形探索でステップ長を選ぶときに,Armijo (sufficient decrease) 条件,regular Wolfe (sufficient decrease + curvature)条件,strong Wolfe条件の3つの基準を選べるようにしました.これらの基準の詳細に関しては,libLBFGSのドキュメンテーションもしくは『Numerical optimization』の本を参照してください.

今回のアップデートでは,いつもお世話になっている今道様から頂いたパッチをそのまま採用させて頂きました.

2009.07.09

CDB++ 1.0 released

CDB++という,静的ハッシュデータベースライブラリをリリースしました.ライセンスは修正BSDです.

静的ハッシュデータベースなので,いったんデータベースを構築したら,要素の追加や削除は行えません.その代わり,コンパクトなデータベース,高速な構築,高速な検索ができるようになっています.データ構造は,Constant Databaseを採用しています.Constant Databaseの実装はいくつかありますが,クロスプラットフォームでお手軽に使えるものがなかったので,作ってみました.また,このライブラリはcdbpp.hというインクルードファイルのみで構成されているので,このファイルをインクルードするだけでアプリケーションに組み込めます.

ハッシュデータベースには,Oracle DBTokyo Cabinetなど,優れた実装がたくさんあります.しかし,単にキーと値のペアをファイルに書き出し,後で簡単な検索を行うだけであれば,CDB++でも十分だと思います.