2011-12-01から1ヶ月間の記事一覧

文字列/バイト列用のハッシュ関数ライブラリ

A Hash Function for Hash Table Lookupに載っているハッシュ関数(Jenkins Hash)をCommon Lispで実装した。 github: jenkins-hash(0.0.2) 作成の主な動機は以下の二つ: SBCLにはバイト列用のハッシュ関数がない *1 一つのキーから複数のハッシュ値を得たい場…

N-Queen (Haskell + Common Lisp)

Etsukata blog: Haskellでlist monadを使ってN-Queens問題を解いてみました を見たのをきっかけに久しぶりにN-Queen問題を解くプログラムをHaskellで書いてみた。 ---- ファイル名: nqueen.hs ---- コンパイル: ghc -O2 -o nqueen nqueen.hs # Glasgow Haske…

ビットリバース

割合汎用的な、整数のビットを前後反転する関数を作成してみた。 2の乗数サイズの任意の整数型のビット反転が可能。 // 反転例 bit_reverse(0x0000FFFF) => 0xFFFF0000 // 実装 // バイト単位での変換表 const unsigned char REV_BYTE[]={ 0,128,64,192,32,1…

cc-dict: ハッシュテーブル

ハッシュテーブルを実装してみた。 ・cc-dict-0.0.3 チェイン法を用いたハッシュテーブルで、リンクリスト(チェイン)のノードを割り当てる際に自前のアロケータを使っている点以外は、特に変わったところもないと思う。 ベンチマーク 一応、ベンチマークも取…

std::tr1::unordered_mapのキーの型をconst char*にした場合の挙動

C++

g++(及びその他)のunordered_mapで文字列をキーにしたい場合の注意書き。 unordered_mapのようにconst char*を指定すると、キーが文字列ではなくポインタ(整数値)として解釈されてしまう*1。 以下、その際の挙動の確認用のコード: /** * ファイル名: str_map…

フィールドのポインタから、オブジェクト全体のポインタを取得するためのマクロ

構造体やクラスのインスタンスの特定のフィールドのアドレス(ポインタ)だけ分かっている場合に、そこからオブジェクト全体のポインタを取得したい場合に使うマクロ。 やっていることは単にフィールドのアドレスから、そのフィールドの(クラスor構造体の)先頭…